两个栈实现队列
思路：
- stack1 用于存放 push 的元素
- pop 的时候分两种情况
- stack2 为空, 把stack1 的栈顶元素弹出, 然后压入 stack2, 最后调用 stack2.pop 方法弹出
- stack2 不为空, 直接调用 stack2.pop 方法弹出
Stack *stack1 = Stack new();
Stack *stack2 = Stack new();
// 入队列
void add(data) {
stack1.push(data);
}
// 出队列
void poll() {
if (stack1.empty() && stack2.empty()) return ;
// 队列2 有元素直接弹出
if (!stack2.empty()) {
stack2.pop();
return;
}
// 把队列1的元素都给队列2
while(!s1.empty()) {
data = s1.top();
stack2.push(data);
stack1.pop();
}
// 模拟出队列操作
stack2.pop();
}
}
两个队列实现栈
思路：
- 如果两个队列为空, 则 push 操作在任意一个queue中执行都行
- 如果有队列不为空, 则 push 操作在队列不为空的队列中执行
- pop 操作, 把有数据的队列除队尾的元素, 全部出队列压入另外一个不为空的队列中, 最后 pop 队尾元素
两个队列在操作过程中总保持其中一个队列为空
Queue *queue1 = Queue new();
Queue *queue2 = Queue new();
// 入栈
void push(data) {
// 判断两个队列是否同时为空
if (queue1.empty() && queue2.empty) {
queue1.add(data);
return;
}
if (queue1.size() > 0) {
queue1.add(data);
} else {
queue2.add(data);
}
// 出栈
void pop() {
if (queue1.empty() && queue2.empty()) return;
if (!queue1.empty()) {
while(queue1.size() > 0) {
result = queue1.poll();
if(queue1.size() != 0) {
queue2.add(result);
}
}
} else {
while(queue2.size() > 0) {
result = queue2.poll();
if (queue2.size() != 0) {
queue1.add(result);
}
}
}
}
