You are not logged in. Please login at www.codechef.com to post your questions!

×

Data Structure Tutorial : Queue

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

asked 22 Nov '16, 01:33

rashedcs's gravatar image

1★rashedcs
4871525
accept rate: 4%

edited 22 Nov '16, 13:40


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

link

answered 22 Nov '16, 09:05

mathecodician's gravatar image

5★mathecodician
2.6k320
accept rate: 8%

2

I changed it.

(22 Nov '16, 09:20) rashedcs1★

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).

link

answered 22 Nov '16, 03:30

ceilks's gravatar image

7★ceilks
1.8k8
accept rate: 36%

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

link

answered 23 Nov '16, 01:10

smsubham's gravatar image

3★smsubham
673214
accept rate: 15%

edited 23 Nov '16, 01:12

Yeap. I edited this.

(23 Nov '16, 19:15) rashedcs1★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×773

question asked: 22 Nov '16, 01:33

question was seen: 756 times

last updated: 23 Nov '16, 19:15