Go實(shí)現(xiàn)棧與隊(duì)列基本操作 _生活百科

一前言
二實(shí)現(xiàn)棧與隊(duì)列基本操作

2.1 棧基本操作
2.2 隊(duì)列基本操作

三用棧實(shí)現(xiàn)隊(duì)列

3.1 理論
3.2 算法題
3.3 思路
3.4 代碼部分

【Go實(shí)現(xiàn)棧與隊(duì)列基本操作】四用隊(duì)列實(shí)現(xiàn)棧

4.1 理論
4.2 算法題
4.3 思路
4.4 使用兩個(gè)隊(duì)列實(shí)現(xiàn)
4.5 優(yōu)化
4.6 使用一個(gè)隊(duì)列實(shí)現(xiàn)

一前言go語言中，并沒有棧與隊(duì)列相關(guān)的數(shù)據(jù)結(jié)構(gòu)，但是我們可以借助切片來實(shí)現(xiàn)棧與隊(duì)列的操作；接下來我們一起實(shí)現(xiàn)棧與隊(duì)列基本操作，并且還會(huì)實(shí)現(xiàn)用棧實(shí)現(xiàn)隊(duì)列，用隊(duì)列實(shí)現(xiàn)棧的操作。
二實(shí)現(xiàn)棧與隊(duì)列基本操作2.1 棧基本操作go語言實(shí)現(xiàn)棧和隊(duì)列主要用到append 和切片(用內(nèi)置數(shù)組類型進(jìn)行操作)
//創(chuàng)建棧stack := make([]int, 0)//push壓入棧stack = append(stack, 10)//pop彈出v := stack[len(stack)-1]stack = stack[:len(stack)-1]//檢查棧空len(stack) == 02.2 隊(duì)列基本操作//創(chuàng)建隊(duì)列queue := make([]int, 0)//enqueue入隊(duì)queue = append(queue, 10)//dequeue出隊(duì)v := queue[0]queue = queue[1:]//檢查隊(duì)列為空len(queue) == 0三用棧實(shí)現(xiàn)隊(duì)列3.1 理論使用棧來模式隊(duì)列的行為，如果僅僅用一個(gè)棧，是一定不行的，所以需要兩個(gè)棧一個(gè)輸入棧，一個(gè)輸出棧，這里要注意輸入棧和輸出棧的關(guān)系。
下面動(dòng)畫模擬以下隊(duì)列的執(zhí)行過程如下：
執(zhí)行語句：
queue.push(1);queue.push(2);queue.pop(); 注意此時(shí)的輸出棧的操作queue.push(3);queue.push(4);queue.pop();queue.pop();注意此時(shí)的輸出棧的操作queue.pop();queue.empty();在push數(shù)據(jù)的時(shí)候，只要數(shù)據(jù)放進(jìn)輸入棧就好，但在pop的時(shí)候，操作就復(fù)雜一些，輸出棧如果為空，就把進(jìn)棧數(shù)據(jù)全部導(dǎo)入進(jìn)來（注意是全部導(dǎo)入），再從出棧彈出數(shù)據(jù)，如果輸出棧不為空，則直接從出棧彈出數(shù)據(jù)就可以了。
最后如何判斷隊(duì)列為空呢？如果進(jìn)棧和出棧都為空的話，說明模擬的隊(duì)列為空了。
3.2 算法題接下來看一下LeetCode原題
232. 用棧實(shí)現(xiàn)隊(duì)列
請你僅使用兩個(gè)棧實(shí)現(xiàn)先入先出隊(duì)列。隊(duì)列應(yīng)當(dāng)支持一般隊(duì)列支持的所有操作（push、pop、peek、empty）：
實(shí)現(xiàn) MyQueue 類：
void push(int x) 將元素 x 推到隊(duì)列的末尾int pop() 從隊(duì)列的開頭移除并返回元素int peek() 返回隊(duì)列開頭的元素boolean empty() 如果隊(duì)列為空，返回 true ；否則，返回 false說明：
你只能使用標(biāo)準(zhǔn)的棧操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。你所使用的語言也許不支持棧。你可以使用 list 或者 deque（雙端隊(duì)列）來模擬一個(gè)棧，只要是標(biāo)準(zhǔn)的棧操作即可。
3.3 思路解決這個(gè)問題，需要一個(gè)輸出棧和輸入棧
先將數(shù)據(jù)放到輸入棧，再把數(shù)據(jù)從輸入棧放到輸出棧，此時(shí)輸出棧輸出數(shù)據(jù)的順序就和隊(duì)列一樣了，先入先出
3.4 代碼部分type MyQueue struct { stackIn []int // 用來保存Push數(shù)據(jù) stackOut []int // 用來保存Pop數(shù)據(jù)}// 棧構(gòu)造器func Constructor() MyQueue { return MyQueue{stackIn: make([]int, 0),stackOut: make([]int, 0), }}func (this *MyQueue) Push(x int) { // 判斷stackOut中是否有元素，有的話全部放到stackIn for len(this.stackOut) != 0 {val := this.stackOut[len(this.stackOut)-1]this.stackOut = this.stackOut[:len(this.stackOut)-1]this.stackIn = append(this.stackIn, val) } // 將數(shù)據(jù)加進(jìn)stackIn this.stackIn = append(this.stackIn, x)}func (this *MyQueue) Pop() int { // 判斷stackIn中是否有元素，有的話全部放到stackOut for len(this.stackIn) != 0 {val := this.stackIn[len(this.stackIn)-1]this.stackIn = this.stackIn[:len(this.stackIn)-1]this.stackOut = append(this.stackOut, val) } // stackOut為零，說明沒有元素，return 0 if len(this.stackOut) == 0 {return 0 } // stackOut Pop 元素 res := this.stackOut[len(this.stackOut)-1] this.stackOut = this.stackOut[:len(this.stackOut)-1] return res}func (this *MyQueue) Peek() int { // 調(diào)用Pop()方法 val := this.Pop() // val為零，說明沒有元素，return 0 if val == 0 {return 0 } // Pop()方法刪除了val，這里加上 this.stackOut = append(this.stackOut, val) return val}func (this *MyQueue) Empty() bool { // 兩個(gè)棧都為空，說明為空，否則不為空 return len(this.stackOut) == 0 && len(this.stackIn) == 0}