Implementation of Queue

Various Implementation of queue ie. Enqueue and Dequeue

Queue works on First-in-first-out (FIFO). In a FIFO data structure, the first element added to the queue will be processed first.

Implementation of the queue using 1 pointer i.e Front

int front = -1;

// Enqueue using only front pointer
void enqueue(int val)
{
    int len = v.size();

    if ((front + 1) > len - 1)
    {
        cout << "Queue Full"
             << "\n";
        return;
    }
    else
    {
        front = front + 1;
        v[front] = val;
    }
}

// Dequeue using only front pointer
void dequeue()
{
    if (front == -1)
    {
        cout << "Queue Empty"
             << "\n";
        return;
    }
    for (int i = 0; i < v.size() - 1; i++)
    {
        v[i] = v[i + 1];
    }
    front = front - 1;
}

Time Complexity for insertion is O(1).

Time Complexity for deletion is O(n). So it has a limitation.

Implementation of queue using 2 pointers i.e Front and Rear

vector<int> v(5);
int front = -1;
int rear = -1;

// Enqueue 
void enqueue(int val)
{
    int len = v.size();

    if (rear == v.size() - 1)
    {
        cout << "Queue Full"
             << "\n";
        return;
    }
    else
    {
        rear = rear + 1;
        v[rear] = val;
    }
}

// Dequeue 
void dequeue()
{
    if (front == rear)
    {
        cout << "Queue Empty"
             << "\n";
        return;
    }
    front++;
    v[front] = 0;
}

Time Complexity for insertion is O(1).

Time Complexity for deletion is O(1).

Drawback of this method:

• With the movement of the start pointer, more and more space is wasted. We cannot reuse the spaces of deleted elements.

• Every location is used only once.

Implement Queue using LL

struct QueueNode
{
    int data;
    QueueNode *next;
    QueueNode(int a)
    {
        data = a;
        next = NULL;
    }
};

struct MyQueue {
    QueueNode *front;
    QueueNode *rear;
    void push(int);
    int pop();
    MyQueue() {front = rear = NULL;}
}; 

//Function to push an element into the queue.
// Function to push an element into the queue.
void MyQueue::push(int x)
{
    // Your Code
    QueueNode *p = new QueueNode(x);

    if (!front)
    {
        front = p;
        rear = p;
    }
    else
    {
        rear->next = p;
        rear = rear->next;
    }
}

// Function to pop front element from the queue.
int MyQueue ::pop()
{
    // Your Code
    if(!front){
        return -1;
    }
    int x = front->data;
    front = front->next;

    return x;
}