轉(zhuǎn)載請(qǐng)注明出處：http://www.reibang.com/p/462b42344098
上一篇《數(shù)據(jù)結(jié)構(gòu)與算法（二）咐旧，線性表》中介紹了數(shù)據(jù)結(jié)構(gòu)中線性表的兩種不同實(shí)現(xiàn)——順序表與鏈表掂骏。這一篇主要介紹線性表中比較特殊的兩種數(shù)據(jù)結(jié)構(gòu)——棧與隊(duì)列没讲。首先必須明確一點(diǎn)眯娱，棧和隊(duì)列都是線性表，它們中的元素都具有線性關(guān)系食零，即前驅(qū)后繼關(guān)系困乒。
目錄：
-
一、棧
- 1贰谣、基本概念
- 2娜搂、棧的順序存儲(chǔ)結(jié)構(gòu)
- 3、兩棧共享空間
- 4吱抚、棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
- 5百宇、棧的應(yīng)用——遞歸
-
二、隊(duì)列
- 1秘豹、基本概念
- 2携御、隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)
- 3、隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
三既绕、總結(jié)
一啄刹、棧
1、基本概念
棧（也稱下壓棧凄贩，堆棧）是僅允許在表尾進(jìn)行插入和刪除操作的線性表誓军。我們把允許插入和刪除的一端稱為棧頂（top），另一端稱為棧底（bottom）疲扎。棧是一種后進(jìn)先出（Last In First Out）的線性表昵时，簡(jiǎn)稱（LIFO)結(jié)構(gòu)。棧的一個(gè)典型應(yīng)用是在集合中保存元素的同時(shí)顛倒元素的相對(duì)順序椒丧。
抽象數(shù)據(jù)類型：
棧同線性表一樣壹甥，一般包括插入、刪除等基本操作。其基于泛型的API接口代碼如下：
public interface Stack<E> {
//棧是否為空
boolean isEmpty();
//棧的大小
int size();
//入棧
void push(E element);
//出棧
E pop();
//返回棧頂元素
E peek();
}
棧的實(shí)現(xiàn)通常有兩種方式：
- 基于數(shù)組的實(shí)現(xiàn)（順序存儲(chǔ)）
- 基于鏈表的實(shí)現(xiàn)（鏈?zhǔn)酱鎯?chǔ)）
2、棧的順序存儲(chǔ)結(jié)構(gòu)
棧的順序存儲(chǔ)結(jié)構(gòu)其實(shí)是線性表順序存儲(chǔ)結(jié)構(gòu)的簡(jiǎn)化，我們可以簡(jiǎn)稱它為「順序検崖撸」。其存儲(chǔ)結(jié)構(gòu)如下圖：
實(shí)現(xiàn)代碼如下：
import java.util.Iterator;
/**
* 能動(dòng)態(tài)調(diào)整數(shù)組大小的棧
*/
public class ArrayStack<E> implements Iterable<E>, Stack<E> {
private E[] elements;
private int size=0;
@SuppressWarnings("unchecked")
public ArrayStack() {
elements = (E[])new Object[1]; //注意：java不允許創(chuàng)建泛型數(shù)組
}
@Override public int size() {return size;}
@Override public boolean isEmpty() {return size == 0;}
//返回棧頂元素
@Override public E peek() {return elements[size-1];}
//調(diào)整數(shù)組大小
public void resizingArray(int num) {
@SuppressWarnings("unchecked")
E[] temp = (E[])new Object[num];
for(int i=0;i<size;i++) {
temp[i] = elements[i];
}
elements = temp;
}
//入棧
@Override public void push(E element) {
if(size == elements.length) {
resizingArray(2*size);//若數(shù)組已滿將長(zhǎng)度加倍
}
elements[size++] = element;
}
//出棧
@Override public E pop() {
E element = elements[--size];
elements[size] = null; //注意：避免對(duì)象游離
if(size > 0 && size == elements.length/4) {
resizingArray(elements.length/2);//小于數(shù)組1/4,將數(shù)組減半
}
return element;
}
//實(shí)現(xiàn)迭代器, Iterable接口在java.lang中如捅，但I(xiàn)terator在java.util中
public Iterator<E> iterator() {
return new Iterator<E>() {
private int num = size;
public boolean hasNext() {
return num > 0;
}
public E next() {
return elements[--num];
}
};
}
//測(cè)試
public static void main(String[] args) {
int[] a = {1,2,3,4,new Integer(5),6};//測(cè)試數(shù)組
ArrayStack<Integer> stack = new ArrayStack<Integer>();
System.out.print("入棧順序：");
for(int i=0;i<a.length;i++) {
System.out.print(a[i]+" ");
stack.push(a[i]);
}
System.out.println();
System.out.print("出棧順序數(shù)組實(shí)現(xiàn)：");
//迭代
for (Integer s : stack) {
System.out.print(s+" ");
}
}
}
優(yōu)點(diǎn)：
- 每項(xiàng)操作的用時(shí)都與集合大小無(wú)關(guān)
- 空間需求總是不超過(guò)集合大小乘以一個(gè)常數(shù)
缺點(diǎn)：push()和pop()操作有時(shí)會(huì)調(diào)整數(shù)組大小袭祟，這項(xiàng)操作的耗時(shí)和棧的大小成正比
3亏掀、兩棧共享空間
用一個(gè)數(shù)組來(lái)存儲(chǔ)兩個(gè)棧缸榄，讓一個(gè)棧的棧底為數(shù)組的始端，即下標(biāo)為0祝拯，另一個(gè)棧的棧底為數(shù)組的末端甚带，即下標(biāo)為 n-1。兩個(gè)棧若增加元素佳头，棧頂都向中間延伸鹰贵。其結(jié)構(gòu)如下：
這種結(jié)構(gòu)適合兩個(gè)棧有相同的數(shù)據(jù)類型并且空間需求具有相反的關(guān)系的情況，即一個(gè)棧增長(zhǎng)時(shí)另一個(gè)椏导危縮短碉输。如，買股票亭珍，有人買入敷钾，就一定有人賣出。
代碼：
public class SqDoubleStack<E> {
private static final int MAXSIZE = 20;
private E[] elements;
private int leftSize=0;
private int rightSize= MAXSIZE - 1;
//標(biāo)記是哪個(gè)棧
enum EnumStack {LEFT, RIGHT}
@SuppressWarnings("unchecked")
public SqDoubleStack() {
elements = (E[])new Object[MAXSIZE]; //注意：java不允許創(chuàng)建泛型數(shù)組
}
//入棧
public void push(E element, EnumStack es) {
if(leftSize - 1 == rightSize)
throw new RuntimeException("棧已滿肄梨，無(wú)法添加");
if(es == EnumStack.LEFT) {
elements[leftSize++] = element;
} else {
elements[rightSize--] = element;
}
}
//出棧
public E pop(EnumStack es ) {
if(es == EnumStack.LEFT) {
if(leftSize <= 0)
throw new RuntimeException("棧為空阻荒，無(wú)法刪除");
E element = elements[--leftSize];
elements[leftSize] = null; //注意：避免對(duì)象游離
return element;
} else {
if(rightSize >= MAXSIZE - 1)
throw new RuntimeException("棧為空，無(wú)法刪除");
E element = elements[++rightSize];
elements[rightSize] = null; //注意：避免對(duì)象游離
return element;
}
}
//測(cè)試
public static void main(String[] args) {
int[] a = {1,2,3,4,new Integer(5),6};//測(cè)試數(shù)組
SqDoubleStack<Integer> stack = new SqDoubleStack<Integer>();
System.out.print("入棧順序：");
for(int i=0;i<a.length;i++) {
System.out.print(a[i]+" ");
stack.push(a[i], EnumStack.RIGHT);
}
System.out.println();
System.out.print("出棧順序數(shù)組實(shí)現(xiàn)：");
//迭代
for(int i=0;i<a.length;i++) {
System.out.print(stack.pop(EnumStack.RIGHT)+" ");
}
}
}
4众羡、棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)侨赡，簡(jiǎn)稱鏈棧。為了操作方便粱侣，一般將棧頂放在單鏈表的頭部羊壹。通常對(duì)于鏈棧來(lái)說(shuō)，不需要頭結(jié)點(diǎn)齐婴。
其存儲(chǔ)結(jié)構(gòu)如下圖：
代碼實(shí)現(xiàn)如下：
import java.util.Iterator;
public class LinkedStack<E> implements Stack<E>, Iterable<E> {
private int size = 0;
private Node head = null;//棧頂
private class Node {
E element;
Node next;
Node(E element, Node next) {
this.element = element;
this.next = next;
}
}
@Override public int size() {return size;}
@Override public boolean isEmpty() {return size == 0;}
@Override public E peek() {return head.element;}
@Override public void push(E element) {
Node node = new Node(element, head);
head = node;
size++;
}
@Override public E pop() {
E element = head.element;
head = head.next;
size--;
return element;
}
//迭代器
public Iterator<E> iterator() {
return new Iterator<E>() {
private Node current = head;
public boolean hasNext() {
return current != null;
}
public E next() {
E element = current.element;
current = current.next;
return element;
}
};
}
public static void main(String[] args) {
int[] a = {1,2,3,4,new Integer(5),6};//測(cè)試數(shù)組
LinkedStack<Integer> stack = new LinkedStack<Integer>();
System.out.print("入棧順序：");
for(int i=0;i<a.length;i++) {
System.out.print(a[i]+" ");
stack.push(a[i]);
}
System.out.println();
System.out.print("出棧順序鏈表實(shí)現(xiàn)：");
for (Integer s : stack) {
System.out.print(s+" ");
}
}
}
注意：私有嵌套類（內(nèi)部類Node）的一個(gè)特點(diǎn)是只有包含他的類能夠直接訪問(wèn)他的實(shí)例變量油猫，無(wú)需將他的實(shí)例變量（element）聲明為public或private。即使將變量element聲明為private尔店，外部類依然可以通過(guò)Node.element的形式調(diào)用眨攘。
優(yōu)點(diǎn)：
- 所需空間和集合的大小成正比
- 操作時(shí)間和集合的大小無(wú)關(guān)
- 鏈棧的push和pop操作的時(shí)間復(fù)雜度都為 O(1)。
缺點(diǎn)：每個(gè)元素都有指針域嚣州，增加了內(nèi)存的開(kāi)銷鲫售。
順序棧與鏈棧的選擇和線性表一樣，若棧的元素變化不可預(yù)料该肴，有時(shí)很大情竹，有時(shí)很小，那最好使用鏈棧匀哄。反之秦效，若它的變化在可控范圍內(nèi)雏蛮，使用順序棧會(huì)好一些。
5阱州、棧的應(yīng)用——遞歸
棧的一個(gè)最重要的應(yīng)用就是遞歸挑秉。那么什么是遞歸呢？借用《哥德?tīng)柼酢釥栂拧秃铡愯抵蟪?/a>》中的話：
遞歸從狹義上來(lái)講，指的是計(jì)算機(jī)科學(xué)中（也就是像各位程序猿都熟悉的那樣）夜惭，一個(gè)模塊的程序在其內(nèi)部調(diào)用自身的技巧姻灶。如果我們把這個(gè)效果視覺(jué)化就成為了「德羅斯特效應(yīng)」，即圖片的一部分包涵了圖片本身诈茧。
如下面這張圖产喉，「先有書還是先有封面 ？」
我們把一個(gè)直接調(diào)用自身或通過(guò)一系列語(yǔ)句間接調(diào)用自身的函數(shù)敢会，稱為遞歸函數(shù)曾沈。每個(gè)遞歸函數(shù)必須至少有一個(gè)結(jié)束條件，即不在引用自身而是返回值退出走触。否則程序?qū)⑾萑霟o(wú)窮遞歸中晦譬。
一個(gè)遞歸的例子：斐波那契數(shù)列（Fibonacci）
遞歸實(shí)現(xiàn)：
public int fibonacci(int num) {
if(num < 2)
return num == 0 ? 0 : 1;
return fibonacci(num - 1) + fibonacci(num - 2);
}
迭代實(shí)現(xiàn)：
public int fibonacci(int num) {
if(num < 2)
return num == 0 ? 0 : 1;
int temp1 = 0;
int temp2 = 1;
int result = 0;
for(int i=2; i < num; i++) {
result = temp1 + temp2;
temp1 = temp2;
temp2 = result;
}
return result;
}
迭代與遞歸的區(qū)別：
- 迭代使用的是循環(huán)結(jié)構(gòu)，遞歸使用的是選擇結(jié)構(gòu)互广。
- 遞歸能使程序的結(jié)構(gòu)更清晰敛腌、簡(jiǎn)潔，更容易使人理解惫皱。但是大量的遞歸將消耗大量的內(nèi)存和時(shí)間像樊。
編譯器使用棧來(lái)實(shí)現(xiàn)遞歸。在前行階段旅敷，每一次遞歸生棍，函數(shù)的局部變量、參數(shù)值及返回地址都被壓入棧中媳谁；退回階段涂滴，這些元素被彈出，以恢復(fù)調(diào)用的狀態(tài)晴音。
二柔纵、隊(duì)列
1、基本概念
隊(duì)列是只允許在一端進(jìn)行插入操作锤躁，在另一端進(jìn)行刪除操作的線性表搁料。它是一種基于先進(jìn)先出（First In First Out，簡(jiǎn)稱FIFO）策略的集合類型。允許插入的一端稱為隊(duì)尾郭计，允許刪除的一端稱為隊(duì)頭霸琴。
抽象數(shù)據(jù)類型：
隊(duì)列作為一種特殊的線性表，它一樣包括插入昭伸、刪除等基本操作梧乘。其基于泛型的API接口代碼如下：
public interface Queue<E> {
//隊(duì)列是否為空
boolean isEmpty();
//隊(duì)列的大小
int size();
//入隊(duì)
void enQueue(E element);
//出隊(duì)
E deQueue();
}
同樣的，隊(duì)列具有兩種存儲(chǔ)方式：順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)庐杨。
2宋下、隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)
其存儲(chǔ)結(jié)構(gòu)如下圖：
與棧不同的是，隊(duì)列元素的出列是在隊(duì)頭辑莫，即下表為0的位置。為保證隊(duì)頭不為空罩引，每次出隊(duì)后隊(duì)列中的所有元素都得向前移動(dòng)各吨，此時(shí)時(shí)間復(fù)雜度為 O(n)。此時(shí)隊(duì)列的實(shí)現(xiàn)和線性表的順序存儲(chǔ)結(jié)構(gòu)完全相同袁铐，不在詳述揭蜒。
若不限制隊(duì)列的元素必須存儲(chǔ)在數(shù)組的前n個(gè)單元，出隊(duì)的性能就能大大提高剔桨。但這種結(jié)構(gòu)可能產(chǎn)生「假溢出」現(xiàn)象屉更，即數(shù)組末尾元素已被占用，如果繼續(xù)向后就會(huì)產(chǎn)生下標(biāo)越界洒缀，而前面為空瑰谜。如下圖：
解決「假溢出」的辦法就是若數(shù)組未滿，但后面滿了树绩，就從頭開(kāi)始入隊(duì)萨脑。我們把這種邏輯上首尾相連的順序存儲(chǔ)結(jié)構(gòu)稱為循環(huán)隊(duì)列。
數(shù)組實(shí)現(xiàn)隊(duì)列的過(guò)程：
假設(shè)開(kāi)始時(shí)數(shù)組長(zhǎng)度為5饺饭，如圖渤早，當(dāng)f入隊(duì)時(shí)，此時(shí)數(shù)組末尾元素已被占用瘫俊，如果繼續(xù)向后就會(huì)產(chǎn)生下標(biāo)越界鹊杖，但此時(shí)數(shù)組未滿，將從頭開(kāi)始入隊(duì)扛芽。當(dāng)數(shù)組滿（h入隊(duì)）時(shí)骂蓖，將數(shù)組的長(zhǎng)度加倍。
代碼如下：
import java.util.Iterator;
/**
* 能動(dòng)態(tài)調(diào)整數(shù)組大小的循環(huán)隊(duì)列
*/
public class CycleArrayQueue<E> implements Queue<E>, Iterable<E> {
private int size; //記錄隊(duì)列大小
private int first; //first表示頭元素的索引
private int last; //last表示尾元素后一個(gè)的索引
private E[] elements;
@SuppressWarnings("unchecked")
public CycleArrayQueue() {
elements = (E[])new Object[1];
}
@Override public int size() {return size;}
@Override public boolean isEmpty(){return size == 0;}
//調(diào)整數(shù)組大小
public void resizingArray(int num) {
@SuppressWarnings("unchecked")
E[] temp = (E[])new Object[num];
for(int i=0; i<size; i++) {
temp[i] = elements[(first+i) % elements.length];
}
elements = temp;
first = 0;//數(shù)組調(diào)整后first胸哥，last位置
last = size;
}
@Override public void enQueue(E element){
//當(dāng)隊(duì)列滿時(shí)涯竟，數(shù)組長(zhǎng)度加倍
if(size == elements.length)
resizingArray(2*size);
elements[last] = element;
last = (last+1) % elements.length;//【關(guān)鍵】
size++;
}
@Override public E deQueue() {
if(isEmpty())
return null;
E element = elements[first];
first = (first+1) % elements.length;//【關(guān)鍵】
size--;
//當(dāng)隊(duì)列長(zhǎng)度小于數(shù)組1/4時(shí)，數(shù)組長(zhǎng)度減半
if(size > 0 && size < elements.length/4)
resizingArray(2*size);
return element;
}
//實(shí)現(xiàn)迭代器
public Iterator<E> iterator() {
return new Iterator<E>() {
private int num = size;
private int current = first;
public boolean hasNext() {
return num > 0;
}
public E next() {
E element = elements[current++];
num--;
return element;
}
};
}
public static void main(String[] args) {
int[] a = {1,2,4,6,new Integer(10),5};
CycleArrayQueue<Integer> queue = new CycleArrayQueue<Integer>();
for(int i=0;i<a.length;i++) {
queue.enQueue(a[i]);
System.out.print(a[i]+" ");
}
System.out.println("入隊(duì)");
for (Integer s : queue) {
System.out.print(s+" ");
}
System.out.println("出隊(duì)");
}
}
3、隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)庐船，其實(shí)就是線性表的單鏈表银酬，只不過(guò)它只能尾進(jìn)頭出而已，我們簡(jiǎn)稱為「鏈隊(duì)列」筐钟。
存儲(chǔ)結(jié)構(gòu)如下圖：
代碼如下：
import java.util.Iterator;
/**
* 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)揩瞪，不帶頭結(jié)點(diǎn)的實(shí)現(xiàn)
*/
public class LinkedQueue<E> implements Queue<E>, Iterable<E> {
private Node first; //頭結(jié)點(diǎn)
private Node last; //尾結(jié)點(diǎn)
private int size = 0;
private class Node {
E element;
Node next;
Node(E element) {
this.element = element;
}
}
@Override public int size() {return size;}
@Override public boolean isEmpty(){return size == 0;}
//入隊(duì)
@Override public void enQueue(E element) {
Node oldLast = last;
last = new Node(element);
if(isEmpty()) {
first = last;//【要點(diǎn)】
}else {
oldLast.next = last;
}
size++;
}
//出隊(duì)
@Override public E deQueue() {
E element = first.element;
first = first.next;
size--;
if(isEmpty())
last = null;//【要點(diǎn)】
return element;
}
//實(shí)現(xiàn)迭代器
public Iterator<E> iterator() {
return new Iterator<E>() {
private Node current = first;
public boolean hasNext() {
return current != null;
}
public E next(){
E element = current.element;
current = current.next;
return element;
}
};
}
public static void main(String[] args) {
int[] a = {1,2,4,6,new Integer(10),5};
LinkedQueue<Integer> queue = new LinkedQueue<Integer>();
for(int i=0;i<a.length;i++) {
queue.enQueue(a[i]);
System.out.print(a[i]+" ");
}
System.out.println("入隊(duì)");
for (Integer s : queue) {
System.out.print(s+" ");
}
System.out.println("出隊(duì)");
}
}
循環(huán)隊(duì)列與鏈隊(duì)列，它們的基本操作的時(shí)間復(fù)雜度都為 O(1)篓冲。和線性表相同李破，在可以確定隊(duì)列長(zhǎng)度的情況下，建議使用循環(huán)隊(duì)列壹将；無(wú)法確定隊(duì)列長(zhǎng)度時(shí)使用鏈隊(duì)列嗤攻。
三、總結(jié)
棧與隊(duì)列诽俯，它們都是特殊的線性表妇菱，只是對(duì)插入和刪除操作做了限制。棧限定僅能在棧頂進(jìn)行插入和刪除操作暴区，而隊(duì)列限定只能在隊(duì)尾插入闯团，在隊(duì)頭刪除。它們都可以使用順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)兩種方式來(lái)實(shí)現(xiàn)仙粱。
對(duì)于棧來(lái)說(shuō)房交，若兩個(gè)棧數(shù)據(jù)類型相同，空間需求相反伐割，則可以使用共享數(shù)組空間的方法來(lái)實(shí)現(xiàn)候味，以提高空間利用率。對(duì)于隊(duì)列來(lái)說(shuō)隔心，為避免插入刪除操作時(shí)數(shù)據(jù)的移動(dòng)负溪，同時(shí)避免「假溢出」現(xiàn)象，引入了循環(huán)隊(duì)列济炎，使得隊(duì)列的基本操作的時(shí)間復(fù)雜度降為 O(1)川抡。
