Home Â» Technical Interview Questions Â» Queue Interview Questions Â» Queue using Stacks

# Queue using Stacks

In queue using a stack problem, we have to implement the following functions of a queue using the standard functions of stack data structure,

1. Enqueue: Add an element to the end of the queue
2. Dequeue: Remove an element from the start of the queue

## Example

Input:
Enqueue(5)
Enqueue(11)
Enqueue(39)
Dequeue()Â  // Returns 5
Enqueue(12)
Dequeue()Â  // Returns 11
Dequeue()Â  // Returns 39
Output:
5
11
39

## Algorithm

A queue can be implemented using two stacks, there are two ways to implement a queue using stacks, first by making enqueue operation costly and second by making dequeue operation costly.

## Method 1 (Costly Enqueue Operation) for Queue using Stacks

Create two stack st1 and st2. Visualize the queue in st1, the top of st1 is front of the queue, and moving downwards in st1 is similar to moving ahead in the queue.

Enqueue(x)

Pushing x to the rear of the queue is the same as pushing x to the bottom of stack st1.

1. Remove all the elements from st1 and push them to st2.
2. Push x to st2.
3. Remove all the elements from st2 and push them back to st1.

Time Complexity = O(n)

Dequeue()

Removing an element from the front of the queue is similar to removing the top of stack st1. So if st1 is not empty pop the top of st1 and return.

Time Complexity= O(1)

Overall Space Complexity of Method 1 = O(n)

### JAVA Code for Queue using Stacks

```import java.util.Stack;

public class QueueUsingStacks {
// Costly Enqueue Operation
private static Stack<Integer> st1;
private static Stack<Integer> st2;

private static void enqueue(int x) {
// remove all the elements from st1 and push them to st2
while (!st1.isEmpty()) {
st2.push(st1.pop());
}

// push x to st2
st2.push(x);

// remove all the elements from st2 and push them back to st1
while (!st2.isEmpty()) {
st1.push(st2.pop());
}
}

private static int dequeue() {
if (st1.isEmpty()) {
return -1;
}

// if st1 is not empty return and remove the top of st1
return st1.pop();
}

public static void main(String[] args) {
st1 = new Stack<>();
st2 = new Stack<>();

// Example
enqueue(5);
enqueue(11);
enqueue(39);
System.out.println(dequeue());
enqueue(12);
System.out.println(dequeue());
System.out.println(dequeue());
}
}```
```5
11
39```

### C++ Code

```#include<bits/stdc++.h>
using namespace std;

// Costly Enqueue Operation

stack<int> st1;
stack<int> st2;

void enqueue(int x) {
// remove all the elements from st1 and push them to st2
while (!st1.empty()) {
int curr = st1.top();
st1.pop();
st2.push(curr);
}

// push x to st2
st2.push(x);

// remove all the elements from st2 and push them back to st1
while (!st2.empty()) {
int curr = st2.top();
st2.pop();
st1.push(curr);
}
}

int dequeue() {
if (st1.empty()) {
return -1;
}

// if st1 is not empty return and remove the top of st1
int top = st1.top();
st1.pop();
}

int main() {
// Example
enqueue(5);
enqueue(11);
enqueue(39);
cout<<dequeue()<<endl;
enqueue(12);
cout<<dequeue()<<endl;
cout<<dequeue()<<endl;

return 0;
}```
```5
11
39```

## Method 2 (Costly Dequeue Operation) for Queue using Stacks

Create two stacks st1 and st2. Visualize queue in st1, the top of st1 represents the rear of the queue, moving upwards in st1 is similar to moving ahead in the queue.

Enqueue(x)

Pushing x to the rear of the queue is similar to pushing x to the top of stack_st1. So push x to top of st1.

READ  Level order traversal using two Queues

Time Complexity= O(1)

Dequeue()

Removing an element from the front of the queue is similar to removing an element from the bottom of stack_st1. So, if st1 is not empty,

1. Remove all the elements from st1 and push them to st2.
2. Pop the top of st2 and store it in a variable top.
3. Remove all the elements from st2 and push them back to st1.

Time Complexity= O(n)

Overall Space Complexity of Method 2 = O(n)

### JAVA Code

```import java.util.Stack;

public class QueueUsingStacks {
// Costly Dequeue Operation
private static Stack<Integer> st1;
private static Stack<Integer> st2;

private static void enqueue(int x) {
// push x to top of st1
st1.push(x);
}

private static int dequeue() {
if (st1.isEmpty()) {
return -1;
}

// if st1 is not empty
// remove all the elements from st1 and push them to st2
while (!st1.isEmpty()) {
st2.push(st1.pop());
}

// pop the top of st2 and store it in a variable top
int top = st2.pop();

// remove all the elements from st2 and push them back to st1
while (!st2.isEmpty()) {
st1.push(st2.pop());
}

}

public static void main(String[] args) {
st1 = new Stack<>();
st2 = new Stack<>();

// Example
enqueue(5);
enqueue(11);
enqueue(39);
System.out.println(dequeue());
enqueue(12);
System.out.println(dequeue());
System.out.println(dequeue());
}
}```
```5
11
39```

### C++ Code

```#include<bits/stdc++.h>
using namespace std;

// Costly Dequeue Operation

stack<int> st1;
stack<int> st2;

void enqueue(int x) {
// push x to top of st1
st1.push(x);
}

int dequeue() {
if (st1.empty()) {
return -1;
}

// if st1 is not empty
// remove all the elements from st1 and push them to st2
while (!st1.empty()) {
int curr = st1.top();
st1.pop();
st2.push(curr);
}

// pop the top of st2 and store it in a variable top
int top = st2.top();
st2.pop();

// remove all the elements from st2 and push them back to st1
while (!st2.empty()) {
int curr = st2.top();
st2.pop();
st1.push(curr);
}

}

int main() {
// Example
enqueue(5);
enqueue(11);
enqueue(39);
cout<<dequeue()<<endl;
enqueue(12);
cout<<dequeue()<<endl;
cout<<dequeue()<<endl;

return 0;
}```
```5
11
39```

Reference1 Â Â Â Â reference2

 Array Interview Questions Graph Interview Questions LinkedList Interview Questions String Interview Questions Tree Interview Questions Core Java Interview Questions