We talked about queue in this post. Now, I’m gonna explain how to implement this data structure. What we need is a basic understanding of pointer and memory. Queue has 4 main methods

  • size() - returns the number of the elements
  • top() - returns the first element of the queue
  • pop() - deletes the first element
  • push(element) - insert new element back of the queue

How hard can it be? Can we use array? If we can, how?

Array implementation and Problems

We can create empty array, and if we push an element we, can create new array with the last element being the new element. If we want to know the first element, we can just return first element of the array. However, creating a new array and copying the old array is O(N). In other words, our push function require O(N), which is bad. Typically, all funcitons are queue are O(1). Using an array wouldn’t work well, as pop() would also be O(N). Because of the shift. Even if didn’t use shift, just tracking the index of the array, we will requires more memory, which is also bad.

Danymic memory

We don’t need to access any element in O(1) time like a vector or array. Instead, we only need to know the first element and push elements to the back. How about using a chain-like structuure? We can keep track of the chain’s head and tail. When we need to add something to the chain, we just connect the last element to the new element. When we remove the first element of the chain, we just delete it and adjust the chain accordingly. This idea can be implemented using dynamic memory.

First, let’s declare our chain’s node.

struct Node {
	int value; // value of the node
	Node *next; // pointer to the next element. can be null
};

implementing push

void push(int v) {
	Node *newNode = new Node(v); // create a new node
	if(last == nullptr) { // if last node doesn't exist, the queue is empty
		front = last = newNode; // the only element now
	} else {
		last->next = newNode; // connect the last element to new element
		last = newNode; // update the last element
	}
	s++; // udpate the size of the queue
}

implement pop

void pop() {
	if(front == nullptr) { // if it's empty, we will do nothing
		return;
	}
	Node *newFront = front->next; // get the second element
	delete front; // delete the first node from memory

	front = newFront; // update the first element
	s--; // update the size of the queue
}

Full implementation

Here’s the full code. We can even implement a function to get any elment from the queue like an array or vector, but it’s not O(1) because we have to traverse the chain.

#include <iostream>
using namespace std;

struct Node {
    int value;
    Node *next;
    Node(int v) { value = v; next = nullptr; }
};

class Queue {
    private:
        Node *front;
        Node *last;
        int s;
    public:
        Queue() {
            front = last = nullptr;
            s = 0;
        }
        int size() { return s; }
        int top() {
            if(front == nullptr) return 0;
            return front->value;
        }
        bool isEmpty() {
            if(s == 0) return true;
            return false;
        }
        void push(int v) {
            Node *newNode = new Node(v);
            if(last == nullptr) {
                front = last = newNode;
            } else {
                last->next = newNode;
                last = newNode;
            }
            s++;
        }
        void pop() {
            if(front == nullptr) {
                return;
            }
            Node *newFront = front->next;
            delete front;

            front = newFront;
            s--;
        }
        int operator[](int index) {
            if(s <= index) return 0;
            Node *current = front;
            while(index > 0) {
                current = current->next;
                index--;
            }
            return current->value;
        }
};

int main() {
    Queue q;

    q.pop();

    q.push(1);
    q.push(2);
    q.push(3);
    q.push(4);
    cout << q[3] << endl;

    cout << q.top() << endl;

    q.pop();

    cout << q.top() << endl;
}

Conclusion

If we look at the implementation, it’s simple yet helps us understand a lot. For example, why do we manually allocate new memory? Because we don’t know the how big is the queue will be. In array, we have to specify its size, making it easy to access elements. In this case, we don’t need to access any element in constant time, allowing us to achieve this implementation. This is why there are many data structures, each suited to different requirements.