aStacks and Queues 1. Introduction 2. Stacks 3. Queues 4. Stacks vs. Queues 5. Implementing Stack and Queue 5.1. Stack Implementation (using Linked List) 5.2. Stack Implementation (using Array) 5.3. Queue Implementation (using Linked List) 5.4. Queue Implementation using Stack

1. Introduction• Both stack and queue are linear data structures.– Linear data structures let us traverse through data sequentially.• The main difference between stack and queue is how data is removed from the data structure.• Unlike array, there's no random access operation.• We mainly use stacks and queues to run commands like push, peek and pop which deal exclusively with the element at the beginning or end of the data structure.• A simple way to remember stacks and queues are by using this analogy:– Stack → Plates– Queue → Waiting line• Stacks and queues are not the right data structure choice for search and lookup. They solely good for getting the first/last element of data structure. 2. Stacks• You can think of stacks as a bunch of plates stacked on top of each other, where you can only access the plate on the top. If you want to access plates in the middle you have to get to them by removing plates from the top.• This is called LIFO (Last In First Out). The last one added appears first.• Most programming languages are modeled with the stack architecture in mind. – When a function is called, usually they're called following the LIFO (think of function of functions cases).• Stacks are also used in browsing history or when you're writing something and want to undo something.• Most common operations for stacks are

Lookup	O(n)${\displaystyle O(n)}$
Pop	O(1)${\displaystyle O(1)}$
Push	O(1)${\displaystyle O(1)}$
Peek	O(1)${\displaystyle O(1)}$

Table 1:Big-O for Stacks

• • Note: The operation peek tells us what's the last element on the list.• 3. Queues• Queues are like stacks but they follow a FIFO (First In First Out) process (like a roller coaster).• Queues are used in applications like waiting list, restaurant table reservation, Uber rides, printers, etc.• Queues have similar operations to stacks. The enqueue is similar to push, and dequeue is similar to pop except that with dequeue the first element is removed.

Lookup	O(n)${\displaystyle O(n)}$
Dequeue	O(1)${\displaystyle O(1)}$
Enqueue	O(1)${\displaystyle O(1)}$
Peek	O(1)${\displaystyle O(1)}$

Table 2:Big-O for Queues

• • Note: The operation peek tells us what's the first element on the list.• Note: In creating queues, we don't use arrays because it's very inefficient (when removing an element we have shift all the other indexes). 4. Stacks vs. Queues• When building stacks, we can use either arrays or linked lists and they both have good performance. However, it's usually better to use arrays. – Arrays have cache locality which makes them faster when accessing its item on memory, because they're right next to each other.– Besides the memory efficiency, linked lists require more memory.– The only limitation of array in this case is the memory limit (versus the dynamic memory allocation of linked lists).– Eventually, based on your application, you could choose any of them.• For queues, we would never use arrays. We use linked lists.– With arrays, when we remove an element, we have to shift all the indexes.– In queues, removing the first element (i.e. First In), means we have to shift all the indexes.– With linked list, we have the pointer to the head node. We just need to move head by one. This is an O(1)${\displaystyle O(1)}$ operation. 5. Implementing Stack and Queue5.1. Stack Implementation (using Linked List)• Here, we use linked list to create a stack data structure.

class Node { constructor(value){ this.value = value; this.next = null; }} class Stack { constructor(){ this.top = null; this.bottom = null; this.length = 0; } peek() { return this.top; } push(value){ const newNode = new Node(value); if (this.length === 0) { this.top = newNode; this.bottom = newNode; } else { const holdingPointer = this.top; this.top = newNode; this.top.next = holdingPointer; } this.length++; return this; } pop(){ if (!this.top) { return null; } if (this.top === this.bottom) { this.bottom = null; } const holdingPointer = this.top; this.top = this.top.next; this.length--; return this; } //isEmpty} const myStack = new Stack();myStack.peek();myStack.push('google');myStack.push('udemy');myStack.push('discord');myStack.peek();myStack.pop();myStack.pop();myStack.pop();

5.2. Stack Implementation (using Array)• Here, we use arrays to build a stack data structure.

class Stack { constructor(){ this.array = []; } peek() { return this.array[this.array.length-1]; } push(value){ this.array.push(value); return this; } pop(){ this.array.pop(); return this; }} const myStack = new Stack();myStack.peek();myStack.push('google');myStack.push('udemy');myStack.push('discord');myStack.peek();myStack.pop();myStack.pop();myStack.pop();

5.3. Queue Implementation (using Linked List)• Here, we use linked lists to create a queue data structure.

class Node { constructor(value) { this.value = value; this.next = null; }} class Queue { constructor(){ this.first = null; this.last = null; this.length = 0; } peek() { return this.first; } enqueue(value){ const newNode = new Node(value); if (this.length === 0) { this.first = newNode; this.last = newNode; } else { this.last.next = newNode; this.last = newNode; } this.length++; return this; } dequeue(){ if (!this.first) { return null; } if (this.first === this.last) { this.last = null; } const holdingPointer = this.first; this.first = this.first.next; this.length--; return this; } //isEmpty;} const myQueue = new Queue();myQueue.peek();myQueue.enqueue('Joy');myQueue.enqueue('Matt');myQueue.enqueue('Pavel');myQueue.peek();myQueue.dequeue();myQueue.dequeue();myQueue.dequeue();myQueue.peek();

5.4. Queue Implementation using Stack• One of most common interview questions is to create a queue using stacks.• Here's one implementation in JS.

class CrazyQueue { constructor() { this.first = []; this.last = []; } enqueue(value) { const length = this.first.length; for (let i = 0; i < length; i++) { this.last.push(this.first.pop()); } this.last.push(value); return this; } dequeue() { const length = this.last.length; for (let i = 0; i < length; i++) { this.first.push(this.last.pop()); } this.first.pop(); return this; } peek() { if (this.last.length > 0) { return this.last[0]; } return this.first[this.first.length - 1]; }} const myQueue = new CrazyQueue();myQueue.peek();myQueue.enqueue('Joy');myQueue.enqueue('Matt');myQueue.enqueue('Pavel');myQueue.peek();myQueue.dequeue();myQueue.dequeue();myQueue.dequeue();myQueue.peek();