Queue Data Structures

Similar to stacks, a queue is also an Abstract Data Type or ADT. A queue follows FIFO (First-in, First out) policy. It is equivalent to the queues in our general life. For example, a new person enters a queue at the last and the person who is at the front (who must have entered the queue at first) will be served first.

Similar to a queue of day to day life, in Computer Science also, a new element enters a queue at the last (tail of the queue) and removal of an element occurs from the front (head of the queue).

Similar to the stack, we will implement the queue using a linked list as well as with an array. But let’s first discuss the operations which are done on a queue.

Enqueue → Enqueue is an operation which adds an element to the queue. As stated earlier, any new item enters at the tail of the queue, so Enqueue adds an item to the tail of a queue.

Dequeue → It is similar to the pop operation of stack i.e., it returns and deletes the front element from the queue.

isEmpty → It is used to check whether the queue has any element or not.

isFull → It is used to check whether the queue is full or not.

Front → It is similar to the top operation of a stack i.e., it returns the front element of the queue (but don’t delete it).

Before moving forward to code up these operations, let’s discuss the applications of a queue.

Applications of Queue

Queues are used in a lot of applications, few of them are:

• Queue is used to implement many algorithms like Breadth First Search (BFS), etc.
• It can be also used by an operating system when it has to schedule jobs with equal priority
• Customers calling a call center are kept in queues when they wait for someone to pick up the calls

Queue Using an Array

We will maintain two pointers - tail and head to represent a queue. head will always point to the oldest element which was added and tail will point where the new element is going to be added.

To insert any element, we add that element at tail and increase the tail by one to point to the next element of the array.

Suppose tail is at the last element of the queue and there are empty blocks before head as shown in the picture given below.

In this case, our tail will point to the first element of the array and will follow a circular order.

Initially, the queue will be empty i.e., both head and tail will point to the same location i.e., at index 1. We can easily check if a queue is empty or not by checking if head and tail are pointing to the same location or not at any time.

IS_EMPTY(Q)
  If Q.tail == Q.head
      return True
  return False

Similarly, we will say that if the head of a queue is 1 more than the tail, the queue is full.

IS_FULL(Q)
  if Q.head = Q.tail+1
      return True
  Return False

Now, we have to deal with the enqueue and the dequeue operations.

To enqueue any item to the queue, we will first check if the queue is full or not i.e.,

Enqueue(Q, x)
    if isFull(Q)
        Error “Queue Overflow”
    else
        …

If the queue is not full, we will add the element to the tail i.e, Q[Q.tail] = x.

While adding the element, it might be possible that we have added the element at the last of the array and in this case, the tail will go to the first element of the array.

Otherwise, we will just increase the tail by 1.

Enqueue(Q, x)
  if isFull(Q)
      Error “Queue Overflow”
  else
      Q[Q.tail] = x
      if Q.tail == Q.size
          Q.tail = 1
      else
          Q.tail = Q.tail+1

To dequeue, we will first check if the queue is empty or not. If the queue is empty, then we will throw an error.

Dequeue(Q, x)
    if isEmpty(Q)
        Error “Queue Underflow”
    else
        …

To dequeue, we will first store the item which we are going to delete from the queue in a variable because we will be returning it at last.

Dequeue(Q, x)
    if isEmpty(Q)
        Error “Queue Underflow”
    else
        x = Q[Q.head]
        …

Now, we just have to increase the head pointer by 1. And in the case when the head is at the last element of the array, it will go 1.

Dequeue(Q, x)
  if isEmpty(Q)
      Error “Queue Underflow”
  else
      x = Q[Q.head]
      if Q.head == Q.size
          Q.head = 1
      else
          Q.head = Q.head+1
      return x

• C
• Python
• Java

#include <stdio.h>
#include <stdlib.h>

typedef struct queue {
int head;
int tail;
int size;
int Q[];
}queue;

queue* new_queue(int size) {
queue *q = malloc(sizeof(queue) + size*sizeof(int));

q->head = 1;
q->tail = 1;
q->size = size;

return q;
}

int is_empty(queue *q) {
if(q->tail == q->head)
  return 1;
return 0;
}

int is_full(queue *q) {
if(q->head == q->tail+1)
  return 1;
return 0;
}

void enqueue(queue *q, int x) {
if(is_full(q)) {
  printf("Queue Overflow\n");
}
else {
  q->Q[q->tail] = x;
  if(q->tail == q->size)
    q->tail = 1;
  else
    q->tail = q->tail+1;
}
}

int dequeue(queue *q) {
if(is_empty(q)) {
  printf("Underflow\n");
  return -1000;
}
else {
  int x = q->Q[q->head];
  if(q->head == q->size) {
    q->head = 1;
  }
  else {
    q->head = q->head+1;
  }
  return x;
}
}

void display(queue *q) {
int i;
for(i=q->head; i<q->tail; i++) {
  printf("%d\n",q->Q[i]);
  if(i == q->size) {
    i = 0;
  }
}
}

int main() {
queue *q = new_queue(10);
enqueue(q, 10);
enqueue(q, 20);
enqueue(q, 30);
enqueue(q, 40);
enqueue(q, 50);
display(q);

printf("\n");

dequeue(q);
dequeue(q);
display(q);

printf("\n");

enqueue(q, 60);
enqueue(q, 70);
display(q);
return 0;
}

class Queue:
def __init__(self, size):
  self.head = 1
  self.tail = 1
  self.Q = [0]*(size)
  self.size = size

def is_empty(self):
  if self.tail == self.head:
    return True
  return False

def is_full(self):
  if self.head == self.tail+1:
    return True
  return False

def enqueue(self, x):
  if self.is_full():
    print("Queue Overflow")
  else:
    self.Q[self.tail] = x
    if self.tail == self.size:
      self.tail = 1
    else:
      self.tail = self.tail+1

def dequeue(self):
  if self.is_empty():
    print("Underflow")
  else:
    x = self.Q[self.head]
    if self.head == self.size:
      self.head = 1
    else:
      self.head = self.head+1
    return x

def display(self):
  i = self.head
  while(i < self.tail):
    print(self.Q[i])
    if(i == self.size):
      i = 0
    i = i+1

if __name__ == '__main__':
q = Queue(10)
q.enqueue(10)
q.enqueue(20)
q.enqueue(30)
q.enqueue(40)
q.enqueue(50)
q.display()

print("")

q.dequeue()
q.dequeue()
q.display()

print("")

q.enqueue(60)
q.enqueue(70)
q.display()

class Queue {
public int head;
public int tail;
public int size;
public int[] Q;

public Queue(int size) {
  this.head = 1;
  this.tail = 1;
  this.Q = new int[size];
}

public boolean isEmpty() {
  if(this.tail == this.head)
    return true;
  return false;
}

public boolean isFull() {
  if(this.head == this.tail+1)
    return true;
  return false;
}

public void enqueue(int x) {
  if(isFull()) {
    System.out.println("Queue Overflow");
  }
  else {
    this.Q[this.tail] = x;
    if(this.tail == this.size)
      this.tail = 1;
    else
      this.tail = this.tail+1;
  }
}

public int dequeue() {
  if(isEmpty()) {
    System.out.println("Underflow");
    return -1000;
  }
  else {
    int x = this.Q[this.head];
    if(this.head == this.size) {
      this.head = 1;
    }
    else {
      this.head = this.head+1;
    }
    return x;
  }
}

public void display() {
  int i;
  for(i=this.head; i<this.tail; i++) {
    System.out.println(this.Q[i]);
    if(i == this.size) {
      i = 0;
    }
  }
}

public static void main(String[] args) {
  Queue q = new Queue(10);
  q.enqueue(10);
  q.enqueue(20);
  q.enqueue(30);
  q.enqueue(40);
  q.enqueue(50);
  q.display();

  System.out.println("");

  q.dequeue();
  q.dequeue();
  q.display();

  System.out.println("");

  q.enqueue(60);
  q.enqueue(70);
  q.display();
}
}

We have covered all the major operations while implementing a queue using an array. Let’s move ahead and implement these operations with a queue made from a linked list.

Queue Using Linked List

As we know that a linked list is a dynamic data structure and we can change the size of it whenever it is needed. So, we are not going to consider that there is a maximum size of the queue and thus the queue will never overflow. However, one can set a maximum size to restrict the linked list from growing more than that size.

As told earlier, we are going to maintain a head and a tail pointer to the queue. In the case of an empty queue, head will point to NULL.

IS_EMPTY(Q)
  if Q.head == null
      return True
  return False

We will point the head pointer to the first element of the linked list and the tail pointer to the last element of it as shown in the picture given below.

The enqueue operation simply adds a new element to the last of a linked list.

However, if the queue is empty, we will simply make the new node head and tail of the queue.

ENQUEUE(Q, n)
  if IS_EMPTY(Q)
      Q.head = n
      Q.tail = n
  else
      Q.tail.next = n
      Q.tail = n

To dequeue, we need to remove the head of the linked list. To do so, we will first store its data in a variable because we will return it at last and then point head to its next element.

x = Q.head.data
Q.head = Q.head.next
return x

We will execute the above codes when the queue is not empty. If it is, we will throw the "Queue Underflow" error.

DEQUEUE(Q, n)
  if IS_EMPTY(Q)
      Error "Queue Underflow"
  else
      x = Q.head.data
      Q.head = Q.head.next
      return x

• C
• Python
• Java

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
int data;
struct node *next;
}node;

typedef struct linked_list {
struct node *head;
struct node *tail;
}queue;

//to make new node
node* new_node(int data) {
node *z;
z = malloc(sizeof(struct node));
z->data = data;
z->next = NULL;

return z;
}

//to make a new queue
queue* new_queue() {
queue *q = malloc(sizeof(queue));
q->head = NULL;
q->tail = NULL;

return q;
}

void traversal(queue *q) {
node *temp = q->head; //temporary pointer to point to head

while(temp != NULL) { //iterating over queue
  printf("%d\t", temp->data);
  temp = temp->next;
}

printf("\n");
}

int is_empty(queue *q) {
if(q->head == NULL)
  return 1;
return 0;
}

void enqueue(queue *q, node *n) {
if(is_empty(q)) {
  q->head = n;
  q->tail = n;
}
else {
  q->tail->next = n;
  q->tail = n;
}
}

int dequeue(queue *q) {
if(is_empty(q)) {
  printf("Underflow\n");
  return -1000;
}
else {
  int x = q->head->data;
  node *temp = q->head;
  q->head = q->head->next;
  free(temp);
  return x;
}
}

int main() {
queue *q = new_queue();

node *a, *b, *c;
a = new_node(10);
b = new_node(20);
c = new_node(30);

dequeue(q);
enqueue(q, a);
enqueue(q, b);
enqueue(q, c);

traversal(q);
dequeue(q);
traversal(q);


return 0;
}

class Node():
def __init__(self, data):
  self.data = data
  self.next = None

class Queue():
def __init__(self):
  self.head = None
  self.tail = None

def traversal(q):
temp = q.head #temporary pointer to point to head

a = ''
while temp != None: #iterating over queue
  a = a+str(temp.data)+'\t'
  temp = temp.next

print(a)

def is_empty(q):
if q.head == None:
  return True
return False

def enqueue(q, n):
if is_empty(q): #empty
  q.head = n
  q.tail = n
else:
  q.tail.next = n
  q.tail = n

def dequeue(q):
if is_empty(q):
  print("Queue Underflow")
  return -1000
else:
  x = q.head.data
  temp = q.head
  q.head = q.head.next
  del temp
  return x

if __name__ == '__main__':
q = Queue()

a = Node(10)
b = Node(20)
c = Node(30)

dequeue(q)
enqueue(q, a)
enqueue(q, b)
enqueue(q, c)

traversal(q)
dequeue(q)
traversal(q)

class Node {
public int data;
public Node next;

public Node(int data) {
  this.data = data;
  next = null;
}
}

class Queue {
public Node head;
public Node tail;

public Queue() {
  head = null;
  tail = null;
}

public void traversal() {
  Node temp = this.head; //temporary pointer to point to head

  while(temp != null) { //iterating over queue
    System.out.print(temp.data+"\t");
    temp = temp.next;
  }

  System.out.println("");
}

public boolean isEmpty() {
  if(this.head == null)
    return true;
  return false;
}

public void enqueue(Node n) {
  if(isEmpty()) {
    this.head = n;
    this.tail = n;
  }
  else {
    this.tail.next = n;
    this.tail = n;
  }
}

public int dequeue() {
  if(this.isEmpty()) {
    System.out.println("Queue Underflow\n");
    return -1000;
  }
  else {
    int x = this.head.data;
    Node temp = this.head;
    this.head = this.head.next;
    return x;
  }
}
}

class QueueMain {
public static void main(String[] args) {
  Queue q = new Queue();

  Node a, b, c;
  a = new Node(10);
  b = new Node(20);
  c = new Node(30);

  q.dequeue();
  q.enqueue(a);
  q.enqueue(b);
  q.enqueue(c);

  q.traversal();
  q.dequeue();
  q.traversal();
}
}

We used a singly linked list to make both stack and queue. We could have made the operations of both the data structures better by using doubly linked list because of the access of the previous node which would prevent us from iterating the entire list in many cases. You must try to make both of these data structures using doubly linked lists on your own.

So, you have studied about linked lists, stacks and queues. In the next chapters, you will learn about one more important data structure - trees.

• Queue in C
• Making a queue using linked list in C
• Making a queue using an array in C