棧

一、什么是棧？

1.后進(jìn)者先出，先進(jìn)者后出，這就是典型的“棧”結(jié)構(gòu)。
2.從棧的操作特性來看，是一種“操作受限”的線性表，只允許在端插入和刪除數(shù)據(jù)。

二、為什么需要棧？

1.棧是一種操作受限的數(shù)據(jù)結(jié)構(gòu)，其操作特性用數(shù)組和鏈表均可實(shí)現(xiàn)。
2.但，任何數(shù)據(jù)結(jié)構(gòu)都是對特定應(yīng)用場景的抽象，數(shù)組和鏈表雖然使用起來更加靈活，但卻暴露了幾乎所有的操作，難免會引發(fā)錯誤操作的風(fēng)險。
3.所以，當(dāng)某個數(shù)據(jù)集合只涉及在某端插入和刪除數(shù)據(jù)，且滿足后進(jìn)者先出，先進(jìn)者后出的操作特性時，我們應(yīng)該首選棧這種數(shù)據(jù)結(jié)構(gòu)。

三、如何實(shí)現(xiàn)棧？

1.棧的API
public class Stack {
//壓棧
public void push(Item item){}
//彈棧
public Item pop(){}
//是否為空
public boolean isEmpty(){}
//棧中數(shù)據(jù)的數(shù)量
public int size(){}
//返回棧中最近添加的元素而不刪除它
public Item peek(){}
}

實(shí)現(xiàn)

2.1 數(shù)組實(shí)現(xiàn)（自動擴(kuò)容）

時間復(fù)雜度分析：根據(jù)均攤復(fù)雜度的定義，可以得數(shù)組實(shí)現(xiàn)（自動擴(kuò)容）符合大多數(shù)情況是O(1)級別復(fù)雜度，個別情況是O(n)級別復(fù)雜度，比如自動擴(kuò)容時，會進(jìn)行完整數(shù)據(jù)的拷貝。
空間復(fù)雜度分析：在入棧和出棧的過程中，只需要一兩個臨時變量存儲空間，所以O(shè)(1)級別。我們說空間復(fù)雜度的時候，是指除了原本的數(shù)據(jù)存儲空間外，算法運(yùn)行還需要額外的存儲空間。

// 基于數(shù)組實(shí)現(xiàn)的順序棧 public class ArrayStack {private String[] items; // 數(shù)組private int count; // 棧中元素個數(shù)private int n; //棧的大小// 初始化數(shù)組，申請一個大小為n的數(shù)組空間public ArrayStack(int n) {this.items = new String[n];this.n = n;this.count = 0;}// 入棧操作public boolean push(String item) {// 數(shù)組空間不夠了，直接返回false，入棧失敗。if (count == n) return false;// 將item放到下標(biāo)為count的位置，并且count加一items[count] = item;++count;return true;}// 出棧操作public String pop() {// 棧為空，則直接返回nullif (count == 0) return null;// 返回下標(biāo)為count-1的數(shù)組元素，并且棧中元素個數(shù)count減一String tmp = items[count-1];--count;return tmp;} }

2.2 鏈表實(shí)現(xiàn)

時間復(fù)雜度分析：壓棧和彈棧的時間復(fù)雜度均為O(1)級別，因?yàn)橹恍韪膯蝹€節(jié)點(diǎn)的索引即可。
空間復(fù)雜度分析：在入棧和出棧的過程中，只需要一兩個臨時變量存儲空間，所以O(shè)(1)級別。我們說空間復(fù)雜度的時候，是指除了原本的數(shù)據(jù)存儲空間外，算法運(yùn)行還需要額外的存儲空間。
實(shí)現(xiàn)代碼：（見另一條留言）

public class StackOfLinked<Item> implements Iterable<Item> { //定義一個內(nèi)部類，就可以直接使用類型參數(shù) private class Node{ Item item; Node next; } private Node first; private int N; //構(gòu)造器 public StackOfLinked(){} //添加 public void push(Item item){ Node oldfirst = first; first = new Node(); first.item = item; first.next = oldfirst; N++; } //刪除 public Item pop(){ Item item = first.item; first = first.next; N--; return item; } //是否為空 public boolean isEmpty(){ return N == 0; } //元素數(shù)量 public int size(){ return N; } //返回棧中最近添加的元素而不刪除它 public Item peek(){ return first.item; } @Override public Iterator<Item> iterator() { return new LinkedIterator(); } //內(nèi)部類：迭代器 class LinkedIterator implements Iterator{ int i = N; Node t = first; @Override public boolean hasNext() { return i > 0; } @Override public Item next() { Item item = (Item) t.item; t = t.next; i--; return item; } } }

三、棧的應(yīng)用

1.棧在函數(shù)調(diào)用中的應(yīng)用

操作系統(tǒng)給每個線程分配了一塊獨(dú)立的內(nèi)存空間，這塊內(nèi)存被組織成“棧”這種結(jié)構(gòu)，用來存儲函數(shù)調(diào)用時的臨時變量。每進(jìn)入一個函數(shù)，就會將其中的臨時變量作為棧幀入棧，當(dāng)被調(diào)用函數(shù)執(zhí)行完成，返回之后，將這個函數(shù)對應(yīng)的棧幀出棧。

2.棧在表達(dá)式求值中的應(yīng)用（比如：34+13*9+44-12/3）

利用兩個棧，其中一個用來保存操作數(shù)，另一個用來保存運(yùn)算符。我們從左向右遍歷表達(dá)式，當(dāng)遇到數(shù)字，我們就直接壓入操作數(shù)棧；當(dāng)遇到運(yùn)算符，就與運(yùn)算符棧的棧頂元素進(jìn)行比較，若比運(yùn)算符棧頂元素優(yōu)先級高，就將當(dāng)前運(yùn)算符壓入棧，若比運(yùn)算符棧頂元素的優(yōu)先級低或者相同，從運(yùn)算符棧中取出棧頂運(yùn)算符，從操作數(shù)棧頂取出2個操作數(shù)，然后進(jìn)行計算，把計算完的結(jié)果壓入操作數(shù)棧，繼續(xù)比較。

3.棧在括號匹配中的應(yīng)用（比如：{}{()}）

用棧保存為匹配的左括號，從左到右一次掃描字符串，當(dāng)掃描到左括號時，則將其壓入棧中；當(dāng)掃描到右括號時，從棧頂取出一個左括號，如果能匹配上，則繼續(xù)掃描剩下的字符串。如果掃描過程中，遇到不能配對的右括號，或者棧中沒有數(shù)據(jù)，則說明為非法格式。
當(dāng)所有的括號都掃描完成之后，如果棧為空，則說明字符串為合法格式；否則，說明未匹配的左括號為非法格式。

4.如何實(shí)現(xiàn)瀏覽器的前進(jìn)后退功能？

我們使用兩個棧X和Y，我們把首次瀏覽的頁面依次壓如棧X，當(dāng)點(diǎn)擊后退按鈕時，再依次從棧X中出棧，并將出棧的數(shù)據(jù)一次放入Y棧。當(dāng)點(diǎn)擊前進(jìn)按鈕時，我們依次從棧Y中取出數(shù)據(jù)，放入棧X中。當(dāng)棧X中沒有數(shù)據(jù)時，說明沒有頁面可以繼續(xù)后退瀏覽了。當(dāng)Y棧沒有數(shù)據(jù)，那就說明沒有頁面可以點(diǎn)擊前進(jìn)瀏覽了。

JVM 內(nèi)存管理中有個“堆棧”的概念。棧內(nèi)存用來存儲局部變量和方法調(diào)用，堆內(nèi)存用來存儲 Java 中的對象。那 JVM 里面的“棧”跟數(shù)據(jù)結(jié)構(gòu)中的“棧”是不是一回事呢？

內(nèi)存中的堆棧和數(shù)據(jù)結(jié)構(gòu)堆棧不是一個概念，可以說內(nèi)存中的堆棧是真實(shí)存在的物理區(qū)，數(shù)據(jù)結(jié)構(gòu)中的堆棧是抽象的數(shù)據(jù)存儲結(jié)構(gòu)。
內(nèi)存空間在邏輯上分為三部分：代碼區(qū)、靜態(tài)數(shù)據(jù)區(qū)和動態(tài)數(shù)據(jù)區(qū)，動態(tài)數(shù)據(jù)區(qū)又分為棧區(qū)和堆區(qū)。

• 代碼區(qū)：存儲方法體的二進(jìn)制代碼。高級調(diào)度（作業(yè)調(diào)度）、中級調(diào)度（內(nèi)存調(diào)度）、低級調(diào)度（進(jìn)程調(diào)度）控制代碼區(qū)執(zhí)行代碼的切換。
• 靜態(tài)數(shù)據(jù)區(qū)：存儲全局變量、靜態(tài)變量、常量，常量包括final修飾的常量和String常量。系統(tǒng)自動分配和回收。
• 棧區(qū)：存儲運(yùn)行方法的形參、局部變量、返回值。由系統(tǒng)自動分配和回收。
• 堆區(qū)：new一個對象的引用或地址存儲在棧區(qū)，指向該對象存儲在堆區(qū)中的真實(shí)數(shù)據(jù)。

leetcode上關(guān)于棧的題目：20,155,232,844,224,682,49

隊列

一、什么是隊列？

1.先進(jìn)者先出，這就是典型的“隊列”結(jié)構(gòu)。
2.支持兩個操作：入隊enqueue()，放一個數(shù)據(jù)到隊尾；出隊dequeue()，從隊頭取一個元素。
3.所以，和棧一樣，隊列也是一種操作受限的線性表。

二、如何實(shí)現(xiàn)隊列？

1.隊列API

public interface Queue {
public void enqueue(T item); //入隊
public T dequeue(); //出隊
public int size(); //統(tǒng)計元素數(shù)量
public boolean isNull(); //是否為空
}

2.實(shí)現(xiàn)

** 2.1 數(shù)組**

// 用數(shù)組實(shí)現(xiàn)的隊列 public class ArrayQueue {// 數(shù)組：items，數(shù)組大小：nprivate String[] items;private int n = 0;// head表示隊頭下標(biāo)，tail表示隊尾下標(biāo)private int head = 0;private int tail = 0;// 申請一個大小為capacity的數(shù)組public ArrayQueue(int capacity) {items = new String[capacity];n = capacity;}// 入隊public boolean enqueue(String item) {// 如果tail == n 表示隊列已經(jīng)滿了if (tail == n) return false;items[tail] = item;++tail;return true;}// 出隊public String dequeue() {// 如果head == tail 表示隊列為空if (head == tail) return null;// 為了讓其他語言的同學(xué)看的更加明確，把--操作放到單獨(dú)一行來寫了String ret = items[head];++head;return ret;}// 入隊操作，將item放入隊尾,如圖public boolean enqueue(String item) {// tail == n表示隊列末尾沒有空間了if (tail == n) {// tail ==n && head==0，表示整個隊列都占滿了if (head == 0) return false;// 數(shù)據(jù)搬移for (int i = head; i < tail; ++i) {items[i-head] = items[i];}// 搬移完之后重新更新head和tailtail -= head;head = 0;}items[tail] = item;++tail;return true;} }

2.2 循環(huán)鏈表思想
關(guān)鍵隊空條件 head == tail
隊滿判斷條件 (tail+1)%n=head

public class CircularQueue {// 數(shù)組：items，數(shù)組大小：nprivate String[] items;private int n = 0;// head表示隊頭下標(biāo)，tail表示隊尾下標(biāo)private int head = 0;private int tail = 0;// 申請一個大小為capacity的數(shù)組public CircularQueue(int capacity) {items = new String[capacity];n = capacity;}// 入隊public boolean enqueue(String item) {// 隊列滿了if ((tail + 1) % n == head) return false;items[tail] = item;tail = (tail + 1) % n;return true;}// 出隊public String dequeue() {// 如果head == tail 表示隊列為空if (head == tail) return null;String ret = items[head];head = (head + 1) % n;return ret;} }

2.3 鏈表實(shí)現(xiàn)

public class LinkedQueue { //定義一個節(jié)點(diǎn)類 private class Node{ String value; Node next; } //記錄隊列元素個數(shù) private int size = 0; //head指向隊頭結(jié)點(diǎn)，tail指向隊尾節(jié)點(diǎn) private Node head; private Node tail; //申請一個隊列 public LinkedQueue(){} //入隊 public boolean enqueue(String item){ Node newNode = new Node(); newNode.value = item; if (size == 0) head = newNode; else tail.next = newNode; tail = newNode; size++; return true; } //出隊 public String dequeue(){ String res = null; if(size == 0) return res; if(size == 1) tail = null; res = head.value; head = head.next; size--; return res; }

三、隊列有哪些常見的應(yīng)用？

1.阻塞隊列

1）在隊列的基礎(chǔ)上增加阻塞操作，就成了阻塞隊列。
2）阻塞隊列就是在隊列為空的時候，從隊頭取數(shù)據(jù)會被阻塞，因?yàn)榇藭r還沒有數(shù)據(jù)可取，直到隊列中有了數(shù)據(jù)才能返回；如果隊列已經(jīng)滿了，那么插入數(shù)據(jù)的操作就會被阻塞，直到隊列中有空閑位置后再插入數(shù)據(jù)，然后在返回。
3）從上面的定義可以看出這就是一個“生產(chǎn)者-消費(fèi)者模型”。這種基于阻塞隊列實(shí)現(xiàn)的“生產(chǎn)者-消費(fèi)者模型”可以有效地協(xié)調(diào)生產(chǎn)和消費(fèi)的速度。當(dāng)“生產(chǎn)者”生產(chǎn)數(shù)據(jù)的速度過快，“消費(fèi)者”來不及消費(fèi)時，存儲數(shù)據(jù)的隊列很快就會滿了，這時生產(chǎn)者就阻塞等待，直到“消費(fèi)者”消費(fèi)了數(shù)據(jù)，“生產(chǎn)者”才會被喚醒繼續(xù)生產(chǎn)。不僅如此，基于阻塞隊列，我們還可以通過協(xié)調(diào)“生產(chǎn)者”和“消費(fèi)者”的個數(shù)，來提高數(shù)據(jù)處理效率，比如配置幾個消費(fèi)者，來應(yīng)對一個生產(chǎn)者。

2.并發(fā)隊列

1）在多線程的情況下，會有多個線程同時操作隊列，這時就會存在線程安全問題。能夠有效解決線程安全問題的隊列就稱為并發(fā)隊列。
2）并發(fā)隊列簡單的實(shí)現(xiàn)就是在enqueue()、dequeue()方法上加鎖，但是鎖粒度大并發(fā)度會比較低，同一時刻僅允許一個存或取操作。
3）實(shí)際上，基于數(shù)組的循環(huán)隊列利用CAS原子操作，可以實(shí)現(xiàn)非常高效的并發(fā)隊列。這也是循環(huán)隊列比鏈?zhǔn)疥犃袘?yīng)用更加廣泛的原因。
3.線程池資源枯竭是的處理
在資源有限的場景，當(dāng)沒有空閑資源時，基本上都可以通過“隊列”這種數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)請求排隊。

[劍指offer][JAVA]面試題第[09]題[用兩個棧實(shí)現(xiàn)隊列][LinkedList]

主要整理參考作者：姜威
筆記整理來源： 王爭 數(shù)據(jù)結(jié)構(gòu)與算法之美

總結(jié)

以上是生活随笔為你收集整理的【数据结构与算法】栈与队列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。