Queue using Stacks

Last Updated : 10 Jul, 2023

The problem is opposite of this post. We are given a stack data structure with push and pop operations, the task is to implement a queue using instances of stack data structure and operations on them.

Stack and Queue with insert and delete operations

A queue can be implemented using two stacks. Let queue to be implemented be q and stacks used to implement q be stack1 and stack2. q can be implemented in two ways:

Method 1 (By making enQueue operation costly): This method makes sure that oldest entered element is always at the top of stack 1, so that deQueue operation just pops from stack1. To put the element at top of stack1, stack2 is used.

enQueue(q, x):

While stack1 is not empty, push everything from stack1 to stack2.
Push x to stack1 (assuming size of stacks is unlimited).
Push everything back to stack1.
Here time complexity will be O(n)

deQueue(q):

If stack1 is empty then error
Pop an item from stack1 and return it
Here time complexity will be O(1)

Below is the implementation of the above approach:

C++

// CPP program to implement Queue using
// two stacks with costly enQueue()
#include <bits/stdc++.h>
using namespace std;
 
struct Queue {
    stack<int> s1, s2;
 
    void enQueue(int x)
    {
        // Move all elements from s1 to s2
        while (!s1.empty()) {
            s2.push(s1.top());
            s1.pop();
        }
 
        // Push item into s1
        s1.push(x);
 
        // Push everything back to s1
        while (!s2.empty()) {
            s1.push(s2.top());
            s2.pop();
        }
    }
 
    // Dequeue an item from the queue
    int deQueue()
    {
        // if first stack is empty
        if (s1.empty()) {
            return -1;
        }
 
        // Return top of s1
        int x = s1.top();
        s1.pop();
        return x;
    }
};
 
// Driver code
int main()
{
    Queue q;
    q.enQueue(1);
    q.enQueue(2);
    q.enQueue(3);
 
    cout << q.deQueue() << '\n';
    cout << q.deQueue() << '\n';
    cout << q.deQueue() << '\n';
 
    return 0;
}

Java

// Java program to implement Queue using 
// two stacks with costly enQueue() 
import java.util.*;
 
class GFG 
{ 
static class Queue 
{ 
    static Stack<Integer> s1 = new Stack<Integer>(); 
    static Stack<Integer> s2 = new Stack<Integer>(); 
 
    static void enQueue(int x) 
    { 
        // Move all elements from s1 to s2 
        while (!s1.isEmpty())
        { 
            s2.push(s1.pop()); 
            //s1.pop(); 
        } 
 
        // Push item into s1 
        s1.push(x); 
 
        // Push everything back to s1 
        while (!s2.isEmpty()) 
        { 
            s1.push(s2.pop()); 
            //s2.pop(); 
        } 
    } 
 
    // Dequeue an item from the queue 
    static int deQueue() 
    { 
        // if first stack is empty 
        if (s1.isEmpty()) 
        { 
            return -1;
        } 
 
        // Return top of s1 
        int x = s1.peek(); 
        s1.pop(); 
        return x; 
    } 
}; 
 
// Driver code 
public static void main(String[] args) 
{ 
    Queue q = new Queue(); 
    q.enQueue(1); 
    q.enQueue(2); 
    q.enQueue(3); 
 
    System.out.println(q.deQueue()); 
    System.out.println(q.deQueue());
    System.out.println(q.deQueue());
} 
} 
 
// This code is contributed by Prerna Saini

Python3

# Python3 program to implement Queue using 
# two stacks with costly enQueue() 
 
class Queue: 
    def __init__(self):
        self.s1 = []
        self.s2 = []
 
    def enQueue(self, x):
         
        # Move all elements from s1 to s2 
        while len(self.s1) != 0: 
            self.s2.append(self.s1[-1]) 
            self.s1.pop()
 
        # Push item into self.s1 
        self.s1.append(x) 
 
        # Push everything back to s1 
        while len(self.s2) != 0: 
            self.s1.append(self.s2[-1]) 
            self.s2.pop()
 
    # Dequeue an item from the queue 
    def deQueue(self):
         
            # if first stack is empty 
        if len(self.s1) == 0: 
            return -1;
     
        # Return top of self.s1 
        x = self.s1[-1] 
        self.s1.pop() 
        return x
 
# Driver code 
if __name__ == '__main__':
    q = Queue()
    q.enQueue(1) 
    q.enQueue(2) 
    q.enQueue(3) 
 
    print(q.deQueue())
    print(q.deQueue())
    print(q.deQueue())
 
# This code is contributed by PranchalK 

C#

// C# program to implement Queue using 
// two stacks with costly enQueue()
using System;
using System.Collections;
 
class GFG 
{ 
     
public class Queue 
{ 
    public Stack s1 = new Stack(); 
    public Stack s2 = new Stack(); 
 
    public void enQueue(int x) 
    { 
        // Move all elements from s1 to s2 
        while (s1.Count > 0) 
        { 
            s2.Push(s1.Pop()); 
            //s1.Pop(); 
        } 
 
        // Push item into s1 
        s1.Push(x); 
 
        // Push everything back to s1 
        while (s2.Count > 0) 
        { 
            s1.Push(s2.Pop()); 
            //s2.Pop(); 
        } 
    } 
 
    // Dequeue an item from the queue 
    public int deQueue() 
    { 
        // if first stack is empty 
        if (s1.Count == 0) 
        { 
            return -1;
        } 
 
        // Return top of s1 
        int x = (int)s1.Peek(); 
        s1.Pop(); 
        return x; 
    } 
}; 
 
// Driver code 
public static void Main() 
{ 
    Queue q = new Queue(); 
    q.enQueue(1); 
    q.enQueue(2); 
    q.enQueue(3); 
 
    Console.Write(q.deQueue()+" "); 
    Console.Write(q.deQueue()+" "); 
    Console.Write(q.deQueue()); 
} 
} 
 
// This code is contributed by 
// Subhadeep Gupta 

Javascript

<script>
 
// Javascript program to implement Queue using  
// two stacks with costly enQueue()  
class Queue{
     
constructor()
{
    this.s1 = [];
    this.s2 = [];
}
 
enQueue(x)
{
     
    // Move all elements from s1 to s2 
    while (this.s1.length != 0)
    { 
        this.s2.push(this.s1.pop()); 
        //s1.pop(); 
    } 
 
    // Push item into s1 
    this.s1.push(x); 
 
    // Push everything back to s1 
    while (this.s2.length != 0) 
    { 
        this.s1.push(this.s2.pop()); 
        //s2.pop(); 
    } 
}
 
// Dequeue an item from the queue  
deQueue() 
{
     
    // If first stack is empty 
    if (this.s1.length == 0) 
    { 
        return -1;
    } 
 
    // Return top of s1 
    let x = this.s1[this.s1.length - 1]; 
    this.s1.pop(); 
    return x; 
}
}
 
// Driver code
let q = new Queue(); 
q.enQueue(1); 
q.enQueue(2); 
q.enQueue(3); 
 
document.write(q.deQueue() + "<br>"); 
document.write(q.deQueue() + "<br>");
document.write(q.deQueue() + "<br>");
 
// This code is contributed by rag2127
 
</script>

Output:

1
2
3

Complexity Analysis:

Time Complexity:
- Push operation: O(N).
  In the worst case we have empty whole of stack 1 into stack 2.
- Pop operation: O(1).
  Same as pop operation in stack.
Auxiliary Space: O(N).
Use of stack for storing values.

Method 2 (By making deQueue operation costly): In this method, in en-queue operation, the new element is entered at the top of stack1. In de-queue operation, if stack2 is empty then all the elements are moved to stack2 and finally top of stack2 is returned.

enQueue(q,  x)
  1) Push x to stack1 (assuming size of stacks is unlimited).
Here time complexity will be O(1)

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.
Here time complexity will be O(n)

Method 2 is definitely better than method 1.

Method 1 moves all the elements twice in enQueue operation, while method 2 (in deQueue operation) moves the elements once and moves elements only if stack2 empty. So, the amortized complexity of the dequeue operation becomes $\Theta (1)$

Implementation of method 2:

C++

// CPP program to implement Queue using
// two stacks with costly deQueue()
#include <bits/stdc++.h>
using namespace std;
 
struct Queue {
    stack<int> s1, s2;
 
    // Enqueue an item to the queue
    void enQueue(int x)
    {
        // Push item into the first stack
        s1.push(x);
    }
 
    // Dequeue an item from the queue
    int deQueue()
    {
        // if both stacks are empty
        if (s1.empty() && s2.empty()) {
            return -1;
        }
 
        // if s2 is empty, move
        // elements from s1
        if (s2.empty()) {
            while (!s1.empty()) {
                s2.push(s1.top());
                s1.pop();
            }
        }
 
        // return the top item from s2
        int x = s2.top();
        s2.pop();
        return x;
    }
};
 
// Driver code
int main()
{
    Queue q;
 
    cout << q.deQueue() << '\n';
    q.enQueue(1);
    cout << q.deQueue() << '\n';
 
    return 0;
}

C

/* C Program to implement a queue using two stacks */
#include <stdio.h>
#include <stdlib.h>
 
/* structure of a stack node */
struct sNode {
    int data;
    struct sNode* next;
};
 
/* Function to push an item to stack*/
void push(struct sNode** top_ref, int new_data);
 
/* Function to pop an item from stack*/
int pop(struct sNode** top_ref);
 
/* structure of queue having two stacks */
struct queue {
    struct sNode* stack1;
    struct sNode* stack2;
};
 
/* Function to enqueue an item to queue */
void enQueue(struct queue* q, int x)
{
    push(&q->stack1, x);
}
 
/* Function to deQueue an item from queue */
int deQueue(struct queue* q)
{
    int x;
 
    /* If both stacks are empty then error */
    if (q->stack1 == NULL && q->stack2 == NULL) {
        return -1;
    }
 
    /* Move elements from stack1 to stack 2 only if
       stack2 is empty */
    if (q->stack2 == NULL) {
        while (q->stack1 != NULL) {
            x = pop(&q->stack1);
            push(&q->stack2, x);
        }
    }
 
    x = pop(&q->stack2);
    return x;
}
 
/* Function to push an item to stack*/
void push(struct sNode** top_ref, int new_data)
{
    /* allocate node */
    struct sNode* new_node = (struct sNode*)malloc(sizeof(struct sNode));
    if (new_node == NULL) {
        printf("Stack overflow \n");
        getchar();
        exit(0);
    }
 
    /* put in the data */
    new_node->data = new_data;
 
    /* link the old list of the new node */
    new_node->next = (*top_ref);
 
    /* move the head to point to the new node */
    (*top_ref) = new_node;
}
 
/* Function to pop an item from stack*/
int pop(struct sNode** top_ref)
{
    int res;
    struct sNode* top;
 
    /*If stack is empty then error */
    if (*top_ref == NULL) {
        return -1;
    }
    else {
        top = *top_ref;
        res = top->data;
        *top_ref = top->next;
        free(top);
        return res;
    }
}
 
/* Driver function to test anove functions */
int main()
{
    /* Create a queue with items 1 2 3*/
    struct queue* q = (struct queue*)malloc(sizeof(struct queue));
    q->stack1 = NULL;
    q->stack2 = NULL;
    enQueue(q, 1);
    enQueue(q, 2);
    enQueue(q, 3);
 
    /* Dequeue items */
    printf("%d ", deQueue(q));
    printf("%d ", deQueue(q));
    printf("%d ", deQueue(q));
 
    return 0;
}

Java

/* Java Program to implement a queue using two stacks */
// Note that Stack class is used for Stack implementation
 
import java.util.Stack;
 
public class GFG {
    /* class of queue having two stacks */
    static class Queue {
        Stack<Integer> stack1;
        Stack<Integer> stack2;
    }
 
    /* Function to push an item to stack*/
    static void push(Stack<Integer> top_ref, int new_data)
    {
        // Push the data onto the stack
        top_ref.push(new_data);
    }
 
    /* Function to pop an item from stack*/
    static int pop(Stack<Integer> top_ref)
    {
        /*If stack is empty then error */
        if (top_ref.isEmpty()) {
            return -1;
        }
 
        // pop the data from the stack
        return top_ref.pop();
    }
 
    // Function to enqueue an item to the queue
    static void enQueue(Queue q, int x)
    {
        push(q.stack1, x);
    }
 
    /* Function to deQueue an item from queue */
    static int deQueue(Queue q)
    {
        int x;
 
        /* If both stacks are empty then error */
        if (q.stack1.isEmpty() && q.stack2.isEmpty()) {
            return -1;
        }
 
        /* Move elements from stack1 to stack 2 only if
        stack2 is empty */
        if (q.stack2.isEmpty()) {
            while (!q.stack1.isEmpty()) {
                x = pop(q.stack1);
                push(q.stack2, x);
            }
        }
        x = pop(q.stack2);
        return x;
    }
 
    /* Driver function to test above functions */
    public static void main(String args[])
    {
        /* Create a queue with items 1 2 3*/
        Queue q = new Queue();
        q.stack1 = new Stack<>();
        q.stack2 = new Stack<>();
        enQueue(q, 1);
        enQueue(q, 2);
        enQueue(q, 3);
 
        /* Dequeue items */
        System.out.print(deQueue(q) + " ");
        System.out.print(deQueue(q) + " ");
        System.out.println(deQueue(q) + " ");
    }
}
// This code is contributed by Sumit Ghosh

Python3

# Python3 program to implement Queue using 
# two stacks with costly deQueue()
 
class Queue:
    def __init__(self):
        self.s1 = []
        self.s2 = []
 
    # EnQueue item to the queue
    def enQueue(self, x):
        self.s1.append(x)
 
    # DeQueue item from the queue
    def deQueue(self):
 
        # if both the stacks are empty
        if len(self.s1) == 0 and len(self.s2) == 0:
            return -1
 
        # if s2 is empty and s1 has elements
        elif len(self.s2) == 0 and len(self.s1) > 0:
            while len(self.s1):
                temp = self.s1.pop()
                self.s2.append(temp)
            return self.s2.pop()
 
        else:
            return self.s2.pop()
 
    # Driver code
if __name__ == '__main__':
    q = Queue()
    q.enQueue(1)
    q.enQueue(2)
    q.enQueue(3)
 
    print(q.deQueue())
    print(q.deQueue())
    print(q.deQueue())
 
# This code is contributed by Pratyush Kumar 

C#

/* C# Program to implement a queue using two stacks */
// Note that Stack class is used for Stack implementation
using System;
using System.Collections.Generic; 
 
class GFG 
{
    /* class of queue having two stacks */
    public class Queue
    {
        public Stack<int> stack1;
        public Stack<int> stack2;
    }
 
    /* Function to push an item to stack*/
    static void push(Stack<int> top_ref, int new_data)
    {
        // Push the data onto the stack
        top_ref.Push(new_data);
    }
 
    /* Function to pop an item from stack*/
    static int pop(Stack<int> top_ref)
    {
        /*If stack is empty then error */
        if (top_ref.Count == 0) 
        {
               return -1;
        }
 
        // pop the data from the stack
        return top_ref.Pop();
    }
 
    // Function to enqueue an item to the queue
    static void enQueue(Queue q, int x)
    {
        push(q.stack1, x);
    }
 
    /* Function to deQueue an item from queue */
    static int deQueue(Queue q)
    {
        int x;
 
        /* If both stacks are empty then error */
        if (q.stack1.Count == 0 && q.stack2.Count == 0)
        {
            return -1;
        }
 
        /* Move elements from stack1 to stack 2 only if
        stack2 is empty */
        if (q.stack2.Count == 0) 
        {
            while (q.stack1.Count != 0) 
            {
                x = pop(q.stack1);
                push(q.stack2, x);
            }
        }
        x = pop(q.stack2);
        return x;
    }
 
    /* Driver code */
    public static void Main(String []args)
    {
        /* Create a queue with items 1 2 3*/
        Queue q = new Queue();
        q.stack1 = new Stack<int>();
        q.stack2 = new Stack<int>();
        enQueue(q, 1);
        enQueue(q, 2);
        enQueue(q, 3);
 
        /* Dequeue items */
        Console.Write(deQueue(q) + " ");
        Console.Write(deQueue(q) + " ");
        Console.WriteLine(deQueue(q) + " ");
    }
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// JS program to implement Queue using
// two stacks with costly deQueue()
 
class Queue {
 
    constructor() {
        this.s1 = [];
        this.s2 = [];
    }
 
    enQueue(x) {
        // Push item into the first stack
        this.s1.push(x);
    }
 
    // Dequeue an item from the queue
    deQueue() {
        // if both stacks are empty
        if (this.s1.length == 0 && this.s2.length == 0) {
            return -1;
        }
 
        // if s2 is empty, move
        // elements from s1
        if (this.s2.length == 0) {
            while (this.s1.length != 0) {
                this.s2.push(this.s1[0]);
                this.s1.shift();
            }
        }
 
        // return the top item from s2
        let x = this.s2[0];
        this.s2.shift();
        return x;
    }
};
 
// Driver code
let q = new Queue;
q.enQueue(1);
q.enQueue(2);
q.enQueue(3);
 
console.log(q.deQueue());
console.log(q.deQueue());
console.log(q.deQueue());
 
// This code is contributed by adityamaharshi21
 
</script>

Output:

1 2 3

Complexity Analysis:

Time Complexity:
- Push operation: O(1).
  Same as pop operation in stack.
- Pop operation: O(N) in general and O(1) amortized time complexity.
  In the worst case we have to empty the whole of stack 1 into stack 2 so its O(N). Amortized time is the way to express the time complexity when an algorithm has the very bad time complexity only once in a while besides the time complexity that happens most of time. So its O(1) amortized time complexity, since we have to empty whole of stack 1 only when stack 2 is empty, rest of the times the pop operation takes O(1) time.
Auxiliary Space: O(N).
Use of stack for storing values.

Queue can also be implemented using one user stack and one Function Call Stack. Below is modified Method 2 where recursion (or Function Call Stack) is used to implement queue using only one user defined stack.

enQueue(x)
  1) Push x to stack1.

deQueue:
  1) If stack1 is empty then error.
  2) If stack1 has only one element then return it.
  3) Recursively pop everything from the stack1, store the popped item 
    in a variable res,  push the res back to stack1 and return res

The step 3 makes sure that the last popped item is always returned and since the recursion stops when there is only one item in stack1 (step 2), we get the last element of stack1 in deQueue() and all other items are pushed back in step

3. Implementation of method 2 using Function Call Stack:

C++

// CPP program to implement Queue using
// one stack and recursive call stack.
#include <bits/stdc++.h>
using namespace std;
 
struct Queue {
    stack<int> s;
 
    // Enqueue an item to the queue
    void enQueue(int x)
    {
        s.push(x);
    }
 
    // Dequeue an item from the queue
    int deQueue()
    {
        if (s.empty()) {
            return -1;
        }
 
        // pop an item from the stack
        int x = s.top();
        s.pop();
 
        // if stack becomes empty, return
        // the popped item
        if (s.empty())
            return x;
 
        // recursive call
        int item = deQueue();
 
        // push popped item back to the stack
        s.push(x);
 
        // return the result of deQueue() call
        return item;
    }
};
 
// Driver code
int main()
{
    Queue q;
    q.enQueue(1);
    q.enQueue(2);
    q.enQueue(3);
 
    cout << q.deQueue() << '\n';
    cout << q.deQueue() << '\n';
    cout << q.deQueue() << '\n';
 
    return 0;
}

C

/* Program to implement a queue using one user defined stack 
and one Function Call Stack */
#include <stdio.h>
#include <stdlib.h>
 
/* structure of a stack node */
struct sNode {
    int data;
    struct sNode* next;
};
 
/* structure of queue having two stacks */
struct queue {
    struct sNode* stack1;
};
 
/* Function to push an item to stack*/
void push(struct sNode** top_ref, int new_data);
 
/* Function to pop an item from stack*/
int pop(struct sNode** top_ref);
 
/* Function to enqueue an item to queue */
void enQueue(struct queue* q, int x)
{
    push(&q->stack1, x);
}
 
/* Function to deQueue an item from queue */
int deQueue(struct queue* q)
{
    int x, res;
 
    /* If both stacks are empty then error */
    if (q->stack1 == NULL) {
        return -1;
    }
    else if (q->stack1->next == NULL) {
        return pop(&q->stack1);
    }
    else {
        /* pop an item from the stack1 */
        x = pop(&q->stack1);
 
        /* store the last deQueued item */
        res = deQueue(q);
 
        /* push everything back to stack1 */
        push(&q->stack1, x);
        return res;
    }
}
 
/* Function to push an item to stack*/
void push(struct sNode** top_ref, int new_data)
{
    /* allocate node */
    struct sNode* new_node = (struct sNode*)malloc(sizeof(struct sNode));
 
    if (new_node == NULL) {
        printf("Stack overflow \n");
        getchar();
        exit(0);
    }
 
    /* put in the data */
    new_node->data = new_data;
 
    /* link the old list of the new node */
    new_node->next = (*top_ref);
 
    /* move the head to point to the new node */
    (*top_ref) = new_node;
}
 
/* Function to pop an item from stack*/
int pop(struct sNode** top_ref)
{
    int res;
    struct sNode* top;
 
    /*If stack is empty then error */
    if (*top_ref == NULL) {
        return -1;
    }
    else {
        top = *top_ref;
        res = top->data;
        *top_ref = top->next;
        free(top);
        return res;
    }
}
 
/* Driver function to test above functions */
int main()
{
    /* Create a queue with items 1 2 3*/
    struct queue* q = (struct queue*)malloc(sizeof(struct queue));
    q->stack1 = NULL;
 
    enQueue(q, 1);
    enQueue(q, 2);
    enQueue(q, 3);
 
    /* Dequeue items */
    printf("%d ", deQueue(q));
    printf("%d ", deQueue(q));
    printf("%d ", deQueue(q));
 
    return 0;
}

Java

// Java Program to implement a queue using one stack
 
import java.util.Stack;
 
public class QOneStack {
    // class of queue having two stacks
    static class Queue {
        Stack<Integer> stack1;
    }
 
    /* Function to push an item to stack*/
    static void push(Stack<Integer> top_ref, int new_data)
    {
        /* put in the data */
        top_ref.push(new_data);
    }
 
    /* Function to pop an item from stack*/
    static int pop(Stack<Integer> top_ref)
    {
        /*If stack is empty then error */
        if (top_ref == null) {
            return -1;
        }
        // return element from stack
        return top_ref.pop();
    }
 
    /* Function to enqueue an item to queue */
    static void enQueue(Queue q, int x)
    {
        push(q.stack1, x);
    }
 
    /* Function to deQueue an item from queue */
    static int deQueue(Queue q)
    {
        int x, res = 0;
        /* If the stacks is empty then error */
        if (q.stack1.isEmpty()) {
            return -1;
        }
        // Check if it is a last element of stack
        else if (q.stack1.size() == 1) {
            return pop(q.stack1);
        }
        else {
 
            /* pop an item from the stack1 */
            x = pop(q.stack1);
 
            /* store the last deQueued item */
            res = deQueue(q);
 
            /* push everything back to stack1 */
            push(q.stack1, x);
            return res;
        }
    }
 
    /* Driver function to test above functions */
    public static void main(String[] args)
    {
        /* Create a queue with items 1 2 3*/
        Queue q = new Queue();
        q.stack1 = new Stack<>();
 
        enQueue(q, 1);
        enQueue(q, 2);
        enQueue(q, 3);
 
        /* Dequeue items */
        System.out.print(deQueue(q) + " ");
        System.out.print(deQueue(q) + " ");
        System.out.print(deQueue(q) + " ");
    }
}
// This code is contributed by Sumit Ghosh

Python3

# Python3 program to implement Queue using  
# one stack and recursive call stack. 
class Queue:
    def __init__(self):
        self.s = []
         
    # Enqueue an item to the queue 
    def enQueue(self, data):
        self.s.append(data)
         
    # Dequeue an item from the queue 
    def deQueue(self):
        # Return if queue is empty
        if len(self.s) <= 0:
            return -1
         
        # pop an item from the stack
        x = self.s[len(self.s) - 1]
        self.s.pop()
         
        # if stack become empty
        # return the popped item
        if len(self.s) <= 0:
            return x
             
        # recursive call
        item = self.deQueue()
         
        # push popped item back to
        # the stack
        self.s.append(x)
         
        # return the result of 
        # deQueue() call
        return item
     
# Driver code  
if __name__ == '__main__':
    q = Queue()
    q.enQueue(1)
    q.enQueue(2)
    q.enQueue(3)
     
    print(q.deQueue())
    print(q.deQueue())
    print(q.deQueue())  
     
# This code is contributed by iArman

C#

// C# Program to implement a queue using one stack
using System;
using System.Collections.Generic; 
 
public class QOneStack
{
    // class of queue having two stacks
    public class Queue 
    {
        public Stack<int> stack1;
    }
 
    /* Function to push an item to stack*/
    static void push(Stack<int> top_ref, int new_data)
    {
        /* put in the data */
        top_ref.Push(new_data);
    }
 
    /* Function to pop an item from stack*/
    static int pop(Stack<int> top_ref)
    {
        /*If stack is empty then error */
        if (top_ref == null)
        {
            return -1;
        }
        // return element from stack
        return top_ref.Pop();
    }
 
    /* Function to enqueue an item to queue */
    static void enQueue(Queue q, int x)
    {
        push(q.stack1, x);
    }
 
    /* Function to deQueue an item from queue */
    static int deQueue(Queue q)
    {
        int x, res = 0;
         
        /* If the stacks is empty then error */
        if (q.stack1.Count == 0)
        {
            return -1;
        }
         
        // Check if it is a last element of stack
        else if (q.stack1.Count == 1) 
        {
            return pop(q.stack1);
        }
        else
        {
 
            /* pop an item from the stack1 */
            x = pop(q.stack1);
 
            /* store the last deQueued item */
            res = deQueue(q);
 
            /* push everything back to stack1 */
            push(q.stack1, x);
            return res;
        }
    }
 
    /* Driver function to test above functions */
    public static void Main(String[] args)
    {
        /* Create a queue with items 1 2 3*/
        Queue q = new Queue();
        q.stack1 = new Stack<int>();
 
        enQueue(q, 1);
        enQueue(q, 2);
        enQueue(q, 3);
 
        /* Dequeue items */
        Console.Write(deQueue(q) + " ");
        Console.Write(deQueue(q) + " ");
        Console.Write(deQueue(q) + " ");
    }
}
 
// This code is contributed by Princi Singh

Javascript

// JS program to implement Queue using
// two stacks with costly deQueue()
class Queue {
    constructor() {
        this.s1 = [];
        this.s2 = [];
    }
 
    // Enqueue an item to the queue
    enQueue(x) {
     
        // Push item into the first stack
        this.s1.push(x);
    }
 
    // Dequeue an item from the queue
    deQueue() {
        // if both stacks are empty
        if (this.s1.length == 0 && this.s2.length == 0) {
            return -1;
        }
 
        // if s2 is empty, move
        // elements from s1
        if (this.s2.length == 0) {
            while (this.s1.length != 0) {
                this.s2.push(this.s1[0]);
                this.s1.shift();
            }
        }
 
        // return the top item from s2
        let x = this.s2[0];
        this.s2.shift();
        return x;
    }
}
 
// Driver code
let q = new Queue();
q.enQueue(1);
q.enQueue(2);
q.enQueue(3);
 
console.log(q.deQueue());
console.log(q.deQueue());
console.log(q.deQueue());
 
// This code is contributed by adityamaharshi21

Output:

1 2 3

Complexity Analysis:

Time Complexity:
- Push operation : O(1).
  Same as pop operation in stack.
- Pop operation : O(N).
  The difference from above method is that in this method element is returned and all elements are restored back in a single call.
Auxiliary Space: O(N).
Use of stack for storing values.

Asked in: Inmobi, Accolite, Adobe, Amazon, DE Shaw, Flipkart, Goldman Sachs, InfoEdge, MakeMyTrip, Microsoft, Oracle

Please write comments if you find any of the above codes/algorithms incorrect, or find better ways to solve the same problem.

GeeksforGeeks

Improve

Previous Article

How to implement a Stack using list in C++ STL

C++ Program to Reverse a String Using Stack

Similar Reads

Should we declare as Queue or Priority Queue while using Priority Queue in Java?

Queue: Queue is an Interface that extends the collection Interface in Java and this interface belongs to java.util package. A queue is a type of data structure that follows the FIFO (first-in-first-out ) order. The queue contains ordered elements where insertion and deletion of elements are done at different ends. Priority Queue and Linked List are

Stack and Queue in Python using queue Module

A simple python List can act as queue and stack as well. Queue mechanism is used widely and for many purposes in daily life. A queue follows FIFO rule(First In First Out) and is used in programming for sorting and for many more things. Python provides Class queue as a module which has to be generally created in languages such as C/C++ and Java. 1.

Check if a queue can be sorted into another queue using a stack

Given a Queue consisting of first n natural numbers (in random order). The task is to check whether the given Queue elements can be arranged in increasing order in another Queue using a stack. The operation allowed are: Push and pop elements from the stack Pop (Or Dequeue) from the given Queue. Push (Or Enqueue) in the another Queue. Examples : Inp

Reversing a Queue using another Queue

Given a queue. The task is to reverse the queue using another empty queue. Examples: Input: queue[] = {1, 2, 3, 4, 5} Output: 5 4 3 2 1 Input: queue[] = {10, 20, 30, 40} Output: 40 30 20 10 Approach: Given a queue and an empty queue.The last element of the queue should be the first element of the new queue.To get the last element there is a need to

Largest Rectangle Area under Histogram using JavaScript | Without using Stacks

Find the largest rectangular area possible in a given histogram where the largest rectangle can be made of a number of contiguous bars. For simplicity, assume that all bars have the same width and the width is 1 unit. For example, consider the following histogram with 7 bars of heights {6, 2, 5, 4, 5, 1, 6}. The largest possible rectangle possible

What is Priority Queue | Introduction to Priority Queue

A priority queue is a type of queue that arranges elements based on their priority values. Elements with higher priority values are typically retrieved before elements with lower priority values. In a priority queue, each element has a priority value associated with it. When you add an element to the queue, it is inserted in a position based on its

queue::empty() and queue::size() in C++ STL

Queue is a type of container adaptor that operate in a first in first out (FIFO) type of arrangement. Elements are inserted at the back (end) and are deleted from the front. queue::empty() empty() function is used to check if the queue container is empty or not. SyntaxqueueName.empty()ParametersThis function does not accept any parameter.Return Val

queue::front() and queue::back() in C++ STL

Queue are a type of container adaptors which operate in a first in first out (FIFO) type of arrangement. Elements are inserted at the back (end) and are deleted from the front. queue::front() This function is used to reference the first or the oldest element of the queue container. This function can be used to fetch the first element of a queue.Syn

Advantages of circular queue over linear queue

Linear Queue: A Linear Queue is generally referred to as Queue. It is a linear data structure that follows the FIFO (First In First Out) order. A real-life example of a queue is any queue of customers waiting to buy a product from a shop where the customer that came first is served first. In Queue all deletions (dequeue) are made at the front and a

Difference between Queue and Deque (Queue vs. Deque)

Queue: The queue is an abstract data type or linear data structure from which elements can be inserted at the rear(back) of the queue and elements can be deleted from the front(head) of the queue. The operations allowed in the queue are:insert an element at the reardelete element from the frontget the last elementget the first elementcheck the size

Article Tags :

Practice Tags :