Data Structure Tutorial : Queue

general
1

Overview:
Queue is a data structure where elements is inserted at the front of the list and any element is deleted from the rear of list. So it is called FIFO(First in First out) data structure.
Insert operation on a queue is often called enque and delete operation is often called deque.
If we insert an element to queue the rear is increment. Similarly If we delete an element from queue the front is increment.

The following picture front is an indicator that indicates the front element of the queue and rear is also an indicator that indicates the last element of the queue.
alt text

Real life applications of stack:
Queues abound in everyday life. In our daily life, when we stand on line to get into bus , we make queue. The man who stands first will get into bus first and the man who stand last will get into the bus last.

Operation :
The following operation are performed in the stack.
1.Enque : To add an element to queue.
2.Deque : To remove an element from the queue.
3.Peek : To get the topmost element in queue.

Implementation :
Queue can be implemented two ways. using array and using linked list.Here we discuss queue implementation using array . It uses front variable to print the top most element and rear variable to print the bottom most element in the linear array.

  1. Initially front=rear=0
  2. In Enqueue operation rear is increased by one and pushed item to queue[rear]
  3. In Deque operation front is increased by one. i.e queue[front++]
  4. In Peek operation check that the front is not equal to rear and return queue[front]
  Algorithm : Enqueue(que, n, item)                
  Step 1: Start         
  Step 2: if(rear==n)         print overflow          
           else               que[rear++]=item.           
  Step 3: End

C++ implementation :
    void Enque(int que[],int n, int item)
    {
      if(rear==n)  cout<<"Overflow"<<endl;
      else        que[rear++] = item;
    }

  Algorithm : Deque(que)
  Step 1: Start
  Step 2: if(front==rear)  print Underflow;
          else             que[front++];
  Step 3: End

C++ implementation :
    void Deque(int que[])
    {
      if(front==rear)    cout<<"UnderFlow"<<endl;
      else               que[front++] ;
    }

  Algorithm : Peek(que)
  Step 1: Start
  Step 2: if(front==rear)    print Empty;
          else               return que[front];
  Step 3: End


C++ implementation :

int Peek(int que[])

{

if(front==rear)    cout<<“Queue is empty”<<endl;

else               return que[front];

}

Spoj Problem: ADAQUEUE
Hackerrank Problem :Queue using Two Stacks

1 Like
2

Your queue is using O(#of enqueues) space. Typically you wouldn’t want this, but rather O(maximal number of items in queue at the same time).

3

At the top you have that stack is a data structure … change it to queue

4

I changed it.

1 Like
5

Real life applications of stack is mentioned change it to queue …

6

Yeap. I edited this.