 # Learn Data Structure and Algorithm in JavaScript | Part 12 Edison Pebojot(👨‍💻) Updated on ・18 min read

# Prerequisite (✋😐)

If you're reading this article right now, please considered to read our Part 01: Big-O Notation, Part 02: JavaScript Unique Part, Part 03: JavaScript Numbers to Part 11: Hash Tables

01 Big-O Notation By the end of this chapter, you will understand how to analyze an implementation of an algorithm with respect to both time (execution time) and space (memory consumed).
02 JavaScript Unique Parts Big-O is important for analyzing and comparing the efficiencies of algorithms. The analysis of Big-O starts by looking at the code, and, applying the rules, applying the rules is because to simplify the Big-O notation linear or quadratic rule is not enough.
03 JavaScript Numbers This part 3 will focus on JavaScript number operations, number representation, Number objects, common number algorithms, and random number generation.
04 JavaScript Strings This part 4 will focus on strings, JavaScript String object, and the String object’s built-in functions. You will learn how to access, compare, decompose, and search strings for commonly used real-life purposes. In addition, the chapter will explore string encoding, decoding, encryption, and decryption.
05 JavaScript Arrays As a JavaScript developer, you will use the array often; it is the most commonly used data structure. Arrays in JavaScript come with a lot of built-in methods. By the end of this part, you will understand arrays and choose the right method
06 JavaScript Object This part will focus on what JavaScript objects are, how they are declared, and how their properties can be changed. In addition, this part will cover how JavaScript classes are implemented using prototypal inheritance. Also this part will be short.
07 JavaScript Memory Management A variable takes up some memory. In C, the programmer allocate and deallocate memory manually. In contrast, modern JavaScript engines have garbage collectors that delete unused variables. However, there are pitfalls(unexpected) that developers can fall into(❗) This part will show these unexpected and present techniques to help the garbage collector minimize the memory problems.
08 Recursion This part 8 introduces the concept of recursion and recursive algorithms(Remember they are different, we will discuss them later(😉)). We will also discuss the definition of recursion and fundamental rules for recursive algorithms.
09 Sets This part focuses on the concepts of sets from both a mathematical definition and on the implementation. Also, Common set operations, as well as their implementations, are covered in great detail (💡).
10 Searching and Sorting This part 10 focuses on searching and sorting for arrays. By the end of this part 10, you will understand how to use sorting and searching algorithms for arrays. Also, this article is a bit complicated for beginners, so as much as possible the visual aids is your friend (👀). (😃)
11 Hash Tables A hash table is a fixed-sized data structure in which the size is defined at the start. This part 11 explains how hash tables work, and the method of generating a unique key. By the end of this part 11, you will understand various hashing techniques and know how to implement a hash table. (😃)
12 Stacks and Queues This part 12 covers stacks and queues(pronounce as kyooz (🔈)) not (kwewe) okay? hehehe (😅); both are data structures used in the implementation of complex data structures. You'll learn what the stacks and queues are, how they're used, when they're used, and how to implement them (😃) Let's go! (🔥🔥🔥)
13 Linked Lists A linked list is a data structure in which each node (or element) points to another node. Unlike arrays, which have a fixed size, a linked list is a dynamic data structure. By the end of this part 13, you will understand how to implement and work with linked lists. And oh! (😮) There are two types of linked lists: singly (➡️) and doubly (↔️). Let’s examine the singly linked list first.(😃) Let's go! (🔥🔥🔥)
14 Caching Caching is the process of storing data into temporary memory so that it can be easily retrieved for later use if it is required again. As an example, a database keeps data cached to avoid re-reading the hard drive, and a web browser caches web images to avoid re-downloading. In this part 14, two caching techniques will discussed: LFU and LRU caching.
15 Trees A general tree data structure is composed of nodes with children nodes. The top node is called the root node. This part 15 will explore different types of trees such as binary trees, binary search trees, and self-balancing binary search trees. First, this part 15 will cover what trees are and how they are structured. Then, it will cover methods of traversing(crossing or taking a zigzag path) the tree data structure in detail. Finally, you will learn about binary search trees and self-balancing binary search trees to understand how to store searchable data. (😃)
16 Heaps A heap is an important data structure that returns the highest or lowest element in O(1) time. This part 16 will focus on explaining how heaps are implemented as well as how to work with them. One example is heap sort, which is a sorting algorithm based on heaps.
17 Graphs In this Part 17, you will learn graph basics, including fundamental terminology and graph types. The Part 17 will also cover working with these different graph types and methods of representing graphs in data structures. Finally, algorithms for traversing, searching, and sorting graphs are explored to solve problems such as finding the shortest path between two graph nodes. (👍)
18 Advance Strings Part 18 will cover more complex string algorithms than covered in the previous section. Now that you have heard of certain other data models or structures, they should be easier to comprehend. Specifically, Part 18 will focus on string searching algorithms. (😉)

# Part 12: Stacks and Queues (😱 🔥 📚) This part 12 covers stacks and queues(pronounce as kyooz (🔈)) not (kwewe) okay? hehehe (😅); both are data structures used in the implementation of complex data structures. You'll learn what the stacks and queues are, how they're used, when they're used, and how to implement them (😃) Let's go! (🔥🔥🔥)

## Stacks (➡️❌) A stack is a data structure in which only the last inserted element can be removed and accessed. Think about stacking(covering with) plates on a table. To get to the bottom one, you must remove the top. This is a principle known as Last In, First Out (LIFO). A stack is great because it is fast. Since the lookup and insertion happen in a constant time of $O(1)$ . Stacks should be used when you need to work in the LIFO form to access only the last-added element. The limitation of stacks is that they cannot access the non-last-added element directly. In JavaScript, arrays have methods that define the stack: pop and push. With this, a stack can be easily implemented. Here is some skeleton code to start:

Example:

// Stack
function Stack(array) {
this.array = [];
if (array) this.array = array;
}

// Instance(example) of the "Stack" class
var stack = new Stack([]);

// Result
stack; // Prints "Stack { array: [] }"


Execution:

   // Stack function Stack(array) { this.array = []; if (array) this.array = array; } // Instance(example) of the "Stack" class var stack = new Stack([]); // Result stack; // Prints "Stack { array: [] }" 

### Peek (🔍📦🔎)

Peeking(or looking) at the last added element of the stack means returning the last-added element without removing it from the data structure. Peeking is often used to compare the last-added element to some variable whether the last-added element should be removed from the data structure or not. Let's look at some example below:

Example:

// Stack
function Stack(array) {
this.array = [];
if (array) this.array = array;
}

// Peek
Stack.prototype.peek = function () {
return this.array[this.array.length - 1];
}

// Push
Stack.prototype.push = function (value) {
this.array.push(value);
}

// Instance(example) of the "Stack" class
var stack = new Stack([]);

stack.push(1);
stack.push(2);

// Result
stack.peek(); // Prints "3"


Execution:

   // Stack function Stack(array) { this.array = []; if (array) this.array = array; } // Peek Stack.prototype.peek = function () { return this.array[this.array.length - 1]; } // Push Stack.prototype.push = function (value) { this.array.push(value); } // Instance(example) of the "Stack" class var stack = new Stack([]); // Add stack.push(1); stack.push(2); stack.push(3); // Last added element // Result stack.peek(); // Prints "3" 

Time Complexity: $O(1)$

### Insertion (➡️📦⬅️)

Inserting into a stack can be done via the push function natively supported with JavaScript arrays. Let's look at some example below:

Example:

// Stack
function Stack(array) {
this.array = [];
if (array) this.array = array;
}

// Push
Stack.prototype.push = function (value) {
this.array.push(value);
}

// Instance(example) of the "Stack" class
var stack = new Stack([]);

stack.push(1);
stack.push(2);
stack.push(3);

// Result
stack // Prints "Stack { array: [1, 2, 3] }"


Execution:

   // Stack function Stack(array) { this.array = []; if (array) this.array = array; } // Push Stack.prototype.push = function (value) { this.array.push(value); } // Instance(example) of the "Stack" class var stack = new Stack([]); // Add stack.push(1); stack.push(2); stack.push(3); // Result stack // Prints "Stack { array: [1, 2, 3] }" 

Time Complexity: $O(1)$

### Deletion (❌📦❌)

Deletion can also be implemented using a native JavaScript array method, called pop or pop(). Let's look at some example below:

Example:

// Stack
function Stack(array) {
this.array = [];
if (array) this.array = array;
}

// Push
Stack.prototype.push = function (value) {
this.array.push(value);
}

// Pop
Stack.prototype.pop = function () {
this.array.pop();
}

// Log
Stack.prototype.log = function (stack) {
return stack;
}

// Instance(example) of the "Stack" class
var stack = new Stack([]);

// Delete
stack.pop(); // Delete 3
stack.pop(); // Delete 2
stack.pop(); // Delete 1

// Result
stack.log(stack) // Prints "Stack { array: [] }"


Execution:

   // Stack function Stack(array) { this.array = []; if (array) this.array = array; } // Push Stack.prototype.push = function (value) { this.array.push(value); } // Pop Stack.prototype.pop = function () { this.array.pop(); } // Log Stack.prototype.log = function (stack) { return stack; } // Instance(example) of the "Stack" class var stack = new Stack([]); // Add stack.push(1); // Add 1 stack.push(2); // Add 2 stack.push(3); // Add 3 // Delete stack.pop(); // Delete 3 stack.pop(); // Delete 2 stack.pop(); // Delete 1 // Result stack.log(stack) // Prints "Stack { array: [] }" 

Time Complexity: $O(1)$

### Access (⬅️📦➡️)

Accessing specific elements in a data structure is important. Let’s take a look at how to access an element based on order below:

Example:

// Stack
function Stack(array) {
this.array = [];
if (array) this.array = array;
}

// Buffer
// Note: A buffer in the code below is use create a copy of an array to prevent the modification of the original array.
Stack.prototype.getBuffer = function () {
return this.array.slice();
}

// Push
Stack.prototype.push = function (value) {
this.array.push(value);
}

// Pop
Stack.prototype.pop = function () {
return this.array.pop();
}

// Access
function stackAccessNthTopNode(stack, n) {
var bufferArray = stack.getBuffer();
if (n <= 0) throw "error";

var bufferStack = new Stack(bufferArray)

while (--n !== 0) {
bufferStack.pop();
}

return bufferStack.pop();
}

// Instance(example) of the "Stack" class
var stack = new Stack([]);

stack.push(3);
stack.push(2);
stack.push(1);

// Result
stackAccessNthTopNode(stack, 3); // Prints "3"


Execution:

   // Stack function Stack(array) { this.array = []; if (array) this.array = array; } // Buffer // Note: A buffer in the code below is use create a copy of an array to prevent the modification of the original array. Stack.prototype.getBuffer = function () { return this.array.slice(); } // Push Stack.prototype.push = function (value) { this.array.push(value); } // Pop Stack.prototype.pop = function () { return this.array.pop(); } // Access function stackAccessNthTopNode(stack, n) { var bufferArray = stack.getBuffer(); if (n <= 0) throw "error"; var bufferStack = new Stack(bufferArray) while (--n !== 0) { bufferStack.pop(); } return bufferStack.pop(); } // Instance(example) of the "Stack" class var stack = new Stack([]); stack.push(3); stack.push(2); stack.push(1); // Result stackAccessNthTopNode(stack, 3); // Prints "3" 

Time Complexity: $O(1)$

Note (📝): Search will be implemented in a similar way.

### Search (🔎📦🔍)

Searching the stack data structure for a specific element is critical. To do this, you must first create a buffer stack so that pop can be called. This way, the original stack is not mutated, and nothing is removed from it. Let's see at some example below:

Example:

// Stack
function Stack(array) {
this.array = [];
if (array) this.array = array;
}

// Buffer
Stack.prototype.getBuffer = function () {
return this.array.slice();
}

// Empty
Stack.prototype.isEmpty = function () {
return this.array.length == 0;
}

// Push
Stack.prototype.push = function (value) {
this.array.push(value);
}

// Pop
Stack.prototype.pop = function () {
return this.array.pop();
}

// Search
function stackSearch(stack, element) {
var bufferArray = stack.getBuffer();

var bufferStack = new Stack(bufferArray)

while (!bufferStack.isEmpty()) {
if (bufferStack.pop() == element) {
return true;
}
}
return false;
}

// Instance(example) of the "Stack" class
var stack = new Stack([]);

stack.push(1);
stack.push(2);
stack.push(3);

// Result
stackSearch(stack, 3); // Prints "true"


Execution:

   // Stack function Stack(array) { this.array = []; if (array) this.array = array; } // Buffer Stack.prototype.getBuffer = function () { return this.array.slice(); } // Empty Stack.prototype.isEmpty = function () { return this.array.length == 0; } // Push Stack.prototype.push = function (value) { this.array.push(value); } // Pop Stack.prototype.pop = function () { return this.array.pop(); } // Search function stackSearch(stack, element) { var bufferArray = stack.getBuffer(); var bufferStack = new Stack(bufferArray) while (!bufferStack.isEmpty()) { if (bufferStack.pop() == element) { return true; } } return false; } // Instance(example) of the "Stack" class var stack = new Stack([]); // Add stack.push(1); stack.push(2); stack.push(3); // Result stackSearch(stack, 3); // Prints "true" 

Time Complexity: $O(1)$

## Queues (❌➡️) A queue is also a data structure, but you can remove only the first added element. This is a principle known as First In, First Out (FIFO). A queue is also great because of the constant time. Similar to a stack, it has limitations because only one item can be accessed at a time. Queues should be used when you need to work in the FIFO form to access the first added element. In JavaScript, arrays have methods that define the queue: shift() and push(). shift() method on an array in JavaScript removes and returns the first element of the array. Adding to a queue is commonly known as enqueuing (en-kyuu-ing (🔈)), and removing from a queue is known as dequeuing (de-kyuu-ing (🔈)). shift() can be used for dequeue, and .push() can be used for enqueue. Here is some skeleton code to start:

Example:

// Queue
function Queue(array) {
this.array = [];
if(array) this.array = array;
}

// Buffer
Queue.prototype.getBuffer = function () {
return this.array.slice();
}

// Empty
Queue.prototype.isEmpty = function () {
return this.array.length == 0;
}

// Instance(example) of the queue class
var queue = new Queue([]);

// Result
queue; // Prints "Stack { array: [] }"


Execution:

   // Queue function Queue(array) { this.array = []; if(array) this.array = array; } // Buffer Queue.prototype.getBuffer = function () { return this.array.slice(); } // Empty Queue.prototype.isEmpty = function () { return this.array.length == 0; } // Instance(example) of the queue class var queue = new Queue([]); // Result queue; // Prints "Stack { array: [] }" 

### Peek (🔍📦🔎)

The peek function looks at the first item. In the stack implementation, the last element in the array was returned, but a queue returns the first element in the array because of FIFO. Let's look at some example below:

Example:

// Queue
function Queue(array) {
this.array = [];
if (array) this.array = array;
}

// Insertion for a queue is known as enqueue
Queue.prototype.enqueue = function (value) {
this.array.push(value);
}

// Peek
Queue.prototype.peek = function () {
return this.array;
}

// Instance(example) of the queue class
var queue = new Queue([]);

// Result
queue.peek(); // Prints "1"


Execution:

   // Queue function Queue(array) { this.array = []; if (array) this.array = array; } // Insertion for a queue is known as enqueue Queue.prototype.enqueue = function (value) { this.array.push(value); } // Peek Queue.prototype.peek = function () { return this.array; } // Instance(example) of the queue class var queue = new Queue([]); // Add queue.enqueue(1); // Add 1 queue.enqueue(2); // Add 2 queue.enqueue(3); // Add 3 // Result queue.peek(); // Prints "1" 

### Insertion (➡️📦⬅️)

As mentioned, insertion for a queue is known as enqueue. The push() method can be used to implement enqueue. Let's look at some example below:

Note (📝): You may wonder why we used the push method instead of the unshift method. Yeah, you 're right, man! The unshift method adds an element at the start of the array. But, huh? If some developer or programmer told you to use the unshift method instead of pushing with queues, don't believe it. What if I told you that the unshift method is slower, yes the unshift method is slower in queues or any data structure, it is faster to use push statements followed by a call to reverse instead of calling unshift all the time. Okay? Okay? (😉)

Example:

// Queue
function Queue(array) {
this.array = [];
if (array) this.array = array;
}

// Insertion for a queue is known as enqueue
Queue.prototype.enqueue = function (value) {
this.array.push(value);
}

// Instance(example) of the queue class
var queue = new Queue([])

// Result
queue; // Prints "Stack { array: [1, 2, 3] }"


Execution:

   // Queue function Queue(array) { this.array = []; if (array) this.array = array; } // Insertion for a queue is known as enqueue Queue.prototype.enqueue = function (value) { this.array.push(value); } // Instance(example) of the queue class var queue = new Queue([]) // Add queue.enqueue(1); // Add 1 queue.enqueue(2); // Add 2 queue.enqueue(3); // Add 3 // Result queue; // Prints "Stack { array: [1, 2, 3] }" 

Time Complexity: $O(1)$

### Deletion (❌📦❌)

As mentioned, deletion for a queue is also known as dequeue. The shift() method can be used to remove the first element in the queue. Let's see at some example below:

Example:

// Queue
function Queue(array) {
this.array = [];
if (array) this.array = array;
}

// Insertion for a queue is known as enqueue
Queue.prototype.enqueue = function (value) {
this.array.push(value);
}

// Deletion for a queue also is known as dequeue
Queue.prototype.dequeue = function () {
this.array.shift();
}

// Log
Queue.prototype.log = function (queue) {
return queue;
}

// Instance(example) of the queue class
var queue = new Queue([])

// Delete
queue.dequeue(); // Delete 1
queue.dequeue(); // Delete 2
queue.dequeue(); // Delete 3

// Result
queue.log(queue) // Prints "Stack { array: [] }"

// queue.log() is optional, you may use another function to output the result
// but this is just mine :)


Execution:

   // Queue function Queue(array) { this.array = []; if (array) this.array = array; } // Insertion for a queue is known as enqueue Queue.prototype.enqueue = function (value) { this.array.push(value); } // Deletion for a queue also is known as dequeue Queue.prototype.dequeue = function () { this.array.shift(); } // Log Queue.prototype.log = function (queue) { return queue; } // Instance(example) of the queue class var queue = new Queue([]) // Add queue.enqueue(1); // Add 1 queue.enqueue(2); // Add 2 queue.enqueue(3); // Add 3 // Delete queue.dequeue(); // Delete 1 queue.dequeue(); // Delete 2 queue.dequeue(); // Delete 3 // Result queue.log(queue) // Prints "Stack { array: [] }" // queue.log() is optional, you may use another function to output the result // but this is just mine :) 

Time Complexity: $O(n)$

Note (📝): Because shift() removes the element at zero indexes and then shifts remaining indexes down consecutively(or in serial/straight), all elements in the array need to have their indexes altered, and this takes $O(n)$ . With a linked-list implementation, as covered in part 13, this can be reduced to $O(1)$ .

### Access (⬅️📦➡️)

Unlike an array, items in a queue cannot be accessed via index(like array or array). To access the last-added node(or element), you need to call dequeue $n$ number of times. A buffer is needed to prevent modification to the original queue. Let's look at some example below:

Example:

// Queue
function Queue(array) {
this.array = [];
if (array) this.array = array;
}

// Insertion for a queue is known as enqueue
Queue.prototype.enqueue = function (value) {
this.array.push(value);
}

// Deletion for a queue also is known as dequeue
Queue.prototype.dequeue = function () {
return this.array.shift();
}

// Buffer
Queue.prototype.getBuffer = function () {
return this.array.slice();
}

// Access
function queueAccessNthTopNode(queue, n) {
var bufferArray = queue.getBuffer();
if (n <= 0) throw "Error";

var bufferQueue = new Queue(bufferArray);

while (--n !== 0) {
bufferQueue.dequeue();
}
return bufferQueue.dequeue();
}

// Instance(example) of the queue class
var queue = new Queue([])

// Result
queueAccessNthTopNode(queue, 3) // Prints "3"


Execution:

   // Queue function Queue(array) { this.array = []; if (array) this.array = array; } // Insertion for a queue is known as enqueue Queue.prototype.enqueue = function (value) { this.array.push(value); } // Deletion for a queue also is known as dequeue Queue.prototype.dequeue = function () { return this.array.shift(); } // Buffer Queue.prototype.getBuffer = function () { return this.array.slice(); } // Access function queueAccessNthTopNode(queue, n) { var bufferArray = queue.getBuffer(); if (n <= 0) throw "Error"; var bufferQueue = new Queue(bufferArray); while (--n !== 0) { bufferQueue.dequeue(); } return bufferQueue.dequeue(); } // Instance(example) of the queue class var queue = new Queue([]) // Add queue.enqueue(1); // Add 1 queue.enqueue(2); // Add 2 queue.enqueue(3); // Add 3 // Result queueAccessNthTopNode(queue, 3) // Prints "3" 

Time Complexity: $O(n)$

### Search (🔎📦🔍)

You might need to search a queue to check whether an element exists. Again, this involves creating a buffer queue first to avoid modifications to the original queue. Let's look at some example below:

Example:

// Queue
function Queue(array) {
this.array = [];
if (array) this.array = array;
}

// Insertion for a queue is known as enqueue
Queue.prototype.enqueue = function (value) {
this.array.push(value);
}

// Deletion for a queue also is known as dequeue
Queue.prototype.dequeue = function () {
return this.array.shift();
}

// Buffer
Queue.prototype.getBuffer = function () {
return this.array.slice();
}

// Empty
Queue.prototype.isEmpty = function () {
return this.array.length == 0;
}

// Search
function queueSearch(queue, element) {
var bufferArray = queue.getBuffer();

var bufferQueue = new Queue(bufferArray);
while (!bufferQueue.isEmpty()) {
if (bufferQueue.dequeue() == element) {
return true;
}
}
return false;
}

// Instance(example) of the queue class
var queue = new Queue([])

// Result
queueSearch(queue, 3) // Prints "true"


Execution:

   // Queue function Queue(array) { this.array = []; if (array) this.array = array; } // Insertion for a queue is known as enqueue Queue.prototype.enqueue = function (value) { this.array.push(value); } // Deletion for a queue also is known as dequeue Queue.prototype.dequeue = function () { return this.array.shift(); } // Buffer Queue.prototype.getBuffer = function () { return this.array.slice(); } // Empty Queue.prototype.isEmpty = function () { return this.array.length == 0; } // Search function queueSearch(queue, element) { var bufferArray = queue.getBuffer(); var bufferQueue = new Queue(bufferArray); while (!bufferQueue.isEmpty()) { if (bufferQueue.dequeue() == element) { return true; } } return false; } // Instance(example) of the queue class var queue = new Queue([]) // Add queue.enqueue(1); // Add 1 queue.enqueue(2); // Add 2 queue.enqueue(3); // Add 3 // Result queueSearch(queue, 3) // Prints "true" 

Time Complexity: $O(n)$

## Summary (📚📚) Both stacks and queues support peek, insertion, and deletion in $O(1)$ . The most important distinction between a stack and a queue is that a stack is LIFO and a queue is FIFO. Table 12-1 summarizes the time complexity below:

# Up Next👉 Part 13: Linked Lists (🔥🔥) (August 13-14, 2020) ### Discussion I think it's important to note that your stated time complexity is for your implementation of the data structures, as opposed to some property of the data structures themselves.

Enqueue and dequeue can be done with a time complexity of O(1), for example.  