Welcome to the third post, this time we will take a quick look at stacks and queues. Let's get started with the stack data structure.
Stack
A stack is a linear data structure that operates in LIFO (last in, first out). This means newer elements get stacked on top of the older elements in the list and get taken off sooner. A good example of this is the call stack. In our stack, we will have three properties, first: the first node in the list, last: the last node in the list, and size: the count of nodes in the list. The methods that we will implement for the stack are push and pop.
push
With push, we will add a node to the top of the stack. When pushing a node to an empty list, we will set it to be first and last. If there are one or more nodes already in the list, we will set the new node to be first, and set its next property to be the previously first node. Increment the size by 1.
push(value: ValueType): void {
const node = new Node(value);
if (this.size === 0) {
this.first = node;
this.last = node;
} else {
const oldTopNode = this.first;
this.first = node;
node.next = oldTopNode;
}
this.size++;
}
pop
Pop will remove the node at the top of the list and return its value. If the stack is empty we will return null. Otherwise, save the first node in a variable. If there was only one node in the list, set the first and last properties to null. If there is more than one node, set first to be the first node's next. Decrement the size by 1 and return the value of the node we saved in the variable.
pop(): ValueType | null {
if (this.size === 0) {
return null;
} else {
const { value } = this.first!;
if (this.size === 1) {
this.first = null;
this.last = null;
} else {
this.first = this.first!.next;
}
this.size--;
return value;
}
}
Queue
A queue is also a linear data structure, but operates in FIFO (first in, first out). Just like a line at the movie theatre, the person in line first, will be served (and taken out of the line) first. A queue will also have a first, last, and size property. We will implement enqueue and dequeue.
enqueue
Enqueue will add a node to the beginning of the list. If there are no nodes in the queue, this node will be set to first and last. If there are already nodes in the list, set the next property on the current last node to be the new node and set last to be this node. increment the size by 1.
enqueue(value: ValueType): void {
const node = new Node(value);
if (this.size === 0) {
this.first = node;
} else {
this.last!.next = node;
}
this.last = node;
this.size++;
}
dequeue
Dequeue will remove the node at the beginning of the list. If the list is empty, we will return null. Otherwise, save the first node in a variable. If there is only one node in the list, set the first and last to null. If there is more than one node, set the first property to the next of the current first node. Decrement by 1 and return the value of the saved node.
dequeue(): ValueType | null {
if (this.size === 0) {
return null;
}
const { value } = this.first!;
if (this.size === 1) {
this.first = null;
this.last = null;
} else {
this.first = this.first!.next;
}
this.size--;
return value;
}
That is all I have for stacks and queues at the moment, be sure to add comments below with anything you would like to add or discuss. Also, you can get all the code here.