Q:用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。
T:
入队:将元素进栈A
出队:判断栈B是否为空,如果为空,则将栈A中所有元素pop,并push进栈B,栈B出栈;如果不为空,栈B直接出栈。
A:
void push(int node) {
stack1.push(node);
}
int pop() {
int temp, temp1, temp2;
while (!stack1.empty()) {
temp = stack1.top();
stack1.pop();
stack2.push(temp);
}
if (stack2.empty()) {
return -1;
} else {
temp1 = stack2.top();
stack2.pop();
while (!stack2.empty()) {
temp2 = stack2.top();
stack2.pop();
stack1.push(temp2);
}
return temp1;
}
}
private:
stack<int> stack1;
stack<int> stack2;
Q:用队列实现栈
T:
解决⽅法简单粗暴,每次压入时都把队列前⾯的都取出来再加⼊队尾:
class MyStack {
Queue<Integer> queue;
/** Initialize your data structure here. */
public MyStack() {
queue = new LinkedList<>();
}
/** Push element x onto stack. */
public void push(int x) {
queue.add(x);
for(int i = 1; i < queue.size(); i++)
queue.add(queue.remove());
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
return queue.poll();
}
/** Get the top element. */
public int top() {
return queue.peek();
}
/** Returns whether the stack is empty. */
public boolean empty() {
return queue.size() == 0;
}
}
/**
* 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();
*/