The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

Stacks & Queues

Problem :-
Implement a Queue data structure using two stacks.

Solution :-
Consider two stacks s1 & s2 ( we will be using STL stacks for implementation ).
Enqueue Operation :: Simply push the element onto s1.
Dequeue Operation :: Transfer all elements from s1 onto s2. Pop the top element from s2. Transfer remaining elements from s2 back to s1.

#include<iostream>
#include<stack>
using namespace std;

// queue data structure using two stacks
class queue {
private :
   stack<int> s1, s2;
public  :
   void enqueue(int element);
   int dequeue();
   void displayQueue();
};

// enqueue an element to the queue
void queue :: enqueue(int element) {
   s1.push(element);
}

// dequeue the front element
int queue :: dequeue() {
   // transfer all elements of s1 into s2
   while (!s1.empty()) {
      s2.push(s1.top());
      s1.pop();
   }
   // pop and store the top element from s2
   int ret = s2.top();
   s2.pop();
   // transfer all elements of s2 back to s1
   while (!s2.empty()) {
      s1.push(s2.top());
      s2.pop();
   }
   return ret;
}

//display the elements of the queue
void queue :: displayQueue() {
   cout<<"\nDisplaying the queue :-\n";
   while (!s1.empty()) {
      s2.push(s1.top());
      s1.pop();
   }
   while (!s2.empty()) {
      cout<<s2.top()<<" ";
      s1.push(s2.top());
      s2.pop();
   }
}

// main
int main() {
   queue q;
   q.enqueue(5);
   q.enqueue(11);
   q.enqueue(1);
   q.enqueue(7);
   q.enqueue(13);
   q.enqueue(11);
   q.displayQueue();
   int dq_element = q.dequeue();
   cout<<"\nAfter dequeing :-";
   q.displayQueue();
   cout<<endl;
   return 0;
}

Back | Next

All problems on Stacks and Queues
* Implement a stack using an array
* Implement a queue using an array
* Implement a circular queue using an array
* Design and implement an extended stack using linked list which permits push, pop & maxElement (gets maximum element in the stack) in O(1) time complexity
* Implement a circular queue using linked list
* Implement a Queue data structure using two stacks
* Sort a Queue using two stacks
* Convert infix expression to the postfix notation
* Implement an algorithm to evaluate a postfix expression
* Given a stack with only 0s & 1s, find the majority element in the stack
* Implement an inplace algorithm to sort a stack