Queue Data Structure

A Queue is a linear data structure that follows the First In, First Out (FIFO) principle, where elements are inserted at the rear and removed from the front.

Queue Data Structure

The term "queue" is well-known; for example, we often stand in a queue while waiting for our turn. Railways are one of the places where people stand in long queues to buy tickets.

One important aspect of queues is their intuitive nature: the first person to join the queue is the first to be served. This principle is known as FIFO (First In First Out), meaning the first element added to the queue will be the first one to be removed. In contrast, stacks operate under LIFO (Last In First Out) principles.

Follow the illustration below to get a visual understanding of a queue.

example

In stacks, we maintained just one end (the head) for both insertion and deletion, while the other end was closed. In queues, however, we must manage both ends: insertion occurs at one end, and deletion happens at the other.

Queue ADT

Data:

To create a queue, we need two pointers: one pointing to the insertion end to indicate where the new element will be inserted, and the other pointing to the deletion end, which holds the address of the element that will be deleted first. Additionally, we need storage to hold the elements themselves.

Methods:

Here are some basic methods we would want to have in queues:

  1. enqueue( ): to insert an element into the queue.
example
  1. dequeue( ): to remove an element from the queue
example

  1. firstVal(): to return the value at the first position.

  2. lastVal(): to return the value at the last position.

  3. peek(position): to return the element at a specific position.

  4. isempty() / isfull(): to determine whether the queue is empty or full, helping us perform efficient enqueue and dequeue operations.

This concludes our abstract data type for queues. While the list of methods could be longer, this is sufficient for our current needs.

A queue can be implemented in various ways, including using arrays, linked lists, or even stacks. Moreover, a queue has broader applications beyond ticket counters or shops/malls, which you'll discover as we proceed.

A queue is a collection of elements with certain operations that follow the FIFO (First In First Out) discipline: we insert at one end and delete from the other.