What Linear Queue?

It is a linear data structure.

It supports FIFO (First In First Out) property.

It is considered a sequence of items.


It has three components:

  • A Container of items that contain elements of a queue.
  • A pointer front that points to the first item of the queue.
  • A pointer rear that points to 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.


There are five operations:

  • Initialization.
  • Addition or insertion.
  • Deletion.
  • Is_full check.
  • Is_empty check.

There are five types of implementation :

  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 initialize 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 items 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;


#include <iostream>
using namespace std;

int queue[100], n = 100, front = -1, rear = -1;

void Insert();
void Delete();
void Display();

void Insert()
{

    int val;
    if (rear == n - 1)
        cout << "Queue Overflow" << endl;
    else
    {
        if (front == -1)
            front = 0;
        cout << "Insert the element in queue : " << endl;
        cin >> val;
        rear++;
        queue[rear] = val;
    }
}
void Delete()
{

    if (front == -1 || front > rear)
    {
        cout << "Queue Underflow ";
        return;
    }
    else
    {
        cout << "Element deleted from queue is : " << queue[front] << endl;
        front++;
        ;
    }
}
void Display()
{

    if (front == -1)
        cout << "Queue is empty" << endl;
    else
    {
        cout << "Queue elements are : ";
        for (int i = front; i <= rear; i++)
            cout << queue[i] << " ";
        cout << endl;
    }
}
int main()
{

    int ch;
    cout << "(1) Insert element " << endl;
    cout << "(2) Delete element " << endl;
    cout << "(3) Display all " << endl;
    cout << "(4) Exit" << endl;
    while (ch != 4)
    {
        cout << "Enter your choice : " << endl;
        cin >> ch;
        switch (ch)
        {
        case 1:
            Insert();
            break;
        case 2:
            Delete();
            break;
        case 3:
            Display();
            break;
        case 4:
            cout << "Exit" << endl;
            break;
        default:
            cout << "Invalid choice" << endl;
        }
    }
    return 0;
}

output:

(1) Insert element
(2) Delete element e
(3) Display all
(4) Exit
Enter your choice :
1
Insert the element in queue :
5
Enter your choice :
1
Insert the element in queue :
10
Enter your choice :
1
Insert the element in queue :
15
Enter your choice :
3
Queue elements are : 5 10 15
Enter your choice :
2
Element deleted from queue is : 5
Enter your choice :
10
Invalid choice
Enter your choice :
3
Queue elements are : 10 15
Enter your choice :
4
Exit