Table of contents
Open Table of contents
Stack
A stack is a linear type data structure that follows the Last In First Out (LIFO) principle means that the last element inserted in stack comes out first. You can think of the stack data structure as the pile of plates on top of another.
Stack has three main operations. They are:
- Push() — New element is added to the top of the stack
- Pop() — Removes and returns the top element from the stack
- Top()/peek() — Looks into the stack and return the last element inserted onto the stack.
Overflow and underflow
Overflow happens when we try to push more items on a stack than it can be hold. In details, when we try to push an item into a stack that has already reached its maximum size then the insertion will generate an error. So we need to check the stack condition before insertion.
Underflow happens when we try to pop an item from an empty stack. So in this situation pop operation will generate an error.
Application of Stack Data Structure
- Function calls and recursion
- Undo/Redo operations
- Expression evaluation
- Browser history
- Balanced Parentheses
- Backtracking Algorithms
Application of Stack in real life
- CD/DVD stand
- Stack of books in a book shop
- Call center systems
- Undo and Redo mechanism in text editors.
- The history of a web browser is stored in the form of a stack.
- Call logs, E-mails, and Google photos in any gallery are also stored in form of a stack.
- YouTube downloads and Notifications are also shown in LIFO format(the latest appears first).
- Allocation of memory by an operating system while executing a process.
Big O of common operations
Stack implementation using Linked List
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class Stack {
constructor() {
this.head = null;
this.length = 0;
}
push(value) {
let node= new Node(value)
node.next = this.head
this.head = node
this.length++
}
pop(){
if(this.isEmpty()) return
const removedNode = this.head
this.head = removedNode.next
this.length--
return removedNode.value
}
peek() {
if(this.isEmpty()) return
return this.head.value
}
isEmpty() {
return this.length === 0
}
print() {
if(this.isEmpty()) return
let data = this.head
while(data) {
console.log(data.value)
data = data.next
}
}
}
let stack = new Stack()
stack.push(5)
stack.push(10)
stack.push(15)
stack.push(20)
console.log(`POPed Value: ${stack.pop()}`)
console.log(`Head/peek Value: ${stack.peek()}`)
stack.print()
Queue
From wikipedia In computer science, a queue is a collection of entities that are maintained in a sequence and can be modified by the addition of entities at one end of the sequence and the removal of entities from the other end of the sequence.
So operations in queue are performed in First In First Out (FIFO) order - the item that inserts in first will come out first. You can think of the queue data structure as the ticket queue outside of a cinema hall.
Queue has three main operations. They are:
- Enqueue: Add an element to the end of the queue
- Dequeue: Remove an element from the front of the queue
- Peek: Get the value at the top of the queue without removing it
Application of Queue Data Structure
- Task Scheduling
- Resource Allocation
- Batch Processing
- Message Buffering
- Event Handling
- Traffic Management
- Operating systems
- Network protocols
- Printer queues
- Web servers
- When a resource is shared among multiple consumers. Examples include CPU scheduling, Disk Scheduling.
- When data is transferred asynchronously (data not necessarily received at the same rate as sent) between two processes. Examples include IO Buffers, pipes, etc.
- Buffer for devices like keyboard
- CPU Scheduling
- Memory management
- Queues in routers/ switches
- Mail Queues
Issues in applications of Queue
- Overflow: If a queue has a fixed size, it can become full, leading to a queue overflow. This can happen if elements are added to the queue faster than they are removed. To prevent overflow, some implementations use dynamic resizing or circular buffers.
- Underflow: If a queue is empty and an attempt is made to remove an element, this can lead to a queue underflow. This can happen if elements are removed from the queue faster than they are added. To prevent underflow, some implementations use sentinel values or null pointers to represent an empty queue.
Big O of common operations
Queue implementation using Linked List
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class Queue {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
enqueue(value) {
let node= new Node(value)
if(this.isEmpty()) {
this.head = node
this.tail = node
} else {
this.tail.next = node
this.tail = node
}
this.size++
}
dequeue(){
if(this.isEmpty()) return
const removedNode = this.head
if (this.size === 1) {
this.head = null
this.tail = null
this.size--
return removedNode.value
}
this.head = removedNode.next
this.size--
return removedNode.value
}
peek() {
if(this.isEmpty()) return
return this.head.value
}
isEmpty() {
return this.size === 0
}
print() {
if(this.isEmpty()) return
let data = this.head
while(data) {
console.log(data.value)
data = data.next
}
}
}
let queue = new Queue()
queue.enqueue(5)
queue.enqueue(10)
queue.enqueue(15)
queue.enqueue(20)
console.log(`POPed Value: ${queue.dequeue()}`)
console.log(`Head/peek Value: ${queue.peek()}`)
queue.print()
Deque
From wikipedia: In computer science, a double-ended queue (abbreviated to deque, pronounced deck, like "cheque") is an abstract data type that generalizes a queue, for which elements can be added to or removed from either the front (head) or back (tail).It is also often called a head-tail linked list, though properly this refers to a specific data structure implementation of a deque.
In short, it is a type of queue data structure that allows insertion and removal of elements from both ends(front or rear).
Application of Deque Data Structure
- Applied as both stack and queue, as it supports both operations.
- Storing a web browser’s history.
- Storing a software application’s list of undo operations.
- Job scheduling algorithm
- Palindrome checking
- Graph traversal
- Task scheduler
- Multi-level undo/redo functionality
- In computer science, deque can be used in many algorithms like LRU Cache, Round Robin Scheduling, Expression Evaluation.
Big O of common operations
Deque implementation using Linked List
The methods we will implement in this article is given below:
addToFront(value)
- add to the beginning of Deque.addToRear(value)
- add to the end of Deque.removeFromFront()
- remove from the beginning of DequeremoveFromRear()
- remove from the end of DequepeekFront()
- retrive first element in the DequepeekRear()
- retrive last element in the DequeisEmpty()
- helper method to check if Deque is emptyprint()
- optional method print Deque elements Here’s an example of a deque implementation in JavaScript:
class Node {
constructor(value) {
this.value = value;
this.next = null;
this.previous = null;
}
}
class Deque {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
addToFront(value) {
let node= new Node(value)
if(this.isEmpty()) {
this.head = node
this.tail = node
} else {
this.head.previous = node
node.next = this.head
this.head = node
}
this.size++
}
addToRear(value) {
let node= new Node(value)
if(this.isEmpty()) {
this.head = node
this.tail = node
} else {
this.tail.next = node
node.previous = this.tail
this.tail = node
}
this.size++
}
removeFromFront(){
if(this.isEmpty()) return
const removedNode = this.head
if (this.size === 1) {
this.head = null
this.tail = null
this.size--
return removedNode.value
}
this.head = removedNode.next
this.head.previous = null
this.size--
return removedNode.value
}
removeFromRear(){
if(this.isEmpty()) return
const removedNode = this.tail
if (this.size === 1) {
this.head = null
this.tail = null
this.size--
return removedNode.value
}
this.tail = removedNode.previous
this.tail.next = null
this.size--
return removedNode.value
}
peekFront() {
if(this.isEmpty()) return
return this.head.value
}
peekRear() {
if(this.isEmpty()) return
return this.tail.value
}
isEmpty() {
return this.size === 0
}
print() {
if(this.isEmpty()) return
let data = this.head
while(data) {
console.log(data.value)
data = data.next
}
}
}
let deque = new Deque()
deque.addToFront(5)
deque.addToRear(10)
deque.addToRear(15)
deque.addToRear(20)
deque.addToFront(2)
deque.print()
console.log(`Remove from front Value: ${deque.removeFromFront()}`)
console.log(`Remove from end Value: ${deque.removeFromRear()}`)
console.log(`Head Value: ${deque.peekFront()}`)
console.log(`Tail Value: ${deque.peekRear()}`)
deque.print()
Difference between Stack and Queue
- A stack is a data structure that stores a collection of elements, with operations to push (add) and pop (remove) elements from the top of the stack. A queue is a data structure that stores a collection of elements, with operations to enqueue (add) elements at the back of the queue, and dequeue (remove) elements from the front of the queue.
- Stacks are based on the LIFO principle, i.e., the element inserted at the last, is the first element to come out of the list. Queues are based on the FIFO principle, i.e., the element inserted at the first, is the first element to come out of the list.
- Stacks are often used for tasks that require backtracking, such as parsing expressions or implementing undo functionality. Queues are often used for tasks that involve processing elements in a specific order, such as handling requests or scheduling tasks.
- Insertion and deletion in stacks takes place only from one end of the list called the top. Insertion and deletion in queues takes place from the opposite ends of the list. The insertion takes place at the rear of the list and the deletion takes place from the front of the list.
- Insert operation is called push operation. Insert operation is called enqueue operation.
- Stacks are implemented using an array or linked list data structure. Queues are implemented using an array or linked list data structure.
- Delete operation is called pop operation. Delete operation is called dequeue operation.
- In stacks we maintain only one pointer to access the list, called the top, which always points to the last element present in the list. In queues we maintain two pointers to access the list. The front pointer always points to the first element inserted in the list and is still present, and the rear pointer always points to the last inserted element.
- Stack is used in solving problems works on recursion. Queue is used in solving problems having sequential processing.
- Stacks are often used for recursive algorithms or for maintaining a history of function calls. Queues are often used in multithreaded applications, where tasks are added to a queue and executed by a pool of worker threads.
- Stack does not have any types. Queue is of three types – 1. Circular Queue 2. Priority queue 3. double-ended queue.
- Examples of stack-based languages include PostScript and Forth. Examples of queue-based algorithms include Breadth-First Search (BFS) and printing a binary tree level-by-level.
References
- https://en.wikipedia.org/wiki/Stack_(abstract_data_type)
- https://www.geeksforgeeks.org/stack-data-structure/
- https://www.geeksforgeeks.org/applications-advantages-and-disadvantages-of-stack/
- https://www.sahinarslan.tech/posts/deep-dive-into-data-structures-using-javascript-stack
- https://en.wikipedia.org/wiki/Queue_(abstract_data_type)
- https://www.geeksforgeeks.org/applications-of-queue-data-structure/
- https://www.sahinarslan.tech/posts/deep-dive-into-data-structures-using-javascript-queue
- https://en.wikipedia.org/wiki/Double-ended_queue
- https://www.geeksforgeeks.org/deque-set-1-introduction-applications/
- https://www.sahinarslan.tech/posts/deep-dive-into-data-structures-using-javascript-deque-double-ended-queue
- https://www.geeksforgeeks.org/difference-between-stack-and-queue-data-structures/