题目
Implement the following operations of a queue using stacks.
- push(x) -- Push element x to the back of queue.
- pop() -- Removes the element from in front of queue.
- peek() -- Get the front element.
- empty() -- Return whether the queue is empty.
Notes:
- You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is empty operations are valid.
- Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
- You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).
解题思路
题目要求用栈实现队列，但是go语言没有实现栈，所以还要先实现栈，这里使用slice实现栈
栈是先进后出，队列是先进先出，所以使用两个栈，两次先进后出，就变成了先进先出
例如：
一列数1，2，3，4，5，先放入一个栈中再出栈的顺序为5，4，3，2，1，出栈后放入另一个队列再出栈的顺序就变为1，2，3，4，5
代码
type MyStack struct {
val []int
}
func ConstructorStack() MyStack {
return MyStack{[]int{}}
}
func (this *MyStack) Push(x int) {
this.val = append([]int{x}, this.val...)
}
func (this *MyStack) Pop() int {
tmp := this.val[0]
this.val = this.val[1:]
return tmp
}
func (this *MyStack) Peek() int {
return this.val[0]
}
func (this *MyStack) Size() int {
return len(this.val)
}
func (this *MyStack) Empty() bool {
if 0 == len(this.val) {
return true
}
return false
}
type MyQueue struct {
stack1 MyStack
stack2 MyStack
}
/** Initialize your data structure here. */
func Constructor() MyQueue {
var queue MyQueue
queue.stack1 = ConstructorStack()
queue.stack2 = ConstructorStack()
return queue
}
/** Push element x to the back of queue. */
func (this *MyQueue) Push(x int) {
this.stack1.Push(x)
}
/** Removes the element from in front of queue and returns that element. */
func (this *MyQueue) Pop() int {
if !this.stack2.Empty() {
return this.stack2.Pop()
} else {
for ;!this.stack1.Empty(); {
tmp := this.stack1.Pop()
this.stack2.Push(tmp)
}
return this.stack2.Pop()
}
}
/** Get the front element. */
func (this *MyQueue) Peek() int {
if !this.stack2.Empty() {
return this.stack2.Peek()
} else {
for ;!this.stack1.Empty(); {
tmp := this.stack1.Pop()
this.stack2.Push(tmp)
}
return this.stack2.Peek()
}
}
/** Returns whether the queue is empty. */
func (this *MyQueue) Empty() bool {
return this.stack1.Empty() && this.stack2.Empty()
}
/**
* Your MyQueue object will be instantiated and called as such:
* obj := Constructor();
* obj.Push(x);
* param_2 := obj.Pop();
* param_3 := obj.Peek();
* param_4 := obj.Empty();
*/
