Suppose we have two stacks and no other temporary variable.
Is to possible to "construct" a queue data structure using only the two stacks?
21 Answers
Keep 2 stacks, let's call them inbox and outbox.
Enqueue:
- Push the new element onto
inbox
Dequeue:
If
outboxis empty, refill it by popping each element frominboxand pushing it ontooutboxPop and return the top element from
outbox
Using this method, each element will be in each stack exactly once - meaning each element will be pushed twice and popped twice, giving amortized constant time operations.
Here's an implementation in Java:
public class Queue<E>
{
private Stack<E> inbox = new Stack<E>();
private Stack<E> outbox = new Stack<E>();
public void queue(E item) {
inbox.push(item);
}
public E dequeue() {
if (outbox.isEmpty()) {
while (!inbox.isEmpty()) {
outbox.push(inbox.pop());
}
}
return outbox.pop();
}
}
You can even simulate a queue using only one stack. The second (temporary) stack can be simulated by the call stack of recursive calls to the insert method.
The principle stays the same when inserting a new element into the queue:
- You need to transfer elements from one stack to another temporary stack, to reverse their order.
- Then push the new element to be inserted, onto the temporary stack
- Then transfer the elements back to the original stack
- The new element will be on the bottom of the stack, and the oldest element is on top (first to be popped)
A Queue class using only one Stack, would be as follows:
public class SimulatedQueue<E> {
private java.util.Stack<E> stack = new java.util.Stack<E>();
public void insert(E elem) {
if (!stack.empty()) {
E topElem = stack.pop();
insert(elem);
stack.push(topElem);
}
else
stack.push(elem);
}
public E remove() {
return stack.pop();
}
}
The time complexities would be worse, though. A good queue implementation does everything in constant time.
Edit
Not sure why my answer has been downvoted here. If we program, we care about time complexity, and using two standard stacks to make a queue is inefficient. It's a very valid and relevant point. If someone else feels the need to downvote this more, I would be interested to know why.
A little more detail: on why using two stacks is worse than just a queue: if you use two stacks, and someone calls dequeue while the outbox is empty, you need linear time to get to the bottom of the inbox (as you can see in Dave's code).
You can implement a queue as a singly-linked list (each element points to the next-inserted element), keeping an extra pointer to the last-inserted element for pushes (or making it a cyclic list). Implementing queue and dequeue on this data structure is very easy to do in constant time. That's worst-case constant time, not amortized. And, as the comments seem to ask for this clarification, worst-case constant time is strictly better than amortized constant time.
Implement the following operations of a queue using stacks.
push(x) -- Push element x to the back of queue.
pop() -- Removes the element from in front of queue.
peek() -- Get the front element.
empty() -- Return whether the queue is empty.
class MyQueue {
Stack<Integer> input;
Stack<Integer> output;
/** Initialize your data structure here. */
public MyQueue() {
input = new Stack<Integer>();
output = new Stack<Integer>();
}
/** Push element x to the back of queue. */
public void push(int x) {
input.push(x);
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
peek();
return output.pop();
}
/** Get the front element. */
public int peek() {
if(output.isEmpty()) {
while(!input.isEmpty()) {
output.push(input.pop());
}
}
return output.peek();
}
/** Returns whether the queue is empty. */
public boolean empty() {
return input.isEmpty() && output.isEmpty();
}
}
You'll have to pop everything off the first stack to get the bottom element. Then put them all back onto the second stack for every "dequeue" operation.
An implementation of a queue using two stacks in Swift:
struct Stack<Element> {
var items = [Element]()
var count : Int {
return items.count
}
mutating func push(_ item: Element) {
items.append(item)
}
mutating func pop() -> Element? {
return items.removeLast()
}
func peek() -> Element? {
return items.last
}
}
struct Queue<Element> {
var inStack = Stack<Element>()
var outStack = Stack<Element>()
mutating func enqueue(_ item: Element) {
inStack.push(item)
}
mutating func dequeue() -> Element? {
fillOutStack()
return outStack.pop()
}
mutating func peek() -> Element? {
fillOutStack()
return outStack.peek()
}
private mutating func fillOutStack() {
if outStack.count == 0 {
while inStack.count != 0 {
outStack.push(inStack.pop()!)
}
}
}
}
While you will get a lot of posts related to implementing a queue with two stacks : 1. Either by making the enQueue process a lot more costly 2. Or by making the deQueue process a lot more costly
https://www.geeksforgeeks.org/queue-using-stacks/
One important way I found out from the above post was constructing queue with only stack data structure and the recursion call stack.
While one can argue that literally this is still using two stacks, but then ideally this is using only one stack data structure.
Below is the explanation of the problem:
Declare a single stack for enQueuing and deQueing the data and push the data into the stack.
while deQueueing have a base condition where the element of the stack is poped when the size of the stack is 1. This will ensure that there is no stack overflow during the deQueue recursion.
While deQueueing first pop the data from the top of the stack. Ideally this element will be the element which is present at the top of the stack. Now once this is done, recursively call the deQueue function and then push the element popped above back into the stack.
The code will look like below:
if (s1.isEmpty())
System.out.println("The Queue is empty");
else if (s1.size() == 1)
return s1.pop();
else {
int x = s1.pop();
int result = deQueue();
s1.push(x);
return result;
This way you can create a queue using a single stack data structure and the recursion call stack.
Below is the solution in javascript language using ES6 syntax.
Stack.js
//stack using array
class Stack {
constructor() {
this.data = [];
}
push(data) {
this.data.push(data);
}
pop() {
return this.data.pop();
}
peek() {
return this.data[this.data.length - 1];
}
size(){
return this.data.length;
}
}
export { Stack };
QueueUsingTwoStacks.js
import { Stack } from "./Stack";
class QueueUsingTwoStacks {
constructor() {
this.stack1 = new Stack();
this.stack2 = new Stack();
}
enqueue(data) {
this.stack1.push(data);
}
dequeue() {
//if both stacks are empty, return undefined
if (this.stack1.size() === 0 && this.stack2.size() === 0)
return undefined;
//if stack2 is empty, pop all elements from stack1 to stack2 till stack1 is empty
if (this.stack2.size() === 0) {
while (this.stack1.size() !== 0) {
this.stack2.push(this.stack1.pop());
}
}
//pop and return the element from stack 2
return this.stack2.pop();
}
}
export { QueueUsingTwoStacks };
Below is the usage:
index.js
import { StackUsingTwoQueues } from './StackUsingTwoQueues';
let que = new QueueUsingTwoStacks();
que.enqueue("A");
que.enqueue("B");
que.enqueue("C");
console.log(que.dequeue()); //output: "A"
With O(1) dequeue(), which is same as pythonquick's answer:
// time: O(n), space: O(n)
enqueue(x):
if stack.isEmpty():
stack.push(x)
return
temp = stack.pop()
enqueue(x)
stack.push(temp)
// time: O(1)
x dequeue():
return stack.pop()
With O(1) enqueue() (this is not mentioned in this post so this answer), which also uses backtracking to bubble up and return the bottommost item.
// O(1)
enqueue(x):
stack.push(x)
// time: O(n), space: O(n)
x dequeue():
temp = stack.pop()
if stack.isEmpty():
x = temp
else:
x = dequeue()
stack.push(temp)
return x
Obviously, it's a good coding exercise as it inefficient but elegant nevertheless.
**Easy JS solution **
- Note: I took ideas from other people comment
/*
enQueue(q, x)
1) Push x to stack1 (assuming size of stacks is unlimited).
deQueue(q)
1) If both stacks are empty then error.
2) If stack2 is empty
While stack1 is not empty, push everything from stack1 to stack2.
3) Pop the element from stack2 and return it.
*/
class myQueue {
constructor() {
this.stack1 = [];
this.stack2 = [];
}
push(item) {
this.stack1.push(item)
}
remove() {
if (this.stack1.length == 0 && this.stack2.length == 0) {
return "Stack are empty"
}
if (this.stack2.length == 0) {
while (this.stack1.length != 0) {
this.stack2.push(this.stack1.pop())
}
}
return this.stack2.pop()
}
peek() {
if (this.stack2.length == 0 && this.stack1.length == 0) {
return 'Empty list'
}
if (this.stack2.length == 0) {
while (this.stack1.length != 0) {
this.stack2.push(this.stack1.pop())
}
}
return this.stack2[0]
}
isEmpty() {
return this.stack2.length === 0 && this.stack1.length === 0;
}
}
const q = new myQueue();
q.push(1);
q.push(2);
q.push(3);
q.remove()
console.log(q)My Solution with PHP
<?php
$_fp = fopen("php://stdin", "r");
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
$queue = array();
$count = 0;
while($line = fgets($_fp)) {
if($count == 0) {
$noOfElement = $line;
$count++;
continue;
}
$action = explode(" ",$line);
$case = $action[0];
switch($case) {
case 1:
$enqueueValue = $action[1];
array_push($queue, $enqueueValue);
break;
case 2:
array_shift($queue);
break;
case 3:
$show = reset($queue);
print_r($show);
break;
default:
break;
}
}
?>
public class QueueUsingStacks<T>
{
private LinkedListStack<T> stack1;
private LinkedListStack<T> stack2;
public QueueUsingStacks()
{
stack1=new LinkedListStack<T>();
stack2 = new LinkedListStack<T>();
}
public void Copy(LinkedListStack<T> source,LinkedListStack<T> dest )
{
while(source.Head!=null)
{
dest.Push(source.Head.Data);
source.Head = source.Head.Next;
}
}
public void Enqueue(T entry)
{
stack1.Push(entry);
}
public T Dequeue()
{
T obj;
if (stack2 != null)
{
Copy(stack1, stack2);
obj = stack2.Pop();
Copy(stack2, stack1);
}
else
{
throw new Exception("Stack is empty");
}
return obj;
}
public void Display()
{
stack1.Display();
}
}
For every enqueue operation, we add to the top of the stack1. For every dequeue, we empty the content's of stack1 into stack2, and remove the element at top of the stack.Time complexity is O(n) for dequeue, as we have to copy the stack1 to stack2. time complexity of enqueue is the same as a regular stack
here is my solution in Java using linkedlist.
class queue<T>{
static class Node<T>{
private T data;
private Node<T> next;
Node(T data){
this.data = data;
next = null;
}
}
Node firstTop;
Node secondTop;
void push(T data){
Node temp = new Node(data);
temp.next = firstTop;
firstTop = temp;
}
void pop(){
if(firstTop == null){
return;
}
Node temp = firstTop;
while(temp != null){
Node temp1 = new Node(temp.data);
temp1.next = secondTop;
secondTop = temp1;
temp = temp.next;
}
secondTop = secondTop.next;
firstTop = null;
while(secondTop != null){
Node temp3 = new Node(secondTop.data);
temp3.next = firstTop;
firstTop = temp3;
secondTop = secondTop.next;
}
}
}
Note: In this case, pop operation is very time consuming. So I won't suggest to create a queue using two stacks.
Related