Queue in Data Structure
What is Queue?
A queue is a linear list of elements in which deletions can take place only at one end called the front, and insertions can take place only at the end called the rear. The queue is a First In First Out type of data structure (FIFO), the terms FRONT and REAR are used in describing a linear list only when it is implemented as a queue.
In computer science queues are used in multiple places e.g. in a time-sharing system program with the same priority from a queue waiting to be executed. A queue is a non-primitive linear data structure. it is a homogeneous collection of elements.
The process to add an element into a queue is called Enqueue and the process of removal of an element from the queue is called Dequeue.
Basic features of Queue
- Like stack, queue is also an ordered list of elements of similar data types.
- Queue is a FIFO( First in First Out ) structure.
- Once a new element is inserted into the Queue, all the elements inserted before the new element in the queue must be removed, to remove the new element.
- peek() function is used to return the value of first element without dequeuing it.
Implementation of Queue Data Structure
The queue can be implemented in two ways :
- Static implementation (using arrays)
- Dynamic implementation (using linked list)
Basics operations on the stack
- Enqueue
- Dequeue
Enqueue operation:
Algorithm for INSERTION operation
- Check for the overflow condition.
- Check if the queue is empty.
- If the queue is empty, then both FRONT and REAR are set to zero, so that the new value can be stored at the 0th location. Otherwise, if the queue already has some values, then REAR is incremented so that it points to the next location in the array.
- The value is stored in the queue at the location pointed by REAR.
Queue_Insert (Queue, Size, Front, Rear, x)
{
if (Rear == Size - 1)
Print Over flow
if (Front = = -1)
Set Front = 0 && Rear = 0
Else
Rear = R + 1
Queue[Rear] = x
EXIT
}Dequeue operation:
Algorithm for DELETION operation
- Check for underflow condition. An underflow occurs if FRONT = –1 or FRONT > REAR.
- If queue has some values, then FRONT is incremented so that it now points to the next value in the queue.
Queue_DELETE (Queue, Size, Front, Rear)
{
if (Front == - 1)
Print Under flow
x = Queue [Front]
if (Front = = Rear)
Set Front = -1 && Rear = -1
Else
Front = Front + 1
EXIT
}Code:
- C++ Code
#include <bits/stdc++.h>
using namespace std;
class Queue {
int front, rear, capacity;
int* queue;
public:
Queue(int val)
{
front = rear = 0;
capacity = val;
queue = new int;
}
Queue() { delete[] queue; }
void queueEnqueue(int data)
{
if (capacity == rear) {
cout<<"Queue is full";
return;
}
else {
queue[rear] = data;
rear++;
}
return;
}
void queueDequeue()
{
if (front == rear) {
cout<<"Queue is empty"<<endl;
return;
}
else {
for (int i = 0; i < rear - 1; i++) {
queue[i] = queue[i + 1];
}
rear--;
}
return;
}
void queueDisplay()
{
int i;
if (front == rear) {
cout<<("Queue is Empty");
return;
}
cout<<endl;
for (i = front; i < rear; i++) {
cout<<queue[i]<<endl;
}
return;
}
void queueFront()
{
if (front == rear) {
cout<<"Queue is Empty";
return;
}
cout<<"Front Element is: "<<queue[front];
return;
}
};
int main()
{
Queue q(4);
q.queueDisplay();
q.queueEnqueue(20);
q.queueEnqueue(30);
q.queueEnqueue(40);
q.queueEnqueue(50);
q.queueDisplay();
q.queueEnqueue(60);
q.queueDisplay();
q.queueDequeue();
q.queueDequeue();
printf("after two node deletion");
q.queueDisplay();
q.queueFront();
return 0;
}Output:
Queue is Empty
20
30
40
50
Queue is full
20
30
40
50
after two node deletion
40
50
Front Element is: 40
- Java Code
import java.util.*;class Queue {
private static int front, rear, capacity;
private static int queue[]; Queue(int val)
{
front = rear = 0;
capacity = val;
queue = new int[capacity];
} static void queueEnqueue(int data)
{
if (capacity == rear) {
System.out.println("Queue is full");
return;
} else {
queue[rear] = data;
rear++;
}
return;
}
static void queueDequeue()
{
if (front == rear) {
System.out.println("Queue is empty");
return;
} else {
for (int i = 0; i < rear - 1; i++) {
queue[i] = queue[i + 1];
}
if (rear < capacity)
queue[rear] = 0;
rear--;
}
return;
}
static void queueDisplay()
{
int i;
if (front == rear) {
System.out.println("Queue is Empty");
return;
}
for (i = front; i < rear; i++) {
System.out.printf("%d ", queue[i]);
}
System.out.println();
return;
}
static void queueFront()
{
if (front == rear) {
System.out.println("Queue is Empty");
return;
}
System.out.print("Front Element is: "+queue[front]);
return;
}
}public class StaticQueueinjava {
public static void main(String[] args)
{
Queue q = new Queue(4);
q.queueDisplay();
q.queueEnqueue(20);
q.queueEnqueue(30);
q.queueEnqueue(40);
q.queueEnqueue(50);
q.queueDisplay();
q.queueEnqueue(60); q.queueDisplay(); q.queueDequeue();
q.queueDequeue();
System.out.println("after two node deletion"); q.queueDisplay(); q.queueFront();
}
}
Output:
Queue is Empty
20 30 40 50
Queue is full
20 30 40 50
after two node deletion
40 50
Front Element is: 40
Complexity Analysis of Queue Operations
Just like Stack, in the case of a Queue too, we know exactly, on which position a new element will be added and from where an element will be removed, hence both these operations require a single step.
- Enqueue: O(1)
- Dequeue: O(1)
- Size: O(1)
Implement Queue Using Array
Problem Statement: Implement Queue Data Structure using Array with all functions like pop, push, top, size, etc.
Example:
Input: push(4)
push(14)
push(24)
push(34)
top()
size()
pop()Output: The element pushed is 4
The element pushed is 14
The element pushed is 24
The element pushed is 34
The peek of the queue before deleting any element 4
The size of the queue before deletion 4
The first element to be deleted 4
The peek of the queue after deleting an element 14
The size of the queue after deleting an element 3
Solution
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Intuition:
The intuition is to fill the array in a circular manner, (ie) after popping from the front, rather than moving all the elements towards the front. We can have 2 variables to keep track of the start and end indexes of the sequence. Mod addition is done to handle boundary conditions.
Approach:
The basic approach is to maintain two variables to point to the START and END of the filled elements in the array. START pointer is used to point to the starting index of the elements and the same case for the END pointer(ending index). Initially, both have value -1(indicating empty queue).
First, let’s see the implementation of the push function. Push basically inserts a new element at the end. So only the END variable is going to be incremented.
Corner case 1: What if we have no empty places in the array? So, first check that, if we don’t have we exit, in the other case we increment the START variable and put the new element.
Corner case 2: What if END reaches the last index? We are doing mod with addition. So, END goes back to index 0([0-(n-1)] will always be the range for END).
Second, let us see the pop function. In Queue pop removes and returns the front element. So, START needs to be modified. The general approach is to copy the current element pointed by START and increase the START variable to the next index.
Corner case 3: What if the Queue is empty? That’s why we are checking the START variable. If it is -1, then the queue is empty, we just exit.
Corner case 4: What if START goes out of bound? As done for END, mod addition comes to the rescue.
Corner case 5: What happens after popping the last element? We check this state with the currSize variable. Queue returns to the initial state, both START and END are set to -1.
Third, let’s see the top function. It behaves more like a pop function. We need to return the element pointed by the START variable. Since we are not actually removing any element, it’s fine to ignore corner cases 4 and 5.
That’s all about the Queue class implementation. In the main function, we just initialize the Queue class to check all corner cases.
Code:
- Java Code
class Queue {
private int arr[];
private int start, end, currSize, maxSize;
public Queue() {
arr = new int[16];
start = -1;
end = -1;
currSize = 0;
}
public Queue(int maxSize) {
this.maxSize = maxSize;
arr = new int[maxSize];
start = -1;
end = -1;
currSize = 0;
}
public void push(int newElement) {
if (currSize == maxSize) {
System.out.println("Queue is full\nExiting...");
System.exit(1);
}
if (end == -1) {
start = 0;
end = 0;
} else
end = (end + 1) % maxSize;
arr[end] = newElement;
System.out.println("The element pushed is " + newElement);
currSize++;
}
public int pop() {
if (start == -1) {
System.out.println("Queue Empty\nExiting...");
System.exit(1);
}
int popped = arr[start];
if (currSize == 1) {
start = -1;
end = -1;
} else
start = (start + 1) % maxSize;
currSize--;
return popped;
}
public int top() {
if (start == -1) {
System.out.println("Queue is Empty");
System.exit(1);
}
return arr[start];
}
public int size() {
return currSize;
}
}
public class TUF {
public static void main(String args[]) {
Queue q = new Queue(6);
q.push(4);
q.push(14);
q.push(24);
q.push(34);
System.out.println("The peek of the queue before deleting any element " + q.top());
System.out.println("The size of the queue before deletion " + q.size());
System.out.println("The first element to be deleted " + q.pop());
System.out.println("The peek of the queue after deleting an element " + q.top());
System.out.println("The size of the queue after deleting an element " + q.size());
}
}Output:
The element pushed is 4
The element pushed is 14
The element pushed is 24
The element pushed is 34
The peek of the queue before deleting any element 4
The size of the queue before deletion 4
The first element to be deleted 4
The peek of the queue after deleting an element 14
The size of the queue after deleting an element 3
Time Complexity:
pop function: O(1)
push function: O(1)
top function: O(1)
size function: O(1)
Space Complexity:
Whole Queue: O(n)
- C++ Code
#include<bits/stdc++.h>using namespace std;
class Queue {
int * arr;
int start, end, currSize, maxSize;
public:
Queue() {
arr = new int[16];
start = -1;
end = -1;
currSize = 0;
} Queue(int maxSize) {
( * this).maxSize = maxSize;
arr = new int[maxSize];
start = -1;
end = -1;
currSize = 0;
}
void push(int newElement) {
if (currSize == maxSize) {
cout << "Queue is full\nExiting..." << endl;
exit(1);
}
if (end == -1) {
start = 0;
end = 0;
} else
end = (end + 1) % maxSize;
arr[end] = newElement;
cout << "The element pushed is " << newElement << endl;
currSize++;
}
int pop() {
if (start == -1) {
cout << "Queue Empty\nExiting..." << endl;
}
int popped = arr[start];
if (currSize == 1) {
start = -1;
end = -1;
} else
start = (start + 1) % maxSize;
currSize--;
return popped;
}
int top() {
if (start == -1) {
cout << "Queue is Empty" << endl;
exit(1);
}
return arr[start];
}
int size() {
return currSize;
}};int main() {
Queue q(6);
q.push(4);
q.push(14);
q.push(24);
q.push(34);
cout << "The peek of the queue before deleting any element " << q.top() << endl;
cout << "The size of the queue before deletion " << q.size() << endl;
cout << "The first element to be deleted " << q.pop() << endl;
cout << "The peek of the queue after deleting an element " << q.top() << endl;
cout << "The size of the queue after deleting an element " << q.size() << endl; return 0;
}
Output:
The element pushed is 4
The element pushed is 14
The element pushed is 24
The element pushed is 34
The peek of the queue before deleting any element 4
The size of the queue before deletion 4
The first element to be deleted 4
The peek of the queue after deleting an element 14
The size of the queue after deleting an element 3
Time Complexity:
pop function: O(1)
push function: O(1)
top function: O(1)
size function: O(1)
Space Complexity:
Whole Queue: O(n)
Implement Queue using Stack
Problem Statement: Given a Stack having some elements stored in it. Can you implement a
Queue using the given Stack?
Queue: A Queue is a linear data structure that works on the basis of FIFO(First in First out). This means the element added at first will be removed first from the Queue.
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Solution 1: Using two Stacks where push operation is O(N)
Approach:
push(x) ->
pop()->
top()->
size()->
size() operation is for returning the size of a queue which can be done by using the function Stack1. size(). It will actually return the total number of elements in the queue.
Code:
- C++ Code
#include <bits/stdc++.h>using namespace std;struct Queue {
stack < int > input, output;
// Push elements in queue
void Push(int data) {
// Pop out all elements from the stack input
while (!input.empty()) {
output.push(input.top());
input.pop();
}
// Insert the desired element in the stack input
cout << "The element pushed is " << data << endl;
input.push(data);
// Pop out elements from the stack output and push them into the stack input
while (!output.empty()) {
input.push(output.top());
output.pop();
}
}
// Pop the element from the Queue
int Pop() {
if (input.empty()) {
cout << "Stack is empty";
exit(0);
}
int val = input.top();
input.pop();
return val;
}
// Return the Topmost element from the Queue
int Top() {
if (input.empty()) {
cout << "Stack is empty";
exit(0);
}
return input.top();
}
// Return the size of the Queue
int size() {
return input.size();
}
};
int main() {
Queue q;
q.Push(3);
q.Push(4);
cout << "The element poped is " << q.Pop() << endl;
q.Push(5);
cout << "The top of the queue is " << q.Top() << endl;
cout << "The size of the queue is " << q.size() << endl;
}
Output:
The element pushed is 3
The element pushed is 4
The element poped is 3
The element pushed is 5
The top of the queue is 4
The size of the queue is 2
Time Complexity: O(N )
Space Complexity: O(2N)
Solution 2: Using two Stacks where push operation is O(1)
Approach :
Push()->
Pop()->
top()->
Size():
Code:
- Java Code
import java.util.*;class MyQueue {
Stack < Integer > input = new Stack < > ();
Stack < Integer > output = new Stack < > ();
/** Initialize your data structure here. */
public MyQueue() { } /** Push element x to the back of queue. */
public void push(int x) {
System.out.println("The element pushed is " + x);
input.push(x);
} /** Removes the element from in front of queue and returns that element. */
public int pop() {
// shift input to output
if (output.empty())
while (input.empty() == false) {
output.push(input.peek());
input.pop();
}
int x = output.peek();
output.pop();
return x;
} /** Get the front element. */
public int peek() {
// shift input to output
if (output.empty())
while (input.empty() == false) {
output.push(input.peek());
input.pop();
}
return output.peek();
}
int size() {
return (output.size() + input.size());
}
}
class TUF {
public static void main(String args[]) {
MyQueue q = new MyQueue();
q.push(3);
q.push(4);
System.out.println("The element poped is " + q.pop());
q.push(5);
System.out.println("The top element is " + q.peek());
System.out.println("The size of the queue is " + q.size()); }
}
Output:
The element pushed is 3
The element pushed is 4
The element poped is 3
The element pushed is 5
The top element is 4
The size of the queue is 2
Time Complexity: O(1 )
Space Complexity: O(2N)
- C++ Code
#include <bits/stdc++.h>using namespace std;class MyQueue {
public:
stack < int > input, output;
/** Initialize your data structure here. */
MyQueue() { } /** Push element x to the back of queue. */
void push(int x) {
cout << "The element pushed is " << x << endl;
input.push(x);
} /** Removes the element from in front of queue and returns that element. */
int pop() {
// shift input to output
if (output.empty())
while (input.size())
output.push(input.top()), input.pop(); int x = output.top();
output.pop();
return x;
} /** Get the front element. */
int top() {
// shift input to output
if (output.empty())
while (input.size())
output.push(input.top()), input.pop();
return output.top();
} int size() {
return (output.size() + input.size());
}};
int main() {
MyQueue q;
q.push(3);
q.push(4);
cout << "The element poped is " << q.pop() << endl;
q.push(5);
cout << "The top of the queue is " << q.top() << endl;
cout << "The size of the queue is " << q.size() << endl;}
Output:
The element pushed is 3
The element pushed is 4
The element poped is 3
The element pushed is 5
The top of the queue is 4
The size of the queue is 2
Time Complexity: O(1 )
Space Complexity: O(2N)
Implement Queue using Linked List
Problem Statement: Implement Queue using Singly LinkedList
Prerequisites: Queue and LinkedList Data Structure.
Detailed Explanation of the Queue and LinkedList Data Structures is Discussed here
Queue Can be Implemented in two ways :
- Static Implementation (Using Arrays)
- Dynamic implementation (Using LinkedList) .
In this article, we would discuss the implementation of queue using LinkedList.
Comparison between Implementation of Queue using LinkedList and Array.
Array LinkedListIt is Static, Needs to provide space Before implementation.
Overflow occurs when queue size reaches its maximum capacity
Nodes are allocated dynamically, so the queue can grow and shrink as much as needed.
Overflow is not possible until and unless the heap memory got exhausted.
Operations Associated with queue are :
- Enqueue (Insert Node at Rare End )
- Dequeue (Delete Node from Front )
- Peek (Return value of Front Node without Dequing)
- Empty (Returns True when queue is empty else False)
- Size (Returns size of Queue)
Let the Initial Queue be 10→20→30→40→Null.
Enqueue:
Let’s Enqueue Node with val 50 to Queue. Enqueue is 3 step process
- Create a node with a value that is to be Enqueued.
- Make the Rare Pointers next, point to the newly created Node.
- As the newly created Node is inserted at the rear end, this is the last value in Queue.
Dequeue :
Let’s Dequeue the front value that is, 10 from Queue.
- First create a ListNode pointer temp, and make it point to the Front value of Queue.
- We should delete the Front Value in Queue. So move the Front pointer to the next node after Front Node. That means Front = Front→next
- Temp is pointing to the previous Front value, temp→next is pointing to the newFront value, as we are interested to delete the temp, Make the temp→next point null.
- We don’t require temp anymore, So delete the temp.
Peek:
If Queue is not empty return Front value of Queue.
Empty:
If Front is Null then Queue is empty else not.
Size:
Maintain a variable size, initially set to zero. Upon Enqueue increment size and on Dequeue decrement size.
Code :
- Java Code
import java.util.*;
class QueueNode
{
int val;
QueueNode next;
QueueNode(int data)
{
val = data;
next = null;
}
}
class Queue
{
QueueNode Front = null, Rear = null;
int size = 0;
boolean Empty()
{
return Front == null;
}
int Peek()
{
if(Empty())
{ System.out.println("Queue is Empty");
return -1;
}
else
return Front.val;
}
void Enqueue(int value)
{
QueueNode Temp;
Temp = new QueueNode(value);
if (Temp == null) //When heap exhausted
System.out.println("Queue is Full");
else
{
if (Front == null)
{
Front = Temp;
Rear = Temp;
}
else
{
Rear.next = Temp;
Rear = Temp;
}
System.out.println(value+" Inserted into Queue ");
size++;
}
}
void Dequeue()
{
if (Front == null)
System.out.println("Queue is Empty");
else
{
System.out.println(Front.val+" Removed From Queue");
QueueNode Temp = Front;
Front = Front.next;
size--;
}
}
public static void main(String args[])
{
Queue Q=new Queue();
Q.Enqueue(10);
Q.Enqueue(20);
Q.Enqueue(30);
Q.Enqueue(40);
Q.Enqueue(50);
Q.Dequeue();
System.out.println("The size of the Queue is "+Q.size);
System.out.println("The Peek element of the Queue is "+Q.Peek());
}
}Output:
10 Inserted into Queue
20 Inserted into Queue
30 Inserted into Queue
40 Inserted into Queue
50 Inserted into Queue
10 Removed From Queue
The size of the Queue is 4
The Peek element of the Queue is 20
Time complexity: O(1).
Space Complexity: O(1)
- C++ Code
#include<bits/stdc++.h>
using namespace std;class QueueNode
{
public:
int val;
QueueNode *next;
QueueNode(int data)
{
val = data;
next = nullptr;
}
};
QueueNode *Front = nullptr, *Rare = nullptr;class Queue
{
public:
int size = 0;
bool Empty();
void Enqueue(int value);
void Dequeue();
int Peek();
};
bool Queue :: Empty()
{
return Front == nullptr;
}
int Queue :: Peek()
{
if(Empty())
{ cout<<"Queue is Empty"<<endl;
return -1;
}
else
return Front->val;
}
void Queue :: Enqueue(int value)
{
QueueNode *Temp;
Temp = new QueueNode(value);
if (Temp == nullptr) //When heap exhausted
cout << "Queue is Full" << endl;
else
{
if (Front == nullptr)
{
Front = Temp;
Rare = Temp;
}
else
{
Rare->next = Temp;
Rare = Temp;
}
cout<<value <<" Inserted into Queue "<<endl;
size++;
}
}
void Queue :: Dequeue()
{
if (Front == nullptr)
cout << "Queue is Empty" << endl;
else
{
cout<<Front->val <<" Removed From Queue"<<endl;
QueueNode *Temp = Front;
Front = Front->next;
delete Temp;
size--;
}
}
int main(){
Queue Q;
Q.Enqueue(10);
Q.Enqueue(20);
Q.Enqueue(30);
Q.Enqueue(40);
Q.Enqueue(50);
Q.Dequeue();
cout<<"The size of the Queue is "<<Q.size<<endl;
cout<<"The Peek element of the Queue is "<<Q.Peek()<<endl;
return 0;
}
Output:
10 Inserted into Queue
20 Inserted into Queue
30 Inserted into Queue
40 Inserted into Queue
50 Inserted into Queue
10 Removed From Queue
The size of the Queue is 4
The Peek element of the Queue is 20
Time complexity: O(1).
Space Complexity: O(1)
Reversing a Queue
Problem Statement: Given a queue with several elements, Your task is to reverse the queue.
Operations allowed on queue data-structure
- empty() : Checks if a queue is empty or not.
- enqueue(x) : Add an item x to rear of queue.
- dequeue() : Remove an item from front of queue.
Examples:
Example 1:
Input: Q = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Output: Q = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
Explanation: Printing the reverse of the queue.
Example 2:
Input: Q = [10, 20, 30, 40, 50]
Output: Q = [50, 40, 30, 20, 10]
Explanation: Printing the reverse of the queue.Solution
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Approach: Our task is to choose such a data structure that can store the data of the queue temporarily Because in this approach we are going to re-insert the elements in the queue so that they would get inserted in reverse order.
We will be requiring the data structure that will support a “LIFO” Principle (i.e Last In First Out).
Using a stack data structure will be a perfect choice according to the above approach
So our approach will be as follows:
- Remove all the elements from the queue and push them to a stack data structure.
- Pop out all the elements from the stack and push them back to the queue.
- The queue is revered.
- Print the queue.
Code:
- Java Code
import java.util.*;
// Java program to reverse a queue
public class TUF {
static Queue < Integer > queue;
//function to print the queue
static void Print() {
while (!queue.isEmpty()) {
System.out.print(queue.peek() + " ");
queue.remove();
}
}
// Function to reverse the queue
static void reversequeue() {
Stack < Integer > stack = new Stack < > ();
while (!queue.isEmpty()) {
stack.add(queue.peek());
queue.remove();
}
while (!stack.isEmpty()) {
queue.add(stack.peek());
stack.pop();
}
}
public static void main(String args[]) {
queue = new LinkedList < Integer > ();
queue.add(1);
queue.add(2);
queue.add(3);
queue.add(4);
queue.add(5);
queue.add(6);
queue.add(7);
queue.add(8);
queue.add(9);
queue.add(10);
reversequeue();
Print();
}
}Output: 10 9 8 7 6 5 4 3 2 1
Time Complexity: O(N)
Space Complexity (Auxiliary Space): O(N)
Reason: Use of the stack to store the value for reversing
- C++ Code
#include <bits/stdc++.h>
using namespace std;
//function to print the queue
void Print(queue < int > & Queue) {
while (!Queue.empty()) {
cout << Queue.front() << " ";
Queue.pop();
}
}
// Function to reverse the queue
void reverseQueue(queue < int > & Queue) {
stack < int > Stack;
while (!Queue.empty()) {
Stack.push(Queue.front());
Queue.pop();
}
while (!Stack.empty()) {
Queue.push(Stack.top());
Stack.pop();
}
}
int main() {
queue < int > Queue;
Queue.push(1);
Queue.push(2);
Queue.push(3);
Queue.push(4);
Queue.push(5);
Queue.push(6);
Queue.push(7);
Queue.push(8);
Queue.push(9);
Queue.push(10);
reverseQueue(Queue);
Print(Queue);
}Output: 10 9 8 7 6 5 4 3 2 1
Time Complexity: O(N)
Space Complexity (Auxiliary Space): O(N)
Reason: Use of the stack to store the value for reversing