So first-- we can quickly implement a queue
using a list
or array
in most languages! This is intuitive given that they're both linear data structures, and we just need to enforce some constraints on data flow:
- To
enqueue
an item in the queue, we can use the list functionappend
. - To
dequeue
an item from the queue, we can use the list functionpop(0)
. - If we want the "top-most" (or last element to be processed) item in the queue, we can get the last index of the list using the
[-1]
index operator.
This is by far the easiest approach, but not necessarily the most performant.
1// Initialize a queue list
2queue = [];
3
4// Add elements
5queue.push(1);
6queue.push(2);
7queue.push(3);
8
9console.log("Initial queue state:");
10console.log(queue);
11
12// Removing elements from the queue
13console.log("Elements dequeued from queue");
14console.log(queue.pop());
15console.log(queue.pop());
16console.log(queue.pop());
17
18console.log("Queue after removing elements");
19console.log(queue);
Note that in C++, I used the standard queue container, which doesn't allow for direct access to its elements. The initial printout of the queue state is achieved by copying the queue to a temporary one and iterating through it. In the Go version, I used slices, which provide direct access to the underlying array, making it easier to print the entire queue.
To make this more efficient with lists, we can create a fixed-sized list and use it with two pointers and modular operations. It will yield a queue with O(1)
access and deletion time.
1function Queue() {
2 this.items = [];
3}
4
5Queue.prototype.enqueue = function (val) {
6 this.items.push(val);
7};
8
9Queue.prototype.dequeue = function () {
10 return this.items.shift();
11};
12
13// Check if the queue is empty
14Queue.prototype.isEmpty = function () {
15 return this.items.length == 0;
16};
17
18// Get the element at the front of the queue
19Queue.prototype.peek = function () {
20 return !this.isEmpty() ? this.items[0] : undefined;
21};
22
23Queue.prototype.length = function () {
24 return this.items.length;
25};
26
27let q = new Queue();
28console.log(q);