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 linked list.
Circular queue is the one in which rear node has a link to the front node.

Solution :-
We implement the queue in such a manner that next of rear always points to the front node.
The pointers are updated during the enqueue and dequeue operations.
See the implementation below.

#include<iostream>
using namespace std;

// structure of a circular queue node
typedef struct cqueue_node {
   int data;
   struct cqueue_node *next;
}node;

// declare the circular queue data structure
class cqueue {
private :
   // pointers to front and rear element
   node *front, *rear;
public :
   cqueue() {
      front = rear = NULL;
   }
   void enqueue(int element); // insert an element
   int dequeue(); // removes the front element
   void displayCQueue(); // display the circular queue
};

// enqueue an element to the circular queue 
void cqueue :: enqueue(int element) {
   node *new_element = new node;
   new_element->data = element;
   new_element->next = NULL;
   if (front == NULL) {
      front = rear = new_element;
   }
   else {
      // next of rear is front in circular queue
      rear->next = new_element;
      rear = new_element;
   }
   rear->next = front;
}

// dequeue front element from circular queue
int cqueue :: dequeue() {
   int element;
   if (front == NULL) {
      return -99999; //for empty queue
   }
   else if (front == rear) {
      // only 1 node in circular queue
      element = front->data;
      delete front;
      front = rear = NULL;
   }
   else {
      node *ptr = front;
      element = ptr->data;
      front = front->next;
      // next of rear is front in circular queue 
      rear->next = front;
      delete ptr;
   }
   return element;
}

// display all the elements of the circular queue
void cqueue :: displayCQueue() {
   node *ptr = front;
   cout<<"\nCircular Queue \n";
   do {
      cout<<ptr->data<<" ";
      ptr = ptr->next;
   } while (ptr != front);
}

// main
int main() {
   cqueue cq;
   cq.enqueue(5);
   cq.enqueue(18);
   cq.enqueue(11);
   cq.enqueue(7);
   cq.enqueue(13);
   cq.enqueue(9);
   cq.displayCQueue();
   int dq_element = cq.dequeue();
   cout<<"\nDequeued element :: "<<dq_element;
   cout<<"\nAfter dequeueing :-";
   cq.displayCQueue();
   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