# Implement Stack using Queues

Difficulty Level Easy
Design Queue StackViews 1276

Implement the following functions of stack data structure using standard operations of queue,

1. push(x) –> Push an element x to the stack
2. pop() –> Removes the element on top of stack
3. top() –> Return the element on top of stack
4. empty() –> Return whether the stack is empty

## Examples

Input:
stack.push(1);
stack.push(2);
stack.top();  // returns 2
stack.pop();  // returns 2
stack.empty();  // returns false
Output:
2
2
false

## Algorithm for Implement Stack using Queues

A stack can be implemented using 2 queues (say q1 and q2).

### push(x)

Push x at the end of q1 and keep it as the top of the stack in top variable.
Pseudo Code

```void push(int x) {
top = x;
}```

Time Complexity= O(1)

### top()

The top of the stack is always maintained in the top variable, so simply return the top.
Pseudo Code

```int top() {
}```

Time Complexity = O(1)

### empty()

The stack is empty if the queue q1 is empty.
Pseudo Code

```boolean empty() {
return q1.isEmpty();
}```

Time Complexity = O(1)

### pop()

The rear of queue q1 contains the top of the stack, let the size of q1 be n

1. Move (n – 1) elements of queue q1 to queue q2.
2. Also, maintain the top of stack as the current variable being transferred.
3. Now, q1 contains only 1 element that is top of the stack.
4. Remove and store this element in some variable (say ele).
5. Move all the elements from queue q2 to queue q1.
6. Return ele.

Time Complexity= O(n)
where n is the number of elements in the queue.

Consider an example,
q1= 3 -> 5 -> 7 -> 1 -> 2
q2 = null

Pop out an element.

1. Transfer (n – 1) from q1 to q2
q1 = 2 and q2=3 -> 5 -> 7 -> 1
2. Remove and store the element in q1.
q1 = null and q2 =3 -> 5 -> 7 -> 1 and ele = 2
3. Move all the elements from q2 to q1.
q1=3 -> 5 -> 7 -> 1 and q2 = null
4. Return ele.

See the image below for clarification.

Pseudo Code

```int pop() {
int n = q1.size();
for (int i = 0; i < n - 1; i++) {
int curr = q1.remove();
top = curr;
}
int ele = q1.remove();
n = q2.size();
for (int i = 0; i < n; i++) {
}
return ele;
}```

Time Complexity = O(n)

## JAVA Code for Implement Stack using Queues

```import java.util.Queue;
public class StackUsingQueues {
// Two queues to implement stack
private static Queue<Integer> q1 = new LinkedList<>();
private static Queue<Integer> q2 = new LinkedList<>();
// Stores the top element of stack
private static int top;

private static void push(int x) {
// Add element at rear of q1
// update top as current element
top = x;
}

private static int top() {
// Top stores the top of stack
}

private static int pop() {
int n = q1.size();
// Shift (n - 1) elements from q1 to q2 and update top as curr
// element transferred
for (int i = 0; i < n - 1; i++) {
int curr = q1.remove();
top = curr;
}
// q1 contains only 1 element which is top of stack
// store the element in ele and remove it from q1
int ele = q1.remove();
n = q2.size();
// Again transfer back the elements from q2 to q1
for (int i = 0; i < n; i++) {
}
// return ele, this is the top of stack
return ele;
}

private static boolean empty() {
// If q1 is empty then stack is empty
return q1.isEmpty();
}

public static void main(String[] args) {
// Example
push(1);
push(2);
System.out.println(top());
System.out.println(pop());
System.out.println(empty());
}
}```

## C++ Code for Implement Stack using Queues

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

// Two queues to implement stack
queue<int> q1;
queue<int> q2;
// Stores the top element of stack
int Top;

void push(int x) {
// Add element at rear of q1
q1.push(x);
// update top as current element
Top = x;
}

int top() {
// Top stores the top of stack
}

bool empty() {
// If q1 is empty then stack is empty
return q1.empty();
}

int pop() {
int n = q1.size();
// Shift (n - 1) elements from q1 to q2 and update top as curr
// element transferred
for (int i = 0; i < n - 1; i++) {
int curr = q1.front();
q1.pop();
q2.push(curr);
Top = curr;
}
// q1 contains only 1 element which is top of stack
// store the element in ele and remove it from q1
int ele = q1.front();
q1.pop();
n = q2.size();
// Again transfer back the elements from q2 to q1
for (int i = 0; i < n; i++) {
q1.push(q2.front());
q2.pop();
}
// return ele, this is the top of stack
return ele;
}

int main() {
// Example
push(1);
push(2);
cout<<top()<<endl;
cout<<pop()<<endl;
if (empty()) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
return 0;
}```
```2
2
false```
Translate »