Tag: queue

Queue – Basics

Implementation

may use dynamic array and an index pointing to the head of the queue.

should support enqueue (appends a new element), dequeue (removes the first element).

class MyQueue {
    private:
        vector<int> data;      
        int p_start;            
    public:
        MyQueue() {p_start = 0;}
        bool enQueue(int x) {
            data.push_back(x);
            return true;
        }

        bool deQueue() {
            if (isEmpty()) {
                return false;
            }
            p_start++;
            return true;
        };
        int Front() {
            return data[p_start];
        };
        bool isEmpty()  {
            return p_start >= data.size();
        }
};

But this has drawbacks. Memory is wasted every time we dequeue.

Thus, need a circular queue. 

Circular Queue

fixed-size array, 2 pointers indicating head and tail. Goal is to reuse the wasted storage.

In designing a DS, it’s good to have as few attributes as possible and maintain a simple manipulation logic. Sometimes, there can be some redundancy to minimize time complexity. 

Attributes:

  • queue: fixed size array.
  • headIndex: integer which indicates the current head element
  • count: the current length. with `headIndex`, we can locate the tail element.
  • capacity: max number of elements that can be held in the queue. With this, we reduce TC for calling len(queue). 
class MyCircularQueue {
private:
    vector<int> data;
    int head;
    int tail;
    int size;
public:
    MyCircularQueue(int k) {
        data.resize(k);
        head = -1;
        tail = -1;
        size = k;
    }
    bool enQueue(int value) {
        if (isFull()) {
            return false;
        }
        if (isEmpty()) {
            head = 0;
        }
        tail = (tail + 1) % size;
        data[tail] = value;
        return true;
    }
    bool deQueue() {
        if (isEmpty()) {
            return false;
        }
        if (head == tail) {
            head = -1;
            tail = -1;
            return true;
        }
        head = (head + 1) % size;
        return true;
    }    
    int Front() {
        if (isEmpty()) {
            return -1;
        }
        return data[head];
    }
    int Rear() {
        if (isEmpty()) {
            return -1;
        }
        return data[tail];
    }
    bool isEmpty() {
        return head == -1;
    }
    bool isFull() {
        return ((tail + 1) % size) == head;
    }
};

Built In Queue C++

use stl queue in practice. 

#include <queue>

int main() {
    queue<int> q;

    q.push(5);

    if (q.empty()) {}

    q.pop();

    q.front() ; get first element

    q.back() ; get last element

    q.size() ; get size
}