Scribd
Upload
57 views4 pages

Implement Queue Using Two Stacks

A queue can be implemented using two stacks. To enqueue an item, it is pushed onto one stack. To dequeue, all items except the last are popped from that stack and pushed onto the other stack. The last item is then returned without changing the stack order. This implementation increases the time complexity of dequeue to O(n) while keeping enqueue at O(1). It is also possible to implement a stack using a queue by adding and removing from the front and back of the queue for push and pop.

Uploaded by

preethi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
57 views4 pages

Implement Queue Using Two Stacks

A queue can be implemented using two stacks. To enqueue an item, it is pushed onto one stack. To dequeue, all items except the last are popped from that stack and pushed onto the other stack. The last item is then returned without changing the stack order. This implementation increases the time complexity of dequeue to O(n) while keeping enqueue at O(1). It is also possible to implement a stack using a queue by adding and removing from the front and back of the queue for push and pop.

Uploaded by

preethi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 4

1. Discuss how to implement queue data structure using stack.

There are two ways to implement a queue.

a) By increasing the cost of the enqueue operation


b) By increasing the cost of the dequeue operation

2. How many stacks are needed to implement a queue?

A queue can be implemented using two stacks. They are function call stack and user stack.

3. Given the StackInterface and the LinkedStack classes, write Java code to create a queue
using stack. Test your code by creating a queue Number that takes N numbers to enqueue
and then dequeue and prints them the numbers on the screen.

Source code:

import java.util.Stack;
public class Linkedinterface {

static class queue {

Stack<Integer> stack1;

static void push(Stack<Integer> top, int new_data)

top.push(new_data);

static int pop(Stack<Integer> top)

{
if (top == null) {

System.out.println("Stack Underflow");

System.exit(0);

return top.pop();

static void enqueue(queue a , int x)

push(a.stack1, x);

static int dequeue(queue a)

int x, res = 0;

if (a.stack1.isEmpty()) {

System.out.println("Queue is Empty");

System.exit(0);

else if (a.stack1.size() == 1) {

return pop(a.stack1);

else {
x = pop(a.stack1);

res = dequeue(a);

push(a.stack1, x);

return res;

return 0;

public static void main(String[] args)

queue a = new queue();

a.stack1 = new Stack<>();

enqueue(a, 89);

enqueue(a, 78);

enqueue(a, 30);

System.out.print(dequeue(a) + " ");

System.out.print(dequeue(a) + " ");

System.out.print(dequeue(a) + " ");

}
4. What is the complexity of queue implementation using stack?

By increasing the cost of the enqueue operation


Time Complexity:
Push = O(N).
Pop = O(1).

By making the dequeue operation costly

Time Complexity:
Push = O(1)

Pop = O(N)

5. Is it possible to implement the stack data structure using a queue? Justify your answer.

a stack data structure with push and pop operations can be used to implement a queue
using instances of stack data structure and operations on them.

You might also like