Types of Queue

 

Simple and Circular Queue:

Introduction:

Queue is an abstract data structure, somewhat similar to Stacks. Unlike stacks, a queue is open at both its ends. One end is always used to insert data (enqueue) and the other is used to remove data (dequeue). Queue follows First-In-First-Out methodology

Queue Representation:

As we now understand that in queue, we access both ends for different reasons. The following diagram given below tries to explain queue representation as data structure −

As in stacks, a queue can also be implemented using Arrays, Linked-lists, Pointers and Structures

Basic Operations:

Here we shall try to understand the basic operations associated with queues.

Ø  enqueue()        add (store) an item to the queue.

Ø  dequeue()         remove (access) an item from the queue

Few more functions are required to make the above-mentioned queue operation efficient.

 These are

Ø  peek()              Gets the element at the front of the queue without removing it.

Ø  isfull()              Checks if the queue is full.

Ø  isempty()        Checks if the queue is empty.

 

Code:

//DSA LAB 6

//CIrcular queue  using linklist

#include <iostream>

using namespace std;

 

struct node {

    node* link;

    int data;

};

 

class queue {

private:

    node* front;

    node* rear;

 

public:

    queue() {

        front = NULL;

        rear = NULL;

    }

 

  

    void push(int);

    void pop();

    void show();

};

 

 

void queue::push(int x) {

    node* p = new node;

    p->data = x;

 

    if (front==NULL) {

        front = p;

        rear = p;

        p->link = p;  // Make it point to itself for a circular link

    } else {

        rear->link = p;

        p->link = front;

        rear = p;

    }

}

 

void queue::pop() {

    if (rear==NULL) {

        cout << "Queue is Empty" << endl;

    } else {

        node* p = front;

        int temp = front->data;

 

        if (front == rear) {

            front = NULL;

            rear = NULL;

        } else {

            front = front->link;

            rear->link = front; // Update the link to make it circular

        }

 

        cout << "Popped value is: " << temp << endl;

        delete p;

    }

}

 

void queue::show() {

    if (rear==NULL) {

        cout << "Queue is Empty" << endl;

        return;

    }

 

    node* p = front;

 

    do {

        cout << p->data << " ";

        p = p->link;

    } while (p != front);

 

    cout << endl;

}

 

int main() {

    queue q1;

    int choice, x;

 

    do {

        cout << "1.Push an element" << endl;

        cout << "2.Pop an element" << endl;

        cout << "3.Show the queue" << endl;

        cout << "Enter the choice: ";

        cin >> choice;

 

        switch (choice) {

            case 1:

                cout << "Enter the element you want to enter: ";

                cin >> x;

                q1.push(x);

                break;

            case 2:

                q1.pop();

                break;

            case 3:

                q1.show();

                break;

        }

    } while (true);

 

    return 0;

}