—A queue is an ordered collection of items from which items may be deleted at one end (called the front of the queue) and into which items may be inserted at the other end  (called the rear of the queue). A Queue can be implemented using arrays and using linked list structure. In this article, we’ll discuss first a simple comparison between implementing Queue using Arrays vs Queues using Linked List. Then we’ll move to discuss implementation of Queues using Linked List. If you are interested in learning queue using Arrays then read this article first.

Implementing queues using arrays

  • —Simple implementation
  • —The size of the queue must be determined when the object is declared
  • —Space is wasted if we use less elements
  • —We cannot “enqueue” more elements than the array can hold

Implementing queues using linked lists

  • —Allocate memory for each new element dynamically
  • —Link the queue elements together
  • —Use two pointers, qFront and qRear, to mark the front and rear of the queue

Queue class specification

struct Node{
	char value;
	Node *next;

class QueueType {
    void MakeEmpty();
    bool IsEmpty() const;
    bool IsFull() const;
    void Enqueue(ItemType);
    void Dequeue(ItemType&);
    Node  *qFront;
    Node  * qRear;

Enqueuing (non-empty queue)

—We need to make qFront point to the new node also

Function Enqueue

void QueueType::Enqueue(Node newItem)
 Node  *newNode;

 newNode = new Node;
 newNode->info = newItem;
 newNode->next = NULL;
 if(qRear == NULL)
   qFront = newNode;
   qRear->next = newNode;
 qRear = newNode;

Dequeueing (the queue contains more than one element)

—We need to reset qRear to NULL also

Function Dequeue

void QueueType::Dequeue(Node& item)
 Node  *tempPtr;

 tempPtr = qFront;
 item = qFront->info;
 qFront = qFront->next;
 if(qFront == NULL)
   qRear = NULL;
 delete tempPtr;

Other Queue functions

Queue Type

void QueueType::QueueType()
 qFront = NULL;
 qRear = NULL;


void QueueType::MakeEmpty()
 Node  *tempPtr;

 while(qFront != NULL) {
   tempPtr = qFront;
   qFront = qFront->next;
   delete tempPtr;


bool QueueType::IsEmpty() const
 return(qFront == NULL);


bool QueueType::IsFull() const
 Node  *ptr;

 ptr = new Node;
 if(ptr == NULL)
   return true;
 else {
   delete ptr;
   return false;


void QueueType::~QueueType()
Tagged with: C/C++ languageClassesObject Oriented

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.