Queue using two stacks, by Apple
Today's Daily Coding Problem:
This is a very common technical interview question, including its variations, such as:
This problem was asked by Apple.
Implement a queue using two stacks. Recall that a queue is a FIFO (first-in, first-out) data structure with the following methods:
enqueue, which inserts an element into the queue, and dequeue, which removes it.This is a very common technical interview question, including its variations, such as:
- Implement a stack using two queues
- Optimize for enqueue/push operation (O(1)-time)
- Optimize for dequeue/pop operation (O(1)-time)
My implementation below optimizes it for the enqueue operation (in O(1)-time), while the dequeue will suffer a little bit on time (O(n)-time).
The idea is as follows:
- On the enqueue operation, push to stack 1
- On the dequeue, pop from stack 1 pushing to stack 2. Save the last element, which you'll return later. Then push all the elements back to stack 1
That's it! Code is here (GitHub): https://github.com/BorisVasilenko/dailycodingproblem/blob/master/DailyCodingProblem11062018.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Collections;
namespace DailyCodingProblem
{
class DailyCodingProblem11062018
{
private Stack[] stack = null;
public DailyCodingProblem11062018()
{
stack = new Stack[2];
stack[0] = new Stack();
stack[1] = new Stack();
}
public void Enqueue(string item)
{
stack[0].Push(item);
}
public string Dequeue()
{
if (stack[0].Count == 0) return null;
//Get, swap, remove
string retVal = SwapStacksReturnLast(stack[0], stack[1], true);
//Swap back, don't remove, ignore the result
SwapStacksReturnLast(stack[1], stack[0], false);
return retVal;
}
private string SwapStacksReturnLast(Stack from, Stack to, bool remove)
{
string retVal = "";
while (from.Count > 0)
{
retVal = (string)from.Pop();
if (!remove || from.Count > 0)
to.Push(retVal);
}
return retVal;
}
}
}
LeetCode also has a variant of this problem https://leetcode.com/problems/implement-queue-using-stacks
ReplyDeleteThe second invocation of SwapStacksReturnLast is not really necessary:
class MyQueue {
private:
stack head;
stack tail;
void rebalance() {
if (tail.empty()) {
while (!head.empty()) {
tail.push(head.top());
head.pop();
}
}
}
public:
/** Push element x to the back of queue. */
void push(int x) {
head.push(x);
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
rebalance();
int value = tail.top();
tail.pop();
return value;
}
/** Get the front element. */
int peek() {
rebalance();
return tail.top();
}
/** Returns whether the queue is empty. */
bool empty() {
return head.empty() && tail.empty();
}
};
We need to maintain an invariant that second stack always contains elements that can be popped in the "queue" order. To do this, we always push into the first stack, but when we pop, we check if second stack is not empty and if so pop the element out of it. In order to maintain the invariant, we just need to push all the elements from the first stack into the second stack when second stack becomes empty, since this transfer reverses the order of pushes and makes it "queue"-like.
Cheers,
Taras