class MyQueue {
private Stack<Integer> s1 = null;
private Stack<Integer> s2 = null;
/** Initialize your data structure here. */
public MyQueue() {
this.s1 = new Stack<>();
this.s2 = new Stack<>();
}
/** Push element x to the back of queue. */
public void push(int x) {
s1.push(x);
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
shift();
if(!s2.isEmpty()) {
return s2.pop();
}
throw new RuntimeException("队列中没有元素");
}
/** Get the front element. */
public int peek() {
shift();
if(!s2.isEmpty()) {
return s2.peek();
}
throw new RuntimeException("队列中没有元素");
}
/** Returns whether the queue is empty. */
public boolean empty() {
return s1.isEmpty() && s2.isEmpty();
}
//将s1中的全部谈进s2,但是要保证s2为空
public void shift() {
if (s2.isEmpty()) {
while(!s1.isEmpty()) {
s2.push(s1.pop());
}
}
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/
栈是一种 后进先出(last in - first out, LIFO)的数据结构,栈内元素从顶端压入(push),从顶端弹出(pop)
。一般我们用数组或者链表来实现栈,但是这里会介绍如何用队列来实现栈。队列是一种与栈相反的 先进先出(first in - first out, FIFO)
的数据结构,队列中元素只能从 后端(rear
)入队(push
),然后从 前端(front
)端出队(pop
)。为了满足栈的特性,我们需要维护两个队列 q1 和 q2。同时,我们用一个额外的变量来保存栈顶元素。
思路:画图帮助分析。
class MyStack {
private Queue<Integer> q;
/** Initialize your data structure here. */
public MyStack() {
q = new LinkedList<>();
}
/** Push element x onto stack. */
public void push(int x) {
q.offer(x);
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
if (!q.isEmpty()) {
shift();
return q.poll();
}
throw new RuntimeException("队列中没有元素");
}
/** Get the top element. */
public int top() {
if (!q.isEmpty()) {
shift();
int elem = q.poll();
q.offer(elem);
return elem;
}
throw new RuntimeException("队列中没有元素");
}
/** Returns whether the stack is empty. */
public boolean empty() {
return q.isEmpty();
}
public void shift() {
for (int i = 0; i < q.size() - 1; i++) {
q.offer(q.poll());
}
}
}
/**
* Your MyStack object will be instantiated and called as such:
* MyStack obj = new MyStack();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.top();
* boolean param_4 = obj.empty();
*/