Go实现栈与队列基本操作 _生活百科

一前言
二实现栈与队列基本操作

2.1 栈基本操作
2.2 队列基本操作

三用栈实现队列

3.1 理论
3.2 算法题
3.3 思路
3.4 代码部分

四用队列实现栈

4.1 理论
4.2 算法题
4.3 思路
4.4 使用两个队列实现
4.5 优化
4.6 使用一个队列实现

一前言go语言中，并没有栈与队列相关的数据结构，但是我们可以借助切片来实现栈与队列的操作；接下来我们一起实现栈与队列基本操作，并且还会实现用栈实现队列，用队列实现栈的操作。
二实现栈与队列基本操作2.1 栈基本操作go语言实现栈和队列主要用到append 和切片(用内置数组类型进行操作)
//创建栈stack := make([]int, 0)//push压入栈stack = append(stack, 10)//pop弹出v := stack[len(stack)-1]stack = stack[:len(stack)-1]//检查栈空len(stack) == 02.2 队列基本操作//创建队列queue := make([]int, 0)//enqueue入队queue = append(queue, 10)//dequeue出队v := queue[0]queue = queue[1:]//检查队列为空len(queue) == 0三用栈实现队列3.1 理论使用栈来模式队列的行为，如果仅仅用一个栈，是一定不行的，所以需要两个栈一个输入栈，一个输出栈，这里要注意输入栈和输出栈的关系。
下面动画模拟以下队列的执行过程如下：
执行语句：
queue.push(1);queue.push(2);queue.pop(); 注意此时的输出栈的操作queue.push(3);queue.push(4);queue.pop();queue.pop();注意此时的输出栈的操作queue.pop();queue.empty();在push数据的时候，只要数据放进输入栈就好，但在pop的时候，操作就复杂一些，输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入），再从出栈弹出数据，如果输出栈不为空，则直接从出栈弹出数据就可以了。
最后如何判断队列为空呢？如果进栈和出栈都为空的话，说明模拟的队列为空了。
3.2 算法题接下来看一下LeetCode原题
232. 用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾int pop() 从队列的开头移除并返回元素int peek() 返回队列开头的元素boolean empty() 如果队列为空，返回 true ；否则，返回 false说明：
你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
3.3 思路解决这个问题，需要一个输出栈和输入栈
先将数据放到输入栈，再把数据从输入栈放到输出栈，此时输出栈输出数据的顺序就和队列一样了，先入先出
3.4 代码部分type MyQueue struct { stackIn []int // 用来保存Push数据 stackOut []int // 用来保存Pop数据}// 栈构造器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) } // 将数据加进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 { // 调用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 { // 两个栈都为空，说明为空，否则不为空 return len(this.stackOut) == 0 && len(this.stackIn) == 0}