Introduction to Linked Queues

In one of the article Introduction
to Linked Stacks, I said that representing data structures such as
Stacks and Queues as arrays had one major problem that it can’t have more
than a predefined number of elements. To overcome this we used linked lists
to represent stacks. In this article we’ll use linked lists to represent
queues.

Below are some graphics that illustrate the addition and retrieval of elements
to and from the linked queue.

FIG.: Addition of data to the linked queue

FIG.: Retrieval of elements from the linked
queue

I don’t think there is anything more that needs to be discussed, so let’s
have a look at the example program:

  // -- Linked Queues --
  // C++ Example Program to
  // illustrate the representation
  // of queues as linked lists
  #include<iostream.h>

  // node class, this will
  // represent the nodes or elements
  // of the linked queues
  class node
  {
   public:
     int info;
     node *link;
  };

  // declare global objects
  node *front=NULL;
  node *rear=NULL;

  // function prototypes
  void add(int);
  int retrieve();
  void free();

  void main(void)
  {
   int ch=0,num;

   while(ch!=3)
   {
    cout<<"1> Add";
    cout<<"\n2> Retrieve";
    cout<<"\n3> Quit\n";

    cin>>ch;

    switch(ch)
    {
     case 1:
       cout<<"enter element:";
       cin>>num;

       add(num);
       break;

     case 2:
       cout<<"\n\Retrieved: ";
       cout<<retrieve();
       cout<<"\n\n";
       break;
    }
   }

   // free up the memory
   free();
  }

  // function to add new nodes
  // to the linked queue
  void add(int inf)
  {
   node *temp;

   temp=new node;

   temp->info=inf;
   temp->link=NULL;

   if(front==NULL)
   {
    rear=front=temp;
    return;
   }

   rear->link=temp;
   rear=rear->link;
  }

  // function to retrieve
  // data from the linked
  // queue
  int retrieve()
  {
   node *temp;
   int inf;

   if(front==NULL)
   {
    cout<<"Queue Empty!\n";
    return NULL;
   }

   inf=front->info;
   temp=front;
   front=front->link;

   delete temp;
   return inf;
  }

  // free the dynamic memory
  // allocated in the form of
  // nodes of the linked queue
  void free(void)
  {
   // below is a bit confusing
   // part.
   // here all the nodes that
   // we have allocated are
   // being freed up
   node temp;
   while(front!=NULL)
   {
    // store the next node
    // to the one being deleted
    temp=*front;
    // delete the node
    delete front;

    // retrieve the next node
    // to be deleted
    front=temp.link;
   }
  }

Good-Bye!

Related Articles:

• 
  

  Introduction
  to Linked Stacks

  
  


• 
  

  Data
  Structures: Introduction to Stacks

  
  


• 
  

  
  Data Structures: Introduction to Queues

  
  


• 
  

  Introduction
  to Linked Lists

  
  

Data Structures: Introduction to Queues

Queue is a linear data structure in which data can be added to one end and
retrieved from the other. Just like the queue of the real world, the data that
goes first into the queue is the first one to be retrieved. That is why queues
are sometimes called as First-In-First-Out data structure.

In case of queues, we saw that data is inserted both from one end but in case
of Queues; data is added to one end (known as REAR) and retrieved from the other
end (known as FRONT).

The data first added is the first one to be retrieved while in case of queues
the data last added is the first one to be retrieved.

A few points regarding Queues:

1. 
   

   Queues: It is a linear data structure; linked lists and
   arrays can represent it. Although representing queues with arrays have its
   shortcomings but due to simplicity, we will be representing queues with
   arrays in this article.

   
   


2. 
   

   Rear: A variable stores the index number in the array
   at which the new data will be added (in the queue).

   
   


3. 
   

   Front: It is a variable storing the index number in the
   array where the data will be retrieved.

   
   

Let us have look at the process of adding and retrieving data in the queue
with the help of an example.

Suppose we have a queue represented by an array queue [10], which is empty
to start with. The values of front and rear variable upon different actions
are mentioned in {}.

queue [10]=EMPTY {front=-1, rear=0}

add (5)

Now, queue [10] = 5 {front=0, rear=1}

add (10)

Now, queue [10] = 5, 10 {front=0, rear=2}

retrieve () [It returns 5]

Now, queue [10] = 10 {front=1, rear=2}

retrieve () [now it returns 10]

Now, queue [10] is again empty {front=-1, rear=-1}

In this way, a queue like a stack, can grow and shrink over time.

Now have a look at the following example program that illustrates all this
stuff:

  // -- A Queue Class in C++ --
  // example program in C++ to
  // illustrate queues represented
  // by arrays
  #include<iostream.h>

  // macro to hold the max
  // number of elements
  // in the queue
  #define MAX 10

  // queue class
  class queue
  {
   int arr[MAX];
   int front, rear;
 
  public:

   void add(int);
   int retrieve(void);
   queue();
  };
  // queue class ends

  // member functions
  queue::queue()  
  {
   // initialize index
   // variables
   front=-1;
   rear=0;
  }

  void queue::add(int data)
  {
   if(rear==MAX-1)
   {
    cout<<"QUEUE FULL!";
    return;
   }

   arr[rear]=data;
   // increase index
   // variable
   rear++;

   if(front=-1)
   front=0;
  }

  int queue::retrieve()
  {
   int data;
 
   if(front==-1)
   {
    cout<<"QUEUE EMPTY!";
    return NULL;
   }

   data=arr[front];
   arr[front]=0;
  
   // if both index variables
   // point to the same location
   // then start afresh
   if(front==rear-1)
   {
    front=-1;
    rear=0;
   }
   else
    front++;

   return data;
  }
  // member functions ends

  void main(void)
  {
   queue obj;
   int ch;
   int num;

   while(ch!=3)
   {
    cout<<"1> ADD";
    cout<<"\n2> RETRIVE";
    cout<<"\n3> QUIT\n";

    cin>>ch;

    switch(ch)
    {
     case 1:
     cout<<"enter element:";
     cin>>num;

     obj.add(num);
     break;

     case 2:
     cout<<"\n\nRetrieved: ";
     cout<<obj.retrieve();
     cout<<"\n\n";
     break;
    }
   }
  }

Good-Bye

Please do check back for updates!

Related Articles:

• 
  

  Data
  Structures: Introduction to Stacks