Queue Data Structure

byknackers -
0

 

Queue in Data Structure




What is Queue?

A queue is described as a linear data structure with open ends and FIFO (First In, First Out) execution of operations.

A queue, according to our definition, is a list in which all additions are made at one end and all deletions are made at the other. The operation is started on the element that is pushed into the order first.




FIFO Principle of Queue:

  • The first person in a queue gets served first, just like in a line waiting to buy tickets. (First come, first served, etc.).
  • The position of the last entry in the queue, that is, the one that was most recently added, is known as the rear (or tail) of the queue. Similarly, the position of the entry in a queue ready to be served, that is, the first entry that will be removed from the queue, is referred to as the front of the queue (sometimes, head of the queue). See the image below.




Characteristics of Queue:

  • Multiple data can be handled using queue.
  • Having access to both ends
  • They move quickly and easily.


Queue Representation:

Queues can be expressed as an array just like stacks: The array is used to implement the Queue in this representation. The variables in this case are:

Queue: the name of the array storing queue elements.

Front: the index where the first element is stored in the array representing the queue.

Rear: the index where the last element is stored in an array representing the queue.


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 often used to return the value of first element without dequeuing it.


Queue implementation in C++

/* Below program is written in C++ language */

#include<iostream>

using namespace std;

#define SIZE 10

class Queue
{
    int a[SIZE];
    int rear;   //same as tail
    int front;  //same as head
  
    public:
    Queue()
    {
        rear = front = -1;
    }
    
    //declaring enqueue, dequeue and display functions
    void enqueue(int x);     
    int dequeue();
    void display();
};

// function enqueue - to add data to queue
void Queue :: enqueue(int x)
{
    if(front == -1) {
        front++;
    }
    if( rear == SIZE-1)
    {
        cout << "Queue is full";
    }
    else
    {
        a[++rear] = x;
    }
}

// function dequeue - to remove data from queue
int Queue :: dequeue()
{
    return a[++front];  // following approach [B], explained above
}

// function to display the queue elements
void Queue :: display()
{
    int i;
    for( i = front; i <= rear; i++)
    {
        cout << a[i] << endl;
    }
}

// the main function
int main()
{
    Queue q;
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);
    q.enqueue(40);
    q.enqueue(50);
    q.dequeue();
    q.enqueue(103);
    q.dequeue();
    q.dequeue();
    q.enqueue(104);
    
    q.display();
    
    return 0;
}


Application of Queue:

Like the name implies, a queue is used whenever we need to manage a group of things in such a way that the first object to enter also exits first, leaving the others waiting till their turn comes, as in the following situations:

  • Scheduling tasks for a single shared resource, such as a printer or a CPU, to serve requests.
  • In the real world, call centre phone systems use queues to keep customers calling in order until a service agent is available.
  • interrupt management in real-time systems. The interruptions are handled first come, first served, in the order that they are received.



Time Complexity of Queue:

Similar to a stack, we can correctly determine where new elements will be added and where they will be removed in a queue, thus both actions only take one step.

  • Enqueue: O(1)
  • Dequeue: O(1)
  • Size: O(1)




Tags

Post a Comment

Previous Post Next Post