用队列实现栈

题目描述

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通队列的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

• void push(int x) 将元素 x 压入栈顶。
• int pop() 移除并返回栈顶元素。
• int top() 返回栈顶元素。
• boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

• 你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
• 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可

测试用例

输入

[“MyStack”, “push”, “push”, “top”, “pop”, “empty”]
[[], [1], [2], [], [], []]

输出

[null, null, null, 2, 2, false]

解释

MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

解题思路

• 两个队列都为空,栈才为空
• 入栈写入one,出栈弹出two
• one不为空,出栈先将one中的数据写入two

代码实现

type MyStack struct {
  one []int
  two []int
}

/** Initialize your data structure here. */
func Constructor() MyStack {
  return MyStack{
    one: make([]int, 0),
    two: make([]int, 0),
  }
}

/** Push element x onto stack. */
func (this *MyStack) Push(x int) {
  this.one = append(this.one, x)
}

/** Removes the element on top of the stack and returns that element. */
func (this *MyStack) Pop() int {
  if this.Empty() {
    return 0
  }
  this.fillTwo()
  data := this.two[len(this.two)-1]
  this.two = this.two[:len(this.two)-1]
  return data
}

/** Get the top element. */
func (this *MyStack) Top() int {
  if this.Empty() {
    return 0
  }
  this.fillTwo()
  return this.two[len(this.two)-1]
}

/** Returns whether the stack is empty. */
func (this *MyStack) Empty() bool {
  return len(this.one) == 0 && len(this.two) == 0
}

// fillTwo 将one栈的数据填充进two栈
//
// Author : go_developer@163.com<白茶清欢>
//
// Date : 6:20 下午 2021/2/10
func (this *MyStack) fillTwo() {
  if len(this.one) == 0 {
    return
  }
  for i := 0; i < len(this.one); i++ {
    this.two = append(this.two, this.one[i])
  }
  this.one = make([]int, 0)
}