The challenge
Implement a FIFO queue using two LIFO stacks. Return each peek or pop result.
Operations are push:value, pop, peek. Empty queries return null.
Example
push:1, push:2, peek, pop, push:3, pop, pop → [1, 1, 2, 3].
Use the walkthrough below to inspect the input and each state change.
See Queue Using Two Stacks, step by step
Inspect each push, pop, and recorded answer. Entries such as 2: 5 mean index: value.
Zero-based input · top labeled explicitlyLIFO
- Current input index
- —
- Main stack size
- 0
Step 01 / 12
Start with an empty stack
Read the input in order. The stack keeps only the state needed to resolve the next item.
Answer so far
Not recorded yet
- Main stack · bottom → top
- Empty
- Auxiliary stack · bottom → top
- Empty
View exact input and state
Input: ["push:1","push:2","peek","pop","push:3","pop","pop"]
Main stack: []. Auxiliary stack · bottom → top: [].
Put it into code
Transfer incoming to outgoing only when outgoing is empty.
Indices are zero-based. C++ uses C++17 or later.
class MyQueue:
def __init__(self):
self.incoming, self.outgoing = [], []
def _transfer(self):
if not self.outgoing:
while self.incoming:
self.outgoing.append(self.incoming.pop())
def push(self, value):
self.incoming.append(value)
def peek(self):
self._transfer()
return self.outgoing[-1] if self.outgoing else None
def pop(self):
self._transfer()
return self.outgoing.pop() if self.outgoing else None
def solve(operations):
queue, output = MyQueue(), []
for token in operations:
op, _, raw = token.partition(':')
if op == 'push': queue.push(int(raw))
else: output.append(queue.pop() if op == 'pop' else queue.peek())
return output
#include <algorithm>
#include <optional>
#include <utility>
#include <string>
#include <vector>
using namespace std;
class MyQueue {
vector<int> incoming, outgoing;
void transfer() {
if (outgoing.empty()) while (!incoming.empty()) {
outgoing.push_back(incoming.back());
incoming.pop_back();
}
}
public:
void push(int value) { incoming.push_back(value); }
optional<int> peek() {
transfer();
return outgoing.empty() ? nullopt : optional<int>(outgoing.back());
}
optional<int> pop() {
auto value = peek();
if (!outgoing.empty()) outgoing.pop_back();
return value;
}
};
vector<optional<int>> solve(const vector<string>& operations) {
MyQueue queue;
vector<optional<int>> output;
for (const auto& op : operations) {
if (op.rfind("push:", 0) == 0) queue.push(stoi(op.substr(5)));
else output.push_back(op == "pop" ? queue.pop() : queue.peek());
}
return output;
}