Two of the most commonly used data structures in web development are stacks and queues. The history of pages visited in a web browser and the undo operation in a text editor are examples of operations made possible using stacks. The handling of events in web browsers often uses a queue data structure.
A stack is a data structure that stores elements in a LIFO (Last In First Out) order. It's like a stack of plates in your kitchen. When a plate is added, it is pushed towards the bottom of a stack. The last plate that you stack becomes the one on the top of the stack and it is the first one that you get to use.
A stack has two basic functions:
- push(): places data onto the top of a stack
- pop(): removes data from the top of the stack
Let's look at how stack is implemented. A common way to implement stack is to use a stack of nodes. You can think of a node as an object that has a value and a pointer that points to the next node.
//Creates a node containing the data and a reference to the next item
var node = function(){
this.data = null;
this.next = null;
}You can then start by creating the constructor function for the stack. This will have the regular push and pop operations. In addition to the push and pop, this will also have a few other operations such as:
- peek: allows you to look at the top of the stack without removing it
- display: to display the whole stack
The constructor is nice and straightforward. The stack has a length, and a head. The head will always contain the first node. In this case we start with an empty first node, represented by null.
var Stack = function(){
this.push = push;
this.pop = pop;
this.peek = peek;
this.top = null;
this.display = display;
}- push(): when you push something onto the stack, the new item is pushed on top of the stack.
function push(data) {
//if the top of the stack is empty, then the data will be the
//top of the stack
if (this.top == null) {
this.top = new node();
this.top.data = data;
}
//if the top already has something then create a new node
//add data to the new node
// have the pointer point to the top
else {
var temp = new node();
temp.data = data;
temp.next = this.top;
this.top = temp;
}
}- peek():
function peek() {
//if the top of the stack does not have anything
//then the stack is empty
//otherwise return what's on the top
if (this.top == null) {
return null;
}
else {
return this.top.data;
}
}- pop ()
function pop() {
//in order to remove the top of the stack, you have to point
//the pointer to the next item and that next item becomes the
//top of the stack
var temp = this.top;
var data = this.top.data;
this.top = this.top.next;
temp = null;
return data;
}- display()
function display() {
// displays the entire contents of the stack
var node = this.top;
while (node != null) {
console.log(node.data);
node = node.next;
}
}var s = new Stack();
s.push(1);
s.push(2);
s.push("Tauhida");
console.log("Top of stack:", s.peek());
s.pop();
s.push("joe");
console.log("The stack contains:");
s.display();It is useful to also know that JavaScript provides us with a different way to implement stack that many other languages don't. In JavaScript the array methods more or less resemble the operations in a stack. Therefore, you can implement stack and its operations in JavaScript using JavaScript arrays. The following code base is another implementation of stack using JS arrays.
function Stack() {
this.dataStore = [];
this.top = 0;
this.push = push;
this.pop = pop;
this.peek = peek;
this.length = length;
this.display = display;
}
function push(element) {
this.dataStore[this.top++] = element;
}
function peek() {
return this.dataStore[this.top-1];
}
function pop() {
return this.dataStore[this.top--];
}
function display() {
console.log("bottom [" + this.dataStore + "] top");
};
function length() {
return this.top;
}
var s = new Stack();
s.push("Joe");
s.push("Tauhida");
s.push(5);
console.log("length: " + s.length());
console.log("top of stack:", s.peek());
s.display();| Access | Search | Insertion | Deletion |
|---|---|---|---|
| O(n) | O(n) | O(1) | O(1) |
Palindrome testing and parenthesis matching.
A stack can remove only the most recently added data. It's in LIFO order. What if you want an operation that is first come, first serve? A Queue is a data structure that models a FIFO (First In First Out) operation. Unlike a stack, a queue deletes only the oldest added data. An example of a queue is the fast food service in McDonalds. You line up and service is provide in the order that you line up. If you are first to line up, you get served first. A queue is a type of list where data is inserted at the end and is removed from the front. Queues are used to store data in the order in which they occur, as opposed to a stack, in which the last piece of data entered is the first element used for processing.
A more practical example of a queue is the event-loop of a web browser. As different events are being triggered, such as the click of a button, they are added to an event-loop's queue and handled in the order they entered the queue. Another example would be a print spooler.
The main operations of a queue include:
- enqueue(data) adds data to a queue (insertion)
- dequeue() removes the oldest added data to a queue (deletion)
var Node = function(data) {
this.data = data;
this.next = null;
};
var Queue = function(){
this.enqueue = enqueue;
this.dequeue = dequeue;
this.first = null;
this.size = 0;
}
function enqueue(data) {
var node = new Node(data);
if (!this.first){
this.first = node;
} else {
n = this.first;
while (n.next) {
n = n.next;
}
n.next = node;
}
this.size += 1;
return node;
};
function dequeue() {
temp = this.first;
this.first = this.first.next;
this.size -= 1;
return temp.data;
};
var q = new Queue();
q.enqueue("Tauhida");
q.enqueue("Joe");
q.enqueue("Tim");
console.log(q.dequeue());
q.enqueue("alison");
q.enqueue("chris");
console.log(q.dequeue());Just as before, you can use arrays to implement queue in JavaScript as well. The code would look very similar to the code from stack. Instead of using the pop() method that removes the last element from an array, we will be using the shift() method to removes the first element from the array.
function Queue() {
this.dataStore = [];
this.enqueue = enqueue;
this.dequeue = dequeue;
this.front = front;
this.back = back;
this.toString = toString;
}
//The enqueue() function adds an element to the end of a queue:
function enqueue(element) {
this.dataStore.push(element);
}
//The dequeue() function removes an element from the front of a queue:
function dequeue() {
return this.dataStore.shift();Note that the actual complexities depend on the underlying implementation and may be worse than these ideals.
| Access | Search | Insertion | Deletion |
|---|---|---|---|
| O(n) | O(n) | O(1) | O(1) |
Square dance pairing, ophidian bank