Queues

A queue is a container of objects (a linear collection) that are inserted and removed according to the first-in first-out (FIFO) principle. An excellent example of a queue is a line of students in the food court of the UC. New additions to a line made to the back of the queue, while removal (or serving) happens in the front. In the queue only two operations are allowed enqueue and dequeue. Enqueue means to insert an item into the back of the queue, dequeue means removing the front item. The picture demonstrates the FIFO access.The difference between stacks and queues is in removing. In a stack we remove the item the most recently added; in a queue, we remove the item the least recently added.

Implementation

In the standard library of classes, the data type queue is an adapter class, meaning that a queue is built on top of other data structures. The underlying structure for a queue could be an array, a Vector, an ArrayList, a LinkedList, or any other collection. Regardless of the type of the underlying data structure, a queue must implement the same functionality. This is achieved by providing a unique interface.

interface QueueInterface‹AnyType>
{
   public boolean isEmpty();
   public AnyType getFront();
   public AnyType dequeue();
   public void enqueue(AnyType e);
   public void clear();
}

Each of the above basic operations must run at constant time O(1). The following picture demonstrates the idea of implementation by composition.

C++ Implementation using array

class queue
{
              int queue1[5];
              int rear,front;
      public:
              queue()
                {
                     rear=-1;
                     front=-1;
                }
              void insert(int x)
               {
                   if(rear >  4)
                    {
                       cout <<"queue over flow";
                       front=rear=-1;
                       return;
                    }
                    queue1[++rear]=x;
                    cout <<"inserted" <<x;
               }
              void delet()
               {
                   if(front==rear)
                     {
                         cout <<"queue under flow";
                         return;
                     }
                     cout <<"deleted" <<queue1[++front];
                }
              void display()
               {
                   if(rear==front)
                     {
                          cout <<" queue empty";
                          return;
                     }
                   for(int i=front+1;i<=rear;i++)
                   cout <<queue1[i]<<" ";
               }
};

 C++ Implementation using Linked List

struct node
{
    int info;
    node *next;
};

class Queue
{
    private:
        node *rear;
        node *front;
    public:
        Queue();
        void enqueue();
        void dequeue();
        void display();
};

Queue::Queue()
{
    rear = NULL;
    front = NULL;
}

void Queue::enqueue()
{
    int data;
    node *temp = new node;
    cout<<"Enter the data to enqueue: ";     
    cin>>data;
    temp->info = data;
    temp->next = NULL;
    if(front == NULL)
    {
        front = temp;
    }
    else
    {
        rear->next = temp;
    }
    rear = temp;
}

void Queue::dequeue()
{
    node *temp = new node;
    if(front == NULL)
    {
        cout<<"\nQueue is Emtpty\n";     
    }     
    else     
    {         
        temp = front;         
        front = front->next;
        cout<<"The data Dequeued is "<info;
        delete temp;
    }
}

void Queue::display()
{
    node *p = new node;
    p = front;
    if(front == NULL)
    {
        cout<<"\nNothing to Display\n";
    }
    else
    {
        while(p!=NULL)
        {
            cout<<endl<<info;
            p = p->next;
        }
    }
}

Types of Queues

Applications

This search is described by looking at how the search tree (representing all the possible paths from the start) will be traversed.

Breadth-First Search with a Queue

In breadth-first search we explore all the nearest possibilities by finding all possible successors and enqueue them to a queue.

  • Create a queue
  • Create a new choice point
  • Enqueue the choice point onto the queue
  • while (not found and queue is not empty)
    • Dequeue the queue
    • Find all possible choices after the last one tried
    • Enqueue these choices onto the queue
  • Return