logo codesdope

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.

queue

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

head and tail of 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.

enqueue

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

dequeue

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.

head and tail in queue using array

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.

inserting element in queue using 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.

circular order in queue using array

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

tail at 1 in circular order for queue using array

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.

Empty queue using an array

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.

full queue using array

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.

enqueue in queue using array

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.

enqueue at last position in queue using 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 in queue using array

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.

head and tail of empty queue using linked list

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.

queue using linked list

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

enqueue in queue using linked list

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

inserting first node in empty 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.

Everything must be made as simple as possible. But not simpler
- Albert Einstein

Download Our App.
BlogsDope App
Get it on Google Play
Doubt? Ask question
Close

Welcome.please sign up.

Close

Welcome.please login.