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 circular queue using an array. Write the following functions :
enqueue ( int ) to insert an element at the rear end of the queue.
dequeue ( ) to remove the an element from the front end of the queue.
display ( ) to display all the elements of queue.

Solution :-
We will use an array of fixed size and maintain two variables front ( stores the index of the front element of the queue ) and rear ( stores the index of last element in the queue ). For enqueing ( inserting ) an element, we increment rear and insert the element. If we have reached the end of the queue, then if there is a space available at front ( space might have been created due to some dequeue operation ), the element can be inserted there also. For dequeing ( removing ) an element, we increment front. See the implementation below.

#include<iostream>
#define SIZE 5
using namespace std;

class cQueue {
   int arr[SIZE];
   int front, rear;
public :
   cQueue() {
      front = rear = -1;
   }
   void enqueue(int); // insert an element into queue
   void dequeue(); // Remove the front element from queue
   void display(); // display the queue elements
};

void cQueue :: enqueue(int data) {
   if (rear == -1) { // queue is empty
      front = rear = 0;
      arr[front] = data;
   }
   else {
      int pos = (rear + 1) % SIZE;
      if (pos == front) { // queue is full
         cout << "No space in queue ..." << endl;
         return;
      }
      else {
         rear = pos; // update rear
         arr[pos] = data; // insert the data in queue
      }
   }
}

void cQueue :: dequeue() {
   if (front == -1) { // queue is empty
      cout << "Queue is empty ... " << endl;
      return;
   }
   else {
      if (front == rear) { // only one element in queue
         front = rear = -1;
      }
      else {
         front = (front + 1) % SIZE; // shift front by 1 position
      }
   }
}

void cQueue :: display() {
   int i;
   cout << "front : " << front << "   rear : " << rear << endl;
   cout << "Current circular Queue Elements ( front to rear ) :- " << endl;
   if (front == -1) {
      cout << "Queue is empty ... " << endl;
      return;
   }
   else {
      i = front;
      do {
         cout << arr[i] << " ";
         i = (i + 1) % SIZE;
      } while(i != rear);
      cout << arr[rear];

   }
   cout << endl;
}

int main() {
   cQueue cq;
   cq.enqueue(7);
   cq.enqueue(11);
   cq.enqueue(8);
   cq.enqueue(2);
   cq.enqueue(6); // queue becomes full
   cq.display();
   cq.dequeue(); // 7 is dequeued from index 0
   cq.dequeue(); // 11 is dequeued from index 1
   cq.display();
   cq.enqueue(5); // 5 is inserted at index 0
   cq.enqueue(3); // 3 is inserted at index 1
   cq.display();
   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