Queues

What is Queue?

“A queue is a linear data structure into which items can only be inserted at one end and removed from the other.”

A queue is a FIFO (First In First Out) structure. Means, the 1^st inserted element will be removed 1^st.

Queue in Real Life

We queue up while depositing a utility bill or purchasing a ticket. The person who has joined the queue first is served first.

If the requirement is to serve the people in some sort of priority order, there is a separate data structure that supports priorities.

Queue Operations

The queue data structure supports the following operations.

Queue using Linked List

Following are the key points associated with the linked list implementation.

• 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.

After dequeue() is called once:

Queue after enqueue(9) call:

Queue using Linked List Methods

dequeue()

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

enqueue()

void enqueue(int x)
{
	Node* newNode = new Node();
	newNode->set(x);
	newNode->setNext(NULL);
	rear->setNext(newNode);
	rear = newNode;
}

front()

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

isEmpty()

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

Queue using Array

If we use an array to hold the queue elements, both insertions and removal at the front (start) of the array are expensive. This is due to the fact that we may have to shift up to “n” elements.

By calling enqueue(6) and enqueue(8):

Now, let’s call dequeue():

dequeue() for the 2^nd time:

Now, by calling enqueue(9) and enqueue(12):

Problems

• First: Array has attained the size limit. And we know that we’ll face the problem with its limited size.
• Second: As we called dequeue() method, first locations of the array are empty. Which causes the useless memory consumption.

Solution

If we allow queue to wrap around, the problems can be avoided.

Circularly Array helps to achieve the purpose of wrapping around the queue.

Queue using Array Methods

enqueue()

Perform enqueue(21):

enqueue(7):

void enqueue( int x)
{
	rear = (rear + 1) % size;   // rear will be between 0 and 7 in given case.
	array[rear] = x;
	noElements = noElements + 1; // incrementing the no. of elements.
}

isFull()

int isFull()
{
	return noElements == size;
}

isEmpty()

int isEmpty() {
	return noElements == 0;
}

dequeue()

Call the dequeue() method:

int dequeue()
{
	int x = array[front];
	front = (front + 1) % size;
	noElements = noElements - 1;
	return x;
}

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, Flight Simulator etc. Each object and action in the simulation has a counterpart in the real world.

REFERENCE: CS301 Handouts (page 84 to 92)