24/180: Implement Queue using Stacks

  1. By Making Enqueue operation costly
  2. By Making Dequeue operation costly
  1. While stack1 is not empty, push everything from stack1 to stack2.
  2. Push x to stack1 (assuming size of stacks is unlimited)
  3. Push everything back to stack 1.
  4. 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)
static class Queue{   static Stack<Integer> s1 = new Stack<Integer>();
static Stack<Integer> s2 = new Stack<Integer>();
static void enQueue(int x){
while(!s1.isEmpty()){
s2.push(s1.pop());
}
s1.push(x);
while(!s2.isEmpty()){
s1.push(s2.pop());
}
}
static int deQueue(){
if(s1.isEmpty()){
System.out.println("Q is empty");
System.exit(0);
}
int x = s1.peek();
s1.pop();
return x;
}
}
Time complexity:
Push Operation O(N)
Pop Operation O(1)
Auxiliary Space O(N)
  1. Push x to stack1 (assuming size of stack is unlimited). Here time complexity will be o(1)
  1. If both stacks are empty then error.
  2. If stack2 is empty, while stack 1 is not empty, push everything from stack1 to stack 2.
  3. Pop the element from stack2 and return it.
public class Queue{
Stack<Integer> stack1;
Stack<Integer> stack2;
static void push(Stack<Integer> top_ref, int new_data){
top_ref.push(new_data);
}
static int pop(Stack<Integer> top_ref){
if(top_ref.isEmpty()){
System.out.println("Stack Underflow");
}
return top_ref.pop();
}
static void enQueue(Queue q, int x){
push(q.stack1, x);
}
static int deQueue(Queue q){
int x;
if(q.stack1.isEmpty() && q.stack2.isEmpty()){
System.out.println("Q is empty");
System.exit(0);
}
if(q.stack2.isEmpty()){
while(!q.stack1.isEmpty()){
x = pop(q.stack1);
push(q.stack2, x);
}
x = pop(q.stack2);
return x;
}}

--

--

--

I am Indian by birth, Punjabi by destiny. Humanity is my religion. Love to eat, travel, read books and my million dreams keep me alive.

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

In this blog we learn how to launch Instance by using Aws cli (command line interface ) by creating…

How to Build and Deploy GraphQL Server in AWS Lambda using nodejs and CloudFormation

Experienced Developers, Use These 7 Tips to Negotiate a Better Salary

Scaling OpenVidu

Camera in the foreground (focused) filming a woman in the background (unfocused). Behind the woman there's a book shelf.

Learning to code (Part 3): Murphy’s Law

Implementing a real-time detection algorithm with Lambda functions and DynamoDb streams

3 Software Developer Jobs Switched. Here’s What I Learned.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Navneet Ojha

Navneet Ojha

I am Indian by birth, Punjabi by destiny. Humanity is my religion. Love to eat, travel, read books and my million dreams keep me alive.

More from Medium

Developer Showcase #2: Matias Lugli, Developer Manager at Tavano

Matias Lugli

Websocket Connection Using Shared Worker

Using confluent-kafka on Apple Silicon

PetriNets: Modelling Concurrent Systems