【栈和队列】leetcode232——用栈实现队列

编号232： 用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列的支持的所有操作（push、pop、peek、empty）：

• push(x) -- 将一个元素放入队列的尾部。
• pop() -- 从队列首部移除元素。
• peek() -- 返回队列首部的元素。
• empty() -- 返回队列是否为空。

示例:

MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek();  // 返回 1
queue.pop();   // 返回 1
queue.empty(); // 返回 false

说明:

• 你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
• 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
• 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。

思路

这是一道模拟题，不涉及到具体算法，考察的就是对栈和队列的掌握程度。使用栈来模式队列的行为，如果仅仅用一个栈，是一定不行的，所以需要两个栈「一个输入栈，一个输出栈」，这里要注意输入栈和输出栈的关系。

在push数据的时候，只要数据放进输入栈就好，「但在pop的时候，操作就复杂一些，输出栈如果为空，就把输入栈中数据全部导入进来（注意是全部导入，再从出栈弹出数据」，如果输出栈不为空，则直接从出栈弹出数据就可以了。

最后如何判断队列为空呢？「如果进栈和出栈都为空的话，说明模拟的队列为空了。」

具体代码如下：

//MyQueue need a stackIn and a stackOut
type MyQueue struct {
	stackIn  []int
	stackOut []int
}

/** Initialize your data structure here. */
func Constructor() MyQueue {
	return MyQueue{}
}

/** Push element x to the back of queue. */
func (this *MyQueue) Push(x int) {
	//入队 只需要把数据存入stackIn栈即可
	this.stackIn = append(this.stackIn, x)
}

/** Removes the element from in front of queue and returns that element. */
func (this *MyQueue) Pop() int {
	//出队  则需要先判断stackOut栈中是否为空  如果不为空则直接从stackOut出栈
	//如果为空 则需要先将stackIn栈中的数据全部导入到stackOut中  再从stackOut出栈
	if len(this.stackOut) == 0 {
		for len(this.stackIn) != 0 {
			val := this.stackIn[len(this.stackIn)-1]
			//从stackIn中删除val
			this.stackIn = this.stackIn[:len(this.stackIn)-1]
			//导入stackOut栈
			this.stackOut = append(this.stackOut, val)
		}
	}

	//获取stackOut栈顶元素
	val := this.stackOut[len(this.stackOut)-1]
	//移除stackOut栈顶元素
	this.stackOut = this.stackOut[:len(this.stackOut)-1]
	//返和出队的第一个元素
	return val
}

/** Get the front element. */
func (this *MyQueue) Peek() int {
	//复用Pop方法
	val := this.Pop()
	//再将val还回去  即进入stackOut栈中
	this.stackOut = append(this.stackOut, val)

	return val
}

/** Returns whether the queue is empty. */
func (this *MyQueue) Empty() bool {
	//判断队列为空 即判断stackIn和stackOut两个栈是否都为空go
	return len(this.stackIn) == 0 && len(this.stackOut) == 0
}

【栈和队列】leetcode232——用栈实现队列

原文：https://www.cnblogs.com/zmk-c/p/14440591.html