棧
棧： 限定僅在表尾進(jìn)行插入和刪除操作的線性表荡陷；
- 后進(jìn)先出（LIFO)雨效。
- 在表尾進(jìn)行操作，表尾是棧頂废赞；最新進(jìn)棧的元素在棧底徽龟。
棧的ADT
進(jìn)棧&出棧
棧的存儲結(jié)構(gòu)實現(xiàn)
- 順序棧
棧也是線性表，只是對表中元素的插入和刪除位置做了限定唉地，因此我們很容易想到利用一維數(shù)組實現(xiàn)棧的存儲結(jié)構(gòu)据悔。Java中的Stack類繼承自Vector，就是用數(shù)組實現(xiàn)耘沼。
Stack.java
public class Stack<E> extends Vector<E> {
public Stack() {
}
public E push(E item) {
addElement(item);
return item;
}
public synchronized E pop() {
E obj;
int len = size();
obj = peek();
removeElementAt(len - 1);
return obj;
}
public synchronized E peek() {
int len = size();
if (len == 0)
throw new EmptyStackException();
return elementAt(len - 1);
}
public boolean empty() {
return size() == 0;
}
public synchronized int search(Object o) {
int i = lastIndexOf(o);
if (i >= 0) {
return size() - i;
}
return -1;
}
private static final long serialVersionUID = 1224463164541339165L;
}
- 兩棧共享存儲空間
如果我們有兩個相同類型的棧极颓，我們?yōu)樗麄兏髯蚤_辟了數(shù)組空間，極有可能第一個棧已經(jīng)滿了群嗤，再進(jìn)棧就溢出了菠隆，而另一個棧還有很多存儲空間空閑。這時狂秘，我們可以充分利用順序棧的單向延伸的特性骇径，使用一個數(shù)組來存儲兩個棧，讓一個棧的棧底為數(shù)組的始端赃绊，另一個棧的棧底為數(shù)組的末端既峡，每個棧從各自的端點向中間延伸。
ShareStack.java
/**
* Created by engineer on 2017/10/22.
*/
public class ShareStack<T> {
private Object[] element; //存放元素的數(shù)組
private int stackSize; // 棧大小
private int top1; //棧1的棧頂指針
private int top2; //棧2的棧頂指針
/**
* 初始化棧
* @param size
*/
public ShareStack(int size){
element = new Object[size];
stackSize = size;
top1 = -1;
top2 = stackSize;
}
/**
* 壓棧
* @param i 第幾個棧
* @param o 入棧元素
* @return
*/
public boolean push(int i , Object o){
if(top1 == top2 - 1)
throw new RuntimeException("棧滿碧查！");
else if(i == 1){
top1++;
element[top1] = o;
}else if(i == 2){
top2--;
element[top2] = o;
}else
throw new RuntimeException("輸入錯誤运敢！");
return true;
}
/**
* 出棧
* @param i
* @return
*/
@SuppressWarnings("unchecked")
public T pop(int i){
if(i == 1){
if(top1 == -1)
throw new RuntimeException("棧1為空");
return (T)element[top1--];
} else if(i == 2){
if(top2 == stackSize)
throw new RuntimeException("棧2為空");
return (T)element[top2++];
} else
throw new RuntimeException("輸入錯誤！");
}
/**
* 獲取棧頂元素
* @param i
* @return
*/
@SuppressWarnings("unchecked")
public T get(int i){
if(i == 1){
if(top1 == -1)
throw new RuntimeException("棧1為空");
return (T)element[top1];
} else if(i == 2){
if(top2 == stackSize)
throw new RuntimeException("棧2為空");
return (T)element[top2];
} else
throw new RuntimeException("輸入錯誤忠售！");
}
/**
* 判斷棧是否為空
* @param i
* @return
*/
public boolean isEmpty(int i){
if(i == 1){
if(top1 == -1)
return true;
else
return false;
} else if(i == 2){
if(top2 == stackSize)
return true;
else
return false;
} else
throw new RuntimeException("輸入錯誤传惠！");
}
}
當(dāng)然，考慮到數(shù)組需要在初始化的時候限定大小稻扬，同時也要考慮擴(kuò)容的問題卦方。因此棧也可以使用鏈表來實現(xiàn)；這個后面一起討論泰佳，這里就不展開來說了盼砍。
棧這種數(shù)據(jù)結(jié)構(gòu)尘吗，非常實用；Android中Activity的回退棧就是最好的例子浇坐，正常模式下睬捶，我們通過startActivity就是將一個Activity壓入了回退棧，finish()方法就是從回退棧里彈出最頂部的Activity近刘；當(dāng)然擒贸，實際流程有很多別的操作，這里也只是大體流程觉渴；遞歸思想也是利用了棧這種結(jié)構(gòu)介劫。
隊列
隊列： 只允許在一端進(jìn)行插入操作、而在另一端進(jìn)行刪除操作的線性表案淋。
- 先進(jìn)先出(FIFO)
- 在隊尾進(jìn)行插入座韵，從隊頭進(jìn)行刪除
隊列的ADT
入隊列&出隊列
隊列的存儲結(jié)構(gòu)實現(xiàn)
- 順序存儲結(jié)構(gòu)
使用數(shù)組實現(xiàn)隊列的存儲結(jié)構(gòu)時，為了避免每次從隊頭刪除元素時哎迄，移動后面的每個元素回右，加入了front和rear兩個指針，分別指向隊頭和隊尾漱挚；這樣每次從隊頭刪除元素時翔烁，移動front指針即可，而不必移動大量的元素旨涝，但是這樣勢必會造成假溢出的問題蹬屹，存儲空間得不到充分的利用，因此需要采用循環(huán)隊列的方式實現(xiàn)了隊列的順序存儲結(jié)構(gòu)白华。
- 循環(huán)隊列
假定在循環(huán)隊列中慨默，QueueSize為循環(huán)隊列大小，即數(shù)組長度弧腥，則有以下結(jié)論：
- 循環(huán)隊列空的條件：front==rear;
- 循環(huán)隊列滿的條件：(rear+1)%QueueSize=front;
- 循環(huán)隊列長度：(rear-front*QueueSize)%QueueSize;
總的來說厦取，采用順序存儲結(jié)構(gòu)，還是需要考慮容量的問題管搪。因此虾攻，在我們無法預(yù)估隊列長度的情況下，需要關(guān)注鏈?zhǔn)酱鎯Y(jié)構(gòu)更鲁。
- 鏈?zhǔn)酱鎯Y(jié)構(gòu)
在上文中我們已經(jīng)說過霎箍，LinkList實現(xiàn)了Deque接口，因此它就是用鏈表實現(xiàn)的隊列澡为。這里簡單分析一下入隊push和出隊pop操作的實現(xiàn)漂坏。
LinkedList-add 隊列入隊
public boolean add(E e) {
linkLast(e);
return true;
}
/**
* Links e as last element.
*/
void linkLast(E e) {
final Node<E> l = last;
//創(chuàng)建新的結(jié)點，其前驅(qū)指向last,后繼為null
final Node<E> newNode = new Node<>(l, e, null);
//last 指針指向新的結(jié)點
last = newNode;
if (l == null)
first = newNode; //如果鏈表為空，frist指針指向新的結(jié)點
else
l.next = newNode; //鏈表不為空顶别，新的結(jié)點連接到原來最后一個結(jié)點之后
size++; //鏈表長度+1
modCount++;
}
LinkList是一個雙向鏈表谷徙，這里first是執(zhí)行第一個結(jié)點的指針，last是指向最后一個結(jié)點指針筋夏。
LinkList-pop 隊列出隊
public E pop() {
return removeFirst();
}
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
//獲取要刪除結(jié)點的值
final E element = f.item;
//得到f的下一個結(jié)點蒂胞，也就是第二個結(jié)點
final Node<E> next = f.next;
// f 釋放
f.item = null;
f.next = null; // help GC
// first 指針指向f的下個結(jié)點图呢，
first = next;
// f 后面已經(jīng)沒有結(jié)點了
if (next == null)
last = null;
else
next.prev = null; // 第二個結(jié)點（也就是現(xiàn)在的第一個結(jié)點)前驅(qū)為null,因為LinkList 是雙端鏈表条篷，非循環(huán)。
size--;
modCount++;
return element;
}
這里就是一個典型的單鏈表刪除頭結(jié)點的實現(xiàn)蛤织。至此赴叹，我們已經(jīng)掌握了棧和隊列這兩種數(shù)據(jù)結(jié)構(gòu)各自的特點；下面再來看看Java官方提供的關(guān)于棧和隊列的實現(xiàn)指蚜。
Deque
這里主要說一下Deque這個類乞巧。
/**
* A linear collection that supports element insertion and removal at
* both ends. The name <i>deque</i> is short for "double ended queue"
* and is usually pronounced "deck". Most {@code Deque}
* implementations place no fixed limits on the number of elements
* they may contain, but this interface supports capacity-restricted
* deques as well as those with no fixed size limit.
* /
public interface Deque<E> extends Queue<E> {
void addFirst(E var1);
void addLast(E var1);
boolean offerFirst(E var1);
boolean offerLast(E var1);
E removeFirst();
E removeLast();
E pollFirst();
E pollLast();
E getFirst();
E getLast();
E peekFirst();
E peekLast();
boolean add(E var1);
boolean offer(E var1);
E remove();
E poll();
E element();
E peek();
void push(E var1);
E pop();
........
}
Deque接口是“double ended queue”的縮寫(通常讀作“deck”)，即雙端隊列摊鸡，支持在線性表的兩端插入和刪除元素绽媒，繼承Queue接口。大多數(shù)的實現(xiàn)對元素的數(shù)量沒有限制免猾，但這個接口既支持有容量限制的deque是辕，也支持沒有固定大小限制的。
我們知道Queue接口定義了隊列的操作集合猎提，而Deque接口又在其基礎(chǔ)上擴(kuò)展获三，定義了在雙端進(jìn)行插入刪除的操作。因此锨苏，我們很可以認(rèn)為疙教，Deque接口既可以當(dāng)做隊列，也可以當(dāng)做棧伞租。
Deque的鏈?zhǔn)酱鎯崿F(xiàn)LinkList
因此贞谓，回過頭來，我們可以發(fā)現(xiàn)LinkList以鏈表結(jié)構(gòu)葵诈，同時實現(xiàn)了隊列和棧裸弦。前面已經(jīng)分析了LinkList作為一個隊列的操作。下面我們可以看看，他又是如何實現(xiàn)鏈?zhǔn)浇Y(jié)構(gòu)實現(xiàn)隊列的。
入棧
public void addLast(E e) {
linkLast(e);
}
可以看到祝迂，對于入棧操作和隊列樣茸歧，都是在鏈表最后插入元素，和隊列一樣使用了linkLast()方法静檬。
出棧
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
出棧同樣是用了unlinkLast 方法，只不過出棧的元素是last鄙才。而不是隊列中的first主之。
Deque的順序存儲實現(xiàn) ArrayDeque
ArrayDeque 用一個動態(tài)數(shù)組實現(xiàn)了棧和隊列所需的所有操作择吊。
添加元素
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)
doubleCapacity();
}
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
elements[tail] = e;
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}
private void doubleCapacity() {
assert head == tail;
int p = head;
int n = elements.length;
int r = n - p; // number of elements to the right of p
int newCapacity = n << 1;
if (newCapacity < 0)
throw new IllegalStateException("Sorry, deque too big");
Object[] a = new Object[newCapacity];
System.arraycopy(elements, p, a, 0, r);
System.arraycopy(elements, 0, a, r, p);
elements = a;
head = 0;
tail = n;
}
這里可以看到，無論是頭部還是尾部添加新元素槽奕，當(dāng)需要擴(kuò)容時几睛，會直接變化為原來的2倍。同時需要復(fù)制并移動大量的元素粤攒。
刪除元素
public E pollFirst() {
final Object[] elements = this.elements;
final int h = head;
@SuppressWarnings("unchecked")
E result = (E) elements[h];
// Element is null if deque empty
if (result != null) {
elements[h] = null; // Must null out slot
head = (h + 1) & (elements.length - 1);
}
return result;
}
public E pollLast() {
final Object[] elements = this.elements;
final int t = (tail - 1) & (elements.length - 1);
@SuppressWarnings("unchecked")
E result = (E) elements[t];
if (result != null) {
elements[t] = null;
tail = t;
}
return result;
}
從頭部和尾部刪除（獲人）元素，就比較方便了夯接，修改head和tail位置即可焕济。head是當(dāng)前數(shù)組中第一個元素的位置，tail是數(shù)組中第一個空的位置盔几。
BlockingDeque
/**
* A {@link Deque} that additionally supports blocking operations that wait
* for the deque to become non-empty when retrieving an element, and wait for
* space to become available in the deque when storing an element.
* /
public interface BlockingDeque<E> extends BlockingQueue<E>, Deque<E> {
}
關(guān)于Deque最后一點晴弃，BlockingDeque 在Deque 基礎(chǔ)上又實現(xiàn)了阻塞的功能，當(dāng)椦放模或隊列為空時上鞠，不允許出棧或出隊列芯丧，會保持阻塞芍阎，直到有可出棧元素出現(xiàn)；同理注整，隊列滿時能曾，不允許入隊，除非有元素出棧騰出了空間肿轨。常用的具體實現(xiàn)類是LinkedBlockingDeque寿冕，使用鏈?zhǔn)浇Y(jié)構(gòu)實現(xiàn)了他的阻塞功能。Android中大家非常熟悉的AsyncTask 內(nèi)部的線程池隊列椒袍，就是使用LinkedBlockingDeque實現(xiàn)驼唱，長度為128，保證了AsyncTask的串行執(zhí)行驹暑。
這里比較一下可以發(fā)現(xiàn)玫恳，對于棧和隊列這兩種特殊的數(shù)據(jù)結(jié)構(gòu)，由于獲扔欧（查找）元素的位置已經(jīng)被限定京办，因此采用順序存儲結(jié)構(gòu)并沒有非常大的優(yōu)勢，反而是在添加元素由于數(shù)組容量的問題還會帶來額外的消耗帆焕；因此惭婿，在無法預(yù)先知道數(shù)據(jù)容量的情況下，使用鏈?zhǔn)浇Y(jié)構(gòu)實現(xiàn)棧和隊列應(yīng)該是更好的選擇。
好了财饥，棧和隊列就先到這里了换吧。
