鍊式存儲結構實作棧
上一節我們說了關于線性表的鍊式存儲結構的實作，今天的棧也是建立線上性表的基礎上
棧的特性：先進後出
1.删除時（出棧）：我們考慮時間複雜度時發現：删除時的頭删的複雜度為O(1),而尾删的時間複雜度為O（n），故而我們出棧選擇從頭出（頭删）
2.插入時（入棧）：插入的複雜度頭尾相同都為O（1），是以對應出棧，我們預設從頭入棧（頭加）
由此得出：實作的鍊式存儲結構的棧從頭出入棧，而rear指向的即是它的棧底
理清思路，我們就可以在linkedlist的基礎上完成
棧的實作：
public class LinkedStack<E> implements Stack<E>{
private LinkedList<E> list;
public LinkedStack() {
list = new LinkedList<E>();
}
@Override
public int getSize() {
return list.getSize();
}
@Override
public boolean isEmpty() {
return list.isEmpty();
}
@Override
public void push(E e) {
list.addFirst(e);
}
@Override
public E pop() {
return list.removeFirst();
}
@Override
public E peek() {
return list.getFirst();
}
@Override
public void clear() {
list.clear();
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("LinkedStack:size=" + getSize() + "\n");
if (isEmpty())
sb.append("[]");
else {
sb.append('[');
for(int i = 0;i<getSize()-1;i++) {
sb.append(list.get(i)+",");
}
sb.append(list.get(getSize()-1) + "]");
}
return sb.toString();
}
@Override
public boolean equals(Object obj) {
if(obj == null)return false;
if(obj == this)return true;
if(obj instanceof LinkedStack) {
LinkedStack<E> newlist = (LinkedStack<E>)obj;
return newlist.list.equals(list);
}
return false;
}
}
鍊式存儲結構實作隊列
同樣的，我們分析隊列的特性，發現它也是建立線上性表的基礎上
隊列的特性：先進先出
1.删除時（出棧）：同樣的，我們考慮時間複雜度時發現在隊列中：删除時的頭删的複雜度為O(1),而尾删的時間複雜度為O（n），故而我們出棧選擇從頭出（頭删）
2.插入時（入棧）：插入的複雜度頭尾相同都為O（1），是以對應出隊，我們預設從尾入隊（頭加）
由此得出：實作的鍊式存儲結構的隊列從尾入隊，從頭出隊，而rear指向的即是它的隊尾（入隊的位置）
理清思路，我們就可以在linkedlist的基礎上完成
隊列的實作：
ps：
- 1.空隊列時，head和rear都指向頭結點
- 2.入隊操作：在隊尾添加元素,先将隊尾元素的next指向添加的元素，然後将隊尾指針重新指向新的隊尾即可。
- 3.出隊操作：頭結結點指向的結點即為隊頭結點，出隊操作，就是把隊頭結點幹掉，先把頭結點指向新的隊頭結點（也就是舊的隊頭結點的後繼結點），然後釋放舊的隊頭結點。如果連結清單除頭結點外隻剩一個元素時，則需将rear指向頭結點即可。
public class LinkedQueue<E> implements Queue<E>{
private LinkedList<E> list ;
public LinkedQueue() {
list = new LinkedList<E>();
}
public LinkedQueue(E[] arr) {
}
@Override
public int getSize() {
return list.getSize();
}
@Override
public boolean isEmpty() {
return list.isEmpty();
}
@Override
public void enqueue(E e) {
list.addLast(e);
}
@Override
public E dequeue() {
return list.removeFirst();
}
@Override
public E getFront() {
return list.getFirst();
}
@Override
public E getRear() {
return list.getLast();
}
@Override
public void clear() {
list.clear();
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("LinkedQueue:size=" + getSize() + "\n");
if (isEmpty())
sb.append("[]");
else {
sb.append('[');
for(int i = 0;i<getSize()-1;i++) {
sb.append(list.get(i)+",");
}
sb.append(list.get(getSize()-1) + "]");
}
return sb.toString();
}
@Override
public boolean equals(Object obj) {
if(obj == null)return false;
if(obj == this)return true;
if(obj instanceof LinkedQueue) {
LinkedQueue<E> newlist = (LinkedQueue<E>)obj;
return newlist.list.equals(list);
}
return false;
}
}
單向循環連結清單
- 我們學習了單向連結清單，一般單向鍊的rear.next指向空；
- 那麼，有循環隊列就有循環連結清單，從單向連結清單實作循環連結清單，最重要的就是将頭尾相接，使得尾循環完後緊接的是頭，故rear.next = head;
- 結構特點:連結清單中最後一個結點的指針不再是結束标記，而是指向整個連結清單的第一個結點，進而使單連結清單形成一個環。
- 和單連結清單相比，循環單連結清單的長處是從鍊尾到鍊頭比較友善。當要處理的資料元素序列具有環型結構特點時，适合于采用循環單連結清單
1.當其為空時，頭尾指針指向空，當隻有一個節點時，頭尾指針都指向它
2.多個時，head指向頭節點，rear指向尾節點，頭插時移動頭指針，尾插時移動尾指針
public class LoopSingle<E> implements List<E> {
private Node head;
private Node rear;
private int size;
public LoopSingle() {
head = null;
rear = null;
size = 0;
}
public LoopSingle(E[] arr) {
}
@Override
public int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public void add(int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("下标值越界！");
}
Node n = new Node(e, null);
if (size == 0) {
head = n;
rear = n;
rear.next = head;
} else if (index == 0) {
rear.next = n;
n.next = head;
head = n;
} else if (index == size) {
n.next = rear.next;
rear.next = n;
rear = rear.next;
} else {
Node p = head;
for (int i = 0; i < index - 1; i++) {
p = p.next;
}
n.next = p.next;
p.next = n;
}
size++;
}
@Override
public void addFirst(E e) {
add(0, e);
}
@Override
public void addLast(E e) {
add(size, e);
}
@Override
public E get(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("下标值越界！");
}
E e = null;
Node n;
if (index == 0) {
e = head.data;
} else if (index == size - 1) {
e = rear.data;
} else {
n = head;
for (int i = 0; i < index; i++) {
n = n.next;
}
e = n.data;
}
return e;
}
@Override
public E getFirst() {
return get(0);
}
@Override
public E getLast() {
return get(size - 1);
}
@Override
public void set(int index, E e) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("下标值越界！");
}
Node n;
if (index == 0) {
head.data = e;
} else if (index == size - 1) {
rear.data = e;
} else {
n = head;
for (int i = 0; i < index; i++) {
n = n.next;
}
n.data = e;
}
}
@Override
public boolean contains(E e) {
return find(e) != -1;
}
@Override
public int find(E e) {
if (isEmpty()) {
return -1;
}
if (size == 1)
if (e == head.data)
return 0;
int i = 0;
Node p = head;
while (p.next != head) {
if (p.data == e)
return i;
p = p.next;
i++;
}
return -1;
}
@Override
public E remove(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("下标值越界！");
}
E e = null;
Node n;
if(size == 1) {
clear();
}
if (index == 0) {
e = head.data;
head = head.next;
rear.next = head;
} else if (index == size - 1) {
e = rear.data;
n = head;
while(n.next!=rear){
n = n.next;
}
n.next = rear.next;
rear = n;
} else {
n = head;
for (int i = 0; i < index; i++) {
n = n.next;
}
n.next = n.next.next;
}
size--;
return e;
}
@Override
public E removeFirst() {
return remove(0);
}
@Override
public E removeLast() {
return remove(size-1);
}
@Override
public void removeElement(E e) {
remove(find(e));
}
@Override
public void clear() {
head = null;
rear = null;
size = 0;
}
class Node {
E data;
Node next;
public Node() {
this(null, null);
}
public Node(E e, Node next) {
this.data = e;
this.next = next;
}
public String toString() {
return data.toString();
}
}
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("LoopSingle:size=" + getSize() + "\n");
if (isEmpty())
sb.append("[]");
else {
sb.append('[');
Node p = head;
while (true) {
sb.append(p.data);
if(p.next == head) {
sb.append(']');
break;
}else {
sb.append(',');
}
p = p.next;
}
}
return sb.toString();
}
public boolean equals(Object obj) {
if(obj == null)return false;
if(obj == this)return true;
if(obj instanceof LoopSingle) {
LoopSingle<E> newlist = (LoopSingle<E>)obj;
if(getSize() == newlist.getSize()) {
Node n = newlist.head;
Node p = head;
for(int i = 0;i<getSize();i++) {
n = n.next;
p = p.next;
if(n.data != p.data)return false;
}
return true;
}
}
return false;
}
}