A stack is LIFO (Last-In First Out) structure. In contrast, a queue is a FIFO (First-In First-Out ) structure. In a FIFO data structure, the first element added to the queue will be the first one to be removed. This is equivalent to the requirement that once a new element is added, all elements that were added before have to be removed before the new element can be removed. A queue is a linear structure for which items can be only inserted at one end and removed at another end.

A Queue can have following operations:

  • Enqueue(X) –   Place X at the rear of the   queue.
  • Dequeue() –  Remove the front element and   return it.
  • Front() –  Return front element without   removing it.
  • IsEmpty()  –  Return TRUE if queue is   empty, FALSE otherwise

Implementation of Queue

1. Implementation using Linked List

Usually Queues are implemented using linked List. Insert works in constant time for either end of a linked list. Remove works in constant time only. Seems best that head of the linked list be the front of the queue so that all removes will be from the front. Inserts will be at the end of the list. Consider the following diagram for implementation of Queue using linked list.

Implementation in C++ using Linked List

int dequeue()
    int x = front->get();
    Node* p = front;
    front = front->getNext();
    delete p;
    return x;

void enqueue(int x)
    Node* newNode = new Node();
    rear = newNode;

int front()
    return front->get();

int isEmpty()
    return ( front == NULL );

Implementation using Array 

If we use an array to hold queue elements, both insertions and removal at the front (start) of the array are expensive. This is because we may have to shift up to “n” elements. For the stack, we needed only one end; for queue we need both. To get around this, we will not shift upon removal of an element.

We have inserts and removal running in constant time but we created a new problem. We cannot insert new elements even though there are two places available at the start of the array.
Solution: allow the queue to “wrap around”. Basic idea is to picture the array as a circular array as show below.
Implementation in C++ using Arrays
void enqueue(int x)
    rear = (rear+1)%size;
    array[rear] = x;
	  noElements = noElements+1;
int dequeue()
    int x = array[front];
	  front = (front+1)%size;
	  noElements = noElements-1;
	  return x;
int isFull()
    return noElements == size;

int isEmpty()
	  return noElements == 0;

Use of Queues

  • Out of the numerous uses of the queues, one of the most useful is simulation.
  • A simulation program attempts to model a real-world phenomenon.
  • Many popular video games are simulations, e.g., SimCity, FlightSimulator
  • Each object and action in the simulation has a counterpart in real world.
  • If the simulation is accurate, the result of the program should mirror the results of the real-world event.
  • Thus it is possible to understand what occurs in the real-world without actually observing its occurrence.
Simulation of a Bank
Let us look at an example. Suppose there is a bank with four tellers. A customer enters the bank at a specific time (t1) desiring to conduct a transaction. Any one of the four tellers can attend to the customer. The transaction (withdraw, deposit) will take a certain period of time (t2). If a teller is free, the teller can process the customer’s transaction immediately and the customer leaves the bank at t1+t2.
Tagged with: C/C++ languageData structures

One Response to Queue Implementation in C++

  1. Iqbal says:

    i want to ask you,
    how about if rear=max, so the count of front, return to front(0)
    ex: max = 5. i have queue 1 2 3 4 5. dequeue 1&2. so the result is 3 4 5.
    i want to take front(3) return to front(0). front(4) return to front(1). etc.
    how the implementation. sorry about my english

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>


Looking for something?

Use the form below to search the site:

Still not finding what you're looking for? Drop a comment on a post or contact us so we can take care of it!

Related News Feeds

Set your Twitter account name in your settings to use the TwitterBar Section.