implementing queue using stack
implementation of queue can be done using two stacks. Queue using stack can be done in two ways.
*By making the enqueue (insertion) operation costly.
*By making the dequeue (deletion) operation costly.
Queue using stacks by making enqueue operation costly:
1)Initialize stack1 and stack2 making top1 = top2 = -1.
2)To perform an enqueue operation, time complexity will be O(n)
While stack1 is not empty, Push all the elements from stack1 to stack2.
Push the new element to stack2.
Pop all the elements from stack2 to stack1.
3) To perform dequeue operation, time complexity will be O(1)
Pop and return the element from stack1.
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()) { cout << "Q is Empty"; exit(0); } // 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 program to implement Queue using
// two stacks with costly enQueue()
import java.util.*;
class awe
{
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())
{
System.out.println("Q is Empty");
System.exit(0);
}
// 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());
}
}
1 2 3
Queue using stacks by making dequeue operation costly
1)Initialize stack1 and stack2 making top1 = top2 = -1.
2)To perform an enqueue operation, time complexity will be O(1)
Push the element to be added to stack1.
3) To perform dequeue operation,
If stack2 is empty While stack1 is not empty ,Push all the elements from stack1 to stack2.
Pop and return the element from the stack2. time complexity will be O(n)
Method 2 is better in performance than method 1. As 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 is empty.
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()) {
cout << "Q is empty";
exit(0);
}
// 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;
q.enQueue(1);
q.enQueue(2);
q.enQueue(3);
cout << q.deQueue() << '\n';
cout << q.deQueue() << '\n';
cout << q.deQueue() << '\n';
return 0;
}
// Java Program to implement a queue using two stacks
// Note that Stack class is used for Stack implementation
import java.util.Stack;
public class awe {
/* 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()) {
System.out.println("Stack Underflow");
System.exit(0);
}
// 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()) {
System.out.println("Q is empty");
System.exit(0);
}
/* 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) + " ");
}
}
1 2 3
No comments