Queue implementation using linked list in data structure
Queue Data StructuresSimilar 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. Show 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 lets 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 dont delete it). Before moving forward to code up these operations, lets discuss the applications of a queue. Applications of QueueQueues are used in a lot of applications, few of them are:
Queue Using an ArrayWe 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. Similarly, we will say that if the head of a queue is 1 more than the tail, the queue is full. 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 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+1To 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) 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) 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.
#include 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. Lets move ahead and implement these operations with a queue made from a linked list. Queue Using Linked ListAs 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. 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. 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 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
#include 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 PREV NEXT # Further Readings
|
