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 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 and for dequeing ( removing ) an element, we increment front.
See the implementation below.

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

class Queue {
   int arr[SIZE];
   int front, rear;
public :
   Queue() {
      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 Queue :: enqueue(int data) {
   if (rear == -1) { // queue is empty
      front = rear = 0;
      arr[front] = data;
   }
   else if (rear == SIZE-1) { // queue is full
      cout << "\nNo space in queue ...";
   }
   else {
      rear++;
      arr[rear] = data; // insert the element at the end of the queue
   }
}

void Queue :: 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++; // shift front by 1 position
      }
   }
}

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

int main() {
   Queue q;
   q.enqueue(7);
   q.enqueue(11);
   q.enqueue(8);
   q.enqueue(2);
   q.display();
   q.dequeue(); // 7 is dequeued
   q.dequeue(); // 11 is dequeued
   q.enqueue(5);
   q.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