×

DS - Basics

DS - Array

DS - Linked List

DS - Stack

DS - Queue

DS Hashing

DS Tree

DS - Graph

DS Programs Using C/C++

DS - Miscellaneous Topics

Linear Queue Tutorial

What Linear Queue?

  • It is a linear data structure.
  • It is considered as sequence of items.
  • It supports FIFO (First In First Out) property.
  • It has three components:
    • A Container of items that contains elements of queue.
    • A pointer front that points the first item of the queue.
    • A pointer rear that points the last item of the queue.
  • Insertion is performed from REAR end.
  • Deletion is performed from FRONT end.
  • Insertion operation is also known as ENQUEUE in queue.

Implementation of Queue

Queue can be implementing by two ways:

  • Array or contiguous implementation.
  • Linked List implementation.

Array Implementation of Queue

In Array implementation FRONT pointer initialized with 0 and REAR initialized with -1.

Consider the implementation :- If there is 5 items in a Queue

linear queue in data structure

Note: In case of empty queue, front is one position ahead of rear : FRONT = REAR + 1;

Drawback of Linear Queue

The linear queue suffers from serious drawback that performing some operations, we can not insert items into queue, even if there is space in the queue. Suppose we have queue of 5 elements and we insert 5 items into queue, and then delete some items, then queue has space, but at that condition we can not insert items into queue.

There are five operations possible on a queue:

  1. Initialize operation
  2. Addition or insertion operation.
  3. Deletion operation.
  4. Is_full check.
  5. Is_empty check.

Algorithms

In algorithm implementation first item of queue starts from 1, and in program implementation first item will be start from 0.

  1. INIT(QUEUE,FRONT,REAR)
  2. INSERT-ITEM(QUEUE,FRONT,REAR,MAX,ITEM)
  3. REMOVE-ITEM(QUEUE,FRONT,REAR,ITEM)
  4. FULL-CHECK(QUEUE,FRONT,REAR,MAX,FULL)
  5. EMPTY-CHECK(QUEUE,FRONT,REAR,EMPTY)
    INIT(QUEUE,FRONT,REAR)
    This algorithm is used to intialize a QUEUE,FRONT,
    and REAR.
        1.	FRONT := 1;
        2.	REAR    := 0;
        3.	Return;
    INSERT-ITEM(QUEUE,FRONT,REAR,MAX,ITEM)
    This algorithm is used to add or insert item to QUEUE.
        1.	If (REAR  = MAX) then
            a.	Display “Queue overflow”;
            b.	Return;
        2.	Otherwise
            a.	REAR := REAR + 1;
            b.	QUEUE(REAR) := ITEM;
        3.	Return;
    REMOVE-ITEM(QUEUE,FRONT,REAR,ITEM)
    This algorithm is used to delete an item from QUEUE.
        1.	If (FRONT = REAR + 1) then
            a.	Display “Queue underflow”;
            b.	Return;
        2.	Otherwise
            a.	ITEM := QUEUE(FRONT);
            b.	FRONT := FRONT + 1;
        3.	Return;
    EMPTY-CHECK(QUEUE,FRONT,REAR,EMPTY)
    This algorithm is used to check whether 
    a QUEUE is EMPTY or not.
        1.	If (FRONT = REAR + 1) then
            a.	EMPTY := true;
        2.	Otherwise
            a.	EMPTY := false;
        3.	Return;
    FULL-CHECK(QUEUE,FRONT,REAR,MAX,FULL)
    This algorithm is used to check whether 
    a QUEUE is full or not.
        1.	If ( REAR = MAX ) then
            a.	FULL := true;
        2.	Otherwise
            a.	FULL := false;
        3.	Return;

Declaration of Linear Queue

                #define MAX 5

                /*Declaration of Queue*/
                typedef struct queue
                {
	                int front	;
	                int rear	;
	                int ele[MAX]	;
                }Queue;
                
                #define MAX 5
                class Queue
                {
                    private:
                        int front,rear;
                        int ele[MAX];
                    public:
                        //To Initalize queue
                        Queue() 
                        {
	                        front =  0;
	                        rear  = -1;
                        }
                        int  isFull();
                        int  isEmpty();
                        void insertQueue(int  item);
                        int  deleteQueue(int *item);
                };
                

Linear Queue Implementation for all above queue operations

            #include <stdio.h>

            #define MAX 5

            //Declaration of Queue
            typedef struct queue
            {
	            int front	;
	            int rear	;
	            int ele[MAX]	;
            }Queue;

            //Intialze Queue
            void init(Queue *q)
            {
	            q->rear  = -1;
	            q->front =  0;
            }

            //To check Queue is full or not
            int isFull(Queue *q)
            {
	            int full=0;

	            if( q->rear == MAX -1)
		            full = 1;

	            return full;
            }

            //To check Queue is empty or not
            int isEmpty(Queue *q)
            {
	            int empty=0;

	            if( q->front == q->rear+1 )
		            empty = 1;

	            return empty;
            }

            //Insert item into queue
            void insertQueue(Queue *q,int item)
            {
	            if( isFull(q) )
	            {
		            printf("\nQueue Overflow");
		            return;
	            }

	            q->ele[++(q->rear)] = item;
	            printf("\nInserted item : %d",item);
            }

            //Delete item from queue
            int deleteQueue(Queue *q, int * item)
            {
	            if( isEmpty(q) )
	            {
		            printf("\nQueue Underflow");
		            return -1;
	            }
	            *item = q->ele[(q->front)++];
	            return 0;
            }

            int main()
            {
	            int item = 0;	
	            Queue q;

	            init(&q);

	            insertQueue(&q,10);
	            insertQueue(&q,20);
	            insertQueue(&q,30);
	            insertQueue(&q,40);
	            insertQueue(&q,50);
	            insertQueue(&q,60);

	            if( deleteQueue( &q, &item ) == 0 )
		            printf("\nDeleted item : %d",item);
	            if( deleteQueue( &q, &item ) == 0 )
		            printf("\nDeleted item : %d",item);
	            if( deleteQueue( &q, &item ) == 0 )
		            printf("\nDeleted item : %d",item);
	            if( deleteQueue( &q, &item ) == 0 )
		            printf("\nDeleted item : %d",item);
	            if( deleteQueue( &q, &item ) == 0 )
		            printf("\nDeleted item : %d",item);
	            if( deleteQueue( &q, &item ) == 0 )
		            printf("\nDeleted item : %d",item);

	            printf("\n");
	            return 0;	
            }
            
Inserted item : 10
Inserted item : 20
Inserted item : 30
Inserted item : 40
Inserted item : 50
Queue Overflow
Deleted item : 10
Deleted item : 20
Deleted item : 30
Deleted item : 40
Deleted item : 50
Queue Underflow
            #include <iostream>
            using namespace std;
            #define MAX 5
            class Queue
            {
	            private:
		            int front,rear;
		            int ele[MAX];
	            public:
		            Queue() //To Initalize queue
		            {
			            front =  0;
			            rear  = -1;
		            }
		
		            int  isFull();
		            int  isEmpty();
		            void insertQueue(int  item);
		            int  deleteQueue(int *item);
            };

            //To check queue is full or not
            int Queue::isFull()
            {
	            int full = 0 ;

	            if( rear == MAX-1 )
		            full = 1;
	
	            return full;
            }

            //To check queue is empty or not
            int Queue::isEmpty()
            {
	            int empty = 0 ;

	            if( front == rear + 1 )
		            empty = 1;
	
	            return empty;
            }


            //Insert Item into queue
            void Queue:: insertQueue(int item)
            {
	            if( isFull() )
	            {
		            cout<<"\nQueue OverFlow" << endl;
		            return;
	            }	
	
	            ele[++rear]=item;
	            cout<<"\ninserted Value :" << item;
            }

            //delete item from queue
            int Queue:: deleteQueue(int *item)
            {
	            if( isEmpty() )
	            {
		            cout<<"\nQueue Underflow" << endl;
		            return -1;
	            }

	            *item = ele[front++];
	            return 0;
            }

            int main()
            {
	            int item=0;
	
	            Queue q = Queue();

	            q.insertQueue(10);
	            q.insertQueue(20);
	            q.insertQueue(30);
	            q.insertQueue(40);
	            q.insertQueue(50);
	            q.insertQueue(60);	

	            if(q.deleteQueue( &item)==0)	
		            cout<<"\nDeleted item : "<< item;
	
	            if(q.deleteQueue( &item)==0)	
		            cout<<"\nDeleted item : "<< item;
	
	            if(q.deleteQueue( &item)==0)	
		            cout<<"\nDeleted item : "<< item;
	
	            if(q.deleteQueue( &item)==0)	
		            cout<<"\nDeleted item : "<< item;
	
	            if(q.deleteQueue( &item)==0)	
		            cout<<"\nDeleted item : "<< item;
	
	            if(q.deleteQueue( &item)==0)	
		            cout<<"\nDeleted item : "<< item;
		
	            cout<< endl;
	            return 0;
            }
            
inserted Value :10
inserted Value :20
inserted Value :30
inserted Value :40
inserted Value :50
Queue OverFlow

Deleted item : 10
Deleted item : 20
Deleted item : 30
Deleted item : 40
Deleted item : 50
Queue Underflow

Note: The drawback of queue can be solved with the help of circular queue.




Comments and Discussions!

Load comments ↻





Copyright © 2024 www.includehelp.com. All rights reserved.