CodeBuddy

Home Learn Practice Contests Rankings Log In Sign Up

Subtopics

Stack
Queue

Basic Data Structures ( Queue )

<h1>Queue</h1>
Queue is a simple data structure used for storing data. In queue, the order in which the data arrives is important. A common example of queue is movie theater ticket counter, the first person who stands in front of ticket window take ticket first and remove from line and new person always stand in line from end. The first person entering the queue is the first one to go out.

Queue is an ordered list in which insertion and deletion are done at different ends. End from which element is inserted is called REAR or BACK and end from which element is removed is called FRONT. The first element inserted is the first one to be removed. Hence it is called FIFO(first in first out) or LILO(last in last out).
 
<hr/>
<h3>Operations</h3>
 
1. Push 
When an element is inserted in the queue, it is added at rear or back end. This operation is known as push. 
<img src='https://s27.postimg.org/my0lcneib/image.jpg'> 
<img src='https://s24.postimg.org/4gd3kk0f9/image.jpg'> 
<img src='https://s28.postimg.org/5tn6owf65/image.jpg'>

2. Pop 
An element is removed from the front end of queue. (Element which was inserted earliest in comparison to all the elements present in the queue) This operation is called as pop. 
<img src='https://s29.postimg.org/56aq9tj8n/qp1.jpg'> 
<img src='https://s23.postimg.org/4g1pf2nln/qp2.jpg'> 
<img src='https://s29.postimg.org/xcw0lmwdz/qp3.jpg'> 
<hr/>
<h3>Queue ADT</h3>
Recall that an Abstract Data Type is defined as "class of objects whose logical behavior is defined by a set of values and a set of operations". i.e. an ADT consists of 2 parts - 
<ul>
	<li>Declaration of data</li>
	<li>Declaration of operations</li>
</ul>
 
Main queue operations :
<ul>
	<li>void Push(data): Inserts data on the back or rear end of queue.</li>
	<li>void Pop(): Removes data from the front end of queue.</li>
</ul>
 
Auxiliary queue operations :
<ul>
	<li>Front(): Returns the element present at the front end of queue without removing it.</li>
	<li>int Size(): Returns the number of elements stored in queue.</li>
	<li>bool IsEmptyQueue(): Returns true if queue is empty.</li>
	<li>bool IsFullQueue(): Returns true if queue is full.</li>
</ul>
 
<hr/>
<h3>Exceptions in Queue</h3>
<ul>
	<li>Underflow: Trying to access an element from an empty queue results in an underflow condition.</li>
	<li>Overflow: Trying to push an element to a queue which has reached its capacity is called overflow.</li>
</ul> 
<hr/>
<h3>Applications of Queue </h3>
<ul>
	<li>Serving requests on a single shared resource, like a printer, CPU task scheduling etc.</li>
	<li>In real life, Call Center phone systems will use Queues, to hold people calling them in an order, until a service representative is free.</li>
	<li>Handling of interrupts in real-time systems. The interrupts are handled in the same order as they arrive, First come first served.</li>
</ul>
 <hr/>
<h3>Simple Array Implementation</h3>
In this method, we store the queue elements in a simple array, and keep a variable to maintain the front and rear end of queue. 
Elements are always added and removed in the left to right direction. 
Initially the rear variable is set to -1 and front variable is set to 0 and whenever we add any element to queue, we increase the rear variable. Similarly on poping an element, we increase the top variable.

<pre><code>#include &lt;bits/stdc++.h&gt;
using namespace std;

struct arrayQueue {
    int frontIndex;
    int rearIndex;
    int capacity;
    int *arr;

arrayQueue(int size) {
        this->rearIndex= -1;
        this->frontIndex= 0;
        this->capacity = size;
        this->arr = (int*) calloc(size, sizeof(int));
    }

bool isEmptyQueue() {
 return this->rearIndex < this->frontIndex;
 }

bool isFullQueue() {
        return this->rearIndex == this->capacity - 1;
    }

void push(int data) {
        if(isFullQueue())
            printf("Queue Overflow!!\n");
        else 
            this->arr[++this->rearIndex] = data;
    }

void pop() {
        if(isEmptyQueue())
            printf("Queue Underflow!!\n");
        else
            ++this->frontIndex;
    }

int front() {
        if(isEmptyQueue()) {
            printf("Queue is Empty!!\n");
            return -1;
        }
        return this->arr[this->frontIndex];
    }

int size() {
        return this->rearIndex - this->frontIndex + 1;
    }
};

int main() {
    arrayQueue qu(10); //creates a queue of size 10
    
    qu.push(4); // queue : 4
    qu.push(1); // queue : 4 1
    qu.pop();   // queue : 1
    qu.push(3); // queue : 1 3
    qu.push(5); // queue : 1 3 5
    qu.push(4); // queue : 1 3 5 4
    qu.pop();   // queue : 3 5 4
    qu.push(2); // queue : 3 5 4 2
    qu.pop();   // queue : 5 4 2
    qu.pop();   // queue : 4 2
    qu.pop();   // queue : 2
    qu.pop();   // queue :
    qu.pop();   // This will cause queue underflow

return 0;
}
</code></pre> 
Following is the complexity analysis for above approach. 
<ul>
	<li>Space Complexity: O(n)</li>
	<li>Time Complexity for each push() operation: O(1)</li>
	<li>Time Complexity for each pop() operation: O(1)</li>
	<li>Time Complexity for each size() operation: O(1)</li>
</ul>
 
Limitation: This approach suffers from the limitation that the maximum size of the queue must be defined in prior and cannot be changed. Trying to push a new element into a full queue causes an implementation-specific exception.