以下完整代碼均可從這里獲取

棧

棧的基本概念

「后進先出、先進后出就是典型的棧結構」。棧可以理解成一種受了限制的線性表，插入和刪除都只能從一端進行

當某個數據集合只涉及在一端插入和刪除數據，并且滿足后進先出、先進后出的特性，就應該首選“棧”這種數據結構（瀏覽器的前進、后退功能）

棧的實現

棧主要有兩種操作，入棧和出棧，這里通過數組（順序棧）和鏈表（鏈式棧）兩種方式實現棧

順序棧

package arrayStackimport "fmt"type Item interface {}type ItemStack struct {Items []ItemN int }//init stack func (stack *ItemStack) Init() *ItemStack {stack.Items = []Item{}return stack }//push stack Item func (stack *ItemStack) Push(item Item) {if len(stack.Items) > stack.N {fmt.Println("棧已滿")return}stack.Items = append(stack.Items, item) }//pop Item from stack func (stack *ItemStack) Pop() Item {if len(stack.Items) == 0 {fmt.Println("棧已空")return nil}item := stack.Items[len(stack.Items) - 1]stack.Items = stack.Items[0:len(stack.Items) - 1]return item }

鏈式棧

package linkListStackimport "fmt"type Item interface {}type Node struct {Data ItemNext *Node }type Stack struct {headNode *Node }//push Stack item func (stack *Stack) Push(item Item) {newNode := &Node{Data: item}newNode.Next = stack.headNodestack.headNode = newNode }//pop Item from stack func (stack *Stack) Pop() Item {if stack.headNode == nil {fmt.Println("棧已空")return nil}item := stack.headNode.Datastack.headNode = stack.headNode.Nextreturn item }func (stack *Stack) Traverse() {if stack.headNode == nil {fmt.Println("棧已空")return}currentNode := stack.headNodefor currentNode != nil {fmt.Printf("%vt", currentNode.Data)currentNode = currentNode.Next} }

棧的應用場景

函數調用棧

? 操作系統給每個線程分配了一塊獨立的內存空間，這塊內存被組織成“棧”這種結構, 用來存儲函數調用時的臨時變量。每進入一個函數，就會將臨時變量作為一個棧幀入棧，當被調用函數執行完成，返回之后，將這個函數對應的棧幀出棧
來源：數據結構與算法之美
?

從這段代碼的執行過程中了解函數調用棧

int main() {int a = 1; int ret = 0;int res = 0;ret = add(3, 5);res = a + ret;printf("%d", res);reuturn 0; }int add(int x, int y) {int sum = 0;sum = x + y;return sum; }

main()函數調用了 add() 函數，獲取計算結果，并且與臨時變量 a 相加，最后打印 res 的值。程序在執行過程中，main函數中的變量會先后入棧，當執行到add()函數時，add()函數中的臨時變量也會先后入棧，結果如下：

「說明：內存中的堆棧和數據結構堆棧不是一個概念，內存中的堆棧是真實存在的物理區，數據結構中的堆棧是抽象的數據存儲結構」

棧在表達式求值中的應用

一個表達式包含兩個部分，數字和運算符。我們用兩個棧來實現表達式求值，一個棧用來存儲數字，一個棧用來存儲運算符

假設有這么一個表達式

1000+5*6-6

從左向右遍歷表達式，當遇到數字時，將數字放入到存儲數字的棧；如果遇到運算符，將存儲運算符棧的棧頂元素取出，進行優先級比較

如果比運算符棧頂元素優先級高，則將當前運算符壓入到存儲運算符的棧中；如果比運算符棧頂元素低或優先級一樣，則從存儲數字的棧中取出兩個元素，然后進行計算，將計算的結果放入到存儲數字的棧中。重復上邊的操作。過程如圖：

棧在括號匹配中的應用

這也是一個比較經典的題，就是給定一個括號串，驗證它是否完全匹配，如：

{{} 不匹配 [[{()}]] 匹配 ([{}] 不匹配

這個也可以用棧來解決。從左到右遍歷括號串，遇到未匹配的左括號則將其壓入棧中，遇到右括號時，從棧頂取出一個左括號，如果能匹配，則繼續遍歷后邊的括號，當遍歷完之后，棧為空了，說明這個括號串是匹配的，否則是不匹配的。具體實現如下：

package bracketMatchfunc BracketsMatch(str string) bool {brackets := map[rune]rune{')':'(', ']':'[', '}':'['}var stack []runefor _, char := range str {if char == '(' || char == '[' || char == '{' {stack = append(stack, char)} else if len(stack) > 0 && brackets[char] == stack[len(stack) - 1] {stack = stack[:len(stack) - 1]} else {return false}}return len(stack) == 0 }

隊列

隊列的基本概念

「先進先出就是典型的隊列結構」，隊列也可以理解成一種受了限制的線性表，插入只能從隊列尾部進行，刪除只能從隊列尾部進行。類比排隊取票

隊列的基本操作也只有兩個，入隊和出隊。隊列的應用確實是十分的廣泛，如消息隊列、阻塞隊列、循環隊列等

隊列的實現

還是通過兩種方式實現隊列，通過數組實現順序隊列，通過鏈表實現鏈式隊列

實現隊列需要兩個指針，一個指向隊列頭部，一個指向隊列尾部

順序隊列

package arrayQueueimport "fmt"type Item interface {}type Queue struct {Queue []ItemLength int }func (queue *Queue) Init() {queue.Queue = []Item{} }func (queue *Queue) Enqueue(data Item) {if len(queue.Queue) > queue.Length {fmt.Println("隊列滿了")return}queue.Queue = append(queue.Queue, data) }func (queue *Queue) Dequeue() Item {if len(queue.Queue) == 0 {fmt.Println("隊列空了")return nil}item := queue.Queue[0]queue.Queue = queue.Queue[1:]return item }

鏈式隊列

package linkListQueueimport "fmt"type Item interface {}type Node struct {Data ItemNext *Node }type Queue struct {headNode *Node }func (queue *Queue) Enqueue(data Item) {node := &Node{Data: data}if queue.headNode == nil {queue.headNode = node} else {currentNode := queue.headNodefor currentNode.Next != nil {currentNode = currentNode.Next}currentNode.Next = node} }func (queue *Queue) Dequeue() Item {if queue.headNode == nil {fmt.Println("隊列空了")return nil}item := queue.headNode.Dataqueue.headNode = queue.headNode.Nextreturn item }func (queue *Queue) Traverse() {if queue.headNode == nil {fmt.Println("隊列空的")return}currentNode := queue.headNodefor currentNode.Next != nil {fmt.Printf("%vt", currentNode.Data)currentNode = currentNode.Next}fmt.Printf("%vt", currentNode.Data) }

循環隊列

為什么會出現循環隊列？

看下邊這種情況，我有有一個長度是5的隊列，目前隊列是滿的。假設現在我從隊頭取出3個元素之后，想再往隊列中放入數據，其實是放不進去的，此時就出現一個問題，隊列有空閑空間，但是卻無法向隊列中放入數據了

其中一個解決辦法就是，「數據搬移」。但是這樣的話，每次在出隊的時候就等于說刪除數組下標為0的元素，而且要將后邊所有的數據向前搬移，這樣就導致出隊的時間復雜度由原來的O(1)變成O(n)，這種方法顯然是不可取的

第二個辦法就是使用一個「循環隊列」，很明顯就是一個環，這簡直和單向循環鏈表一模一樣。具體什么樣，大家應該都十分的清楚，它的難點就在于判空和判滿

隊列為空時：tail == head 隊列為滿時：(tail+1)%n == head

哎，找規律問題，不行硬記住就可以了，直接看下邊如何實現

循環隊列的實現

package loopQueueimport "fmt"type Item interface {}const QueueSize = 5 type LoopQueue struct {Items [QueueSize]ItemHead intTail int }//init func (queue *LoopQueue) Init() {queue.Head = 0queue.Tail = 0 }//enqueue func (queue *LoopQueue) Enqueue(data Item) {if ((queue.Tail + 1) % QueueSize) == queue.Head {fmt.Println("隊列滿了")}queue.Items[queue.Tail] = dataqueue.Tail = (queue.Tail+1) % QueueSize }//dequeue func (queue *LoopQueue) Dequeue() Item {if queue.Head == queue.Tail {fmt.Println("隊列空了")return nil}item := queue.Items[queue.Head]queue.Head = (queue.Head + 1) % QueueSizereturn item }

隊列的應用場景

阻塞隊列和并發隊列

阻塞隊列

在實際應用中，隊列不會是無限長的，隊列一旦有長度限制，就會有滿的時候，當隊列滿了的時候，入隊操作就會被阻塞，因為沒有數據可取。而當隊列為空時，出隊是阻塞的，直到隊列中有數據可取

沒錯，平時經常用到的「生產者-消費者模型」就是這樣，通過隊列可以輕松實現一個生產者-消費者模型

基于阻塞隊列，還可以通過調整“生產者”和“消費者”的個數，來提高數據的處理效率

并發隊列

對于上邊的阻塞隊列，在多線程的情況下，就會存在多個線程同時操作隊列，這個時候就會存在線程安全問題（如果想了解底層原因，可以看我的這篇文章：進程管理之進程同步）

保證線程安全的隊列就稱之為并發隊列，最簡單的方式就是在入隊和出隊的時候加鎖。關于鎖，也可以看我這里的系列文章：線程鎖系列

參考資料：

• 數據結構與算法之美
• 從零學習數據結構

總結

以上是生活随笔為你收集整理的假设有搅乱顺序的一群儿童成一个队列_数据结构与算法系列之栈amp;队列（GO）...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。