—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). —Data structure which implements a first-in, first-out list; e.g. print queue, which contains a list of jobs to be printed in order. —In programming, a queue is a data structure in which elements are removed in the same order they were entered. This is often referred to as FIFO (first in, first out). A Queue can be implemented using arrays and using linked list structure. If you are interested learning Queue using Linked list then read this article.

——In contrast, a stack is a data structure in which elements are removed in the reverse order from which they were entered. This is referred to as LIFO (last in, first out). —The queue data structure is very similar to the stack. —In a stack, all insertions and deletions occur at one end, the top, of the list. —In the queue, as in the stack, all deletions occur at the head of the list. —However, all insertions to the queue occur at the tail of the list.

—Basically, data enters the queue at one end and exits at the other end.

—You get in line at the end and get serviced when you get to the front of the line. —This characteristic gives a queue its first-in, first-out (FIFO) behavior.

Applications

  • —Ticketing counter
  • —Bus stop line
  • —Bank Customers
  • —Printer SPOOL
  • —CPU Scheduling (at times)
  • —And etc.

Queue Operations

  • —Initialize the queue, Q, to be the empty queue
  • —Determine if the queue Q is empty
  • —Determine if the queue Q is full
  • —Insert (enqueue) a new item onto the rear of the queue Q, provided Q is not full
  • —Remove (dequeue) an item from the front of Q, provided Q is nonempty
Similarly, we can define various operations that can perform on queues.
  • isEmpty() – check to see if the queue is empty
  • isFull() – check to see if the queue is full
  • enqueue(elem)  – put the element at the end of the queue
  • dequeue() – take the first element from the queue
  • first() – return the first element in the queue without removing it

Enqueue

—The queue insert is known as enqueue. —After the data has been inserted, this new element becomes the rear of the queue.

Dequeue

—The queue delete operation is known as dequeue. —The data at the front of the queue is returned to the user and deleted from the queue.

Queue implementation using Array

Implementation of a queue requires storage for the data as well as markers (“pointers”) for the front and for the back of the queue.

An array-based implementation would need structure like

  • Items, an array to store the elements of the queue
  • Front, an index to track the front queue element
  • Rear, an index to track the position following last queue element
  • Additions to the queue would result in incrementing Rear.
  • Deletions from the queue would result in incrementing Front.

Example of Queue in C++:

#define length 10
Struct queue
{
  int items[length];
  int front, rear;
};

—insert(q, x) {
  q.items[++q.rear]=x;
}

—remove(q) {
  x=q.items[++q.front];
}

Clearly, we’d run out of space soon!

Solutions to this problem include:

  1. Shifting the elements downward with each deletion.
  2. Viewing array as a circular buffer, i.e. wrapping the end to the front.

Solution 1: Shifting items

—First is do it as we do in real world

  • Check if array is not empty
  • Simply dequeue from the first location of array say array[0] i.e. the zeroth index
  • After dequeue shift all the elements of the array from array[index] to array[index-1]

x=q.items[0];
for(i=0; i<q.rear; i++)
  q.items[i]=q.items[i+1]
q.rear--;
return x;

—Method is costly as we have to move all the elements in the array. —Do we need Front Index in this case? No, Because we are always dequeueing from the first index.

Solution2: Circular Queue

—To avoid the costly operation of copying all the elements again we employ another method called circular queue.

Circular queue

Tagged with: C/C++ languageData structures
 

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.