The next step is to explore more specialized types of collections.
In this article, we cover Stacks and Queues.
Some languages, such as Java, C++, and C#, have built-in support for stacks and queues.
Other languages, like JavaScript, use the array data type with methods that can emulate stacks and queues. In Python, the
collections package provides the deque class, which can function as a stack or a queue. For languages without built-in support, stacks and queues can be implemented by creating a class with a list as an attribute and adding specific methods.Stack
A stack is a collection of items that follows the principle of Last In, First Out (LIFO).
A stack functions like a pile of books where books can only be added to the top and removed from the top. The last book added to the pile is the first one that can be removed.
A stack typically has two primary methods:
- push(): Adds an element to the top of the stack.
- pop(): Removes the element from the top of the stack and returns its value.
Additionally, there is an optional method:
- peek(): Returns the element at the top of the stack without removing it.
Some languages may also implement the following (though these are not standardized):
- length() or size(): Returns the number of elements in the stack.
- empty() or isEmpty(): Returns true if the stack is empty.
If a pop() is called on an empty stack, the behavior depends on the language. Some languages return a null or default value, while others raise an exception.
You can alternate push() and pop() operations freely as long as you avoid calling pop() on an empty stack.
In pseudo-code it would look like this:
stack = []
# empty stack
stack.push('Moby Dick')
# stack has one element
stack.push('War and Peace')
# stack has 2 elements
print(stack.pop())
# prints 'War and Peace' and it only has 'Moby Dick'
print(stack.peek())
# prints 'Moby Dick' and it doesn't changes the stack
stack.push('Meditations')
# stack as 2 elementsHow to implement a Stack in Java
Java provides the Stack class in the java.util package, which extends Vector and implements the List interface.
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Stack<String> bookStack = new Stack<>();
bookStack.push("Moby Dick");
bookStack.push("War and Peace");
bookStack.push("Meditations");
System.out.println("Top book: " + bookStack.peek()); // Displays Meditations
System.out.println("Popped book: " + bookStack.pop()); // Displays Meditations and removes it
System.out.println("New top book: " + bookStack.peek());
}
}How to implement a Stack in JavaScript
JavaScript does not have a built-in stack class, but you can use an array with methods like push() and pop() which mimic stack operations:
let bookStack = [];
bookStack.push('Moby Dick');
bookStack.push('War and Peace');
bookStack.push('Meditations');
// JavaScript has no peek method
console.log("Top book:", bookStack[bookStack.length - 1]); // peek operation
console.log("Popped book:", bookStack.pop());
console.log("New top book:", bookStack[bookStack.length - 1]); // peek after popHow to implement a Stack in Python
Python doesn’t have a built-in implementation of a stack but it has collections.deque which can be used both for stacks and queues.
An alternative it’s to implement it as a class having a list as an attribute, this implementation is slower but enforces the usage of only the stack methods.
from collections import deque
book_stack = deque()
# python uses append method to add elements to the stack instead of push
book_stack.append('Moby Dick')
book_stack.append('War and Peace')
book_stack.append('Meditations')
# python doesn't have a peek method
print("Books in the stack (top to bottom):")
while len(book_stack):
print(book_stack.pop())
# It will display:
# Meditations
# War and Peace
# Moby Dick
# ------------------------------------------------------
# Implementation as a class
# ------------------------------------------------------
class Stack:
def __init__(self):
self._items = []
def push(self, item):
self._items.append(item)
def pop(self):
if not self.is_empty():
return self._items.pop()
else:
raise IndexError("Stack is empty")
def peek(self):
return self._items[-1] if not self.is_empty() else None
def is_empty(self):
return len(self._items) == 0
book_stack = Stack()
book_stack.push('Moby Dick')
book_stack.push('War and Peace')
book_stack.push('Meditations')
print("Top book:", book_stack.peek()) # Displays Meditations but doesn't removes
print("Popped book:", book_stack.pop()) # Displays Meditations and removes it
print("Popped book:", book_stack.pop()) # Displays War and Peace and removes itUse Cases of Stacks
Stacks operate on the LIFO (Last In, First Out) principle, where the last element added is the first one removed. They are suitable for tasks that require reversing or tracking execution flow.
- Expression Evaluation and Parsing:
- Convert infix expressions to postfix/prefix.
- Evaluate postfix expressions.
- Undo Operations in Text Editors:
- Store states of text for undo operations.
- Browser Navigation:
- Maintain history of visited pages (back/forward navigation).
- Call Stack in Recursion:
- Manage function calls and local variables during recursive execution.
- Parenthesis Matching:
- Validate balanced brackets in code or mathematical expressions.
- Reversing Data:
- Reverse strings, linked lists, or other data.
- Syntax Parsing in Compilers:
- Manage tokens for syntax checking and parsing.
Queue
A queue is a collection of items that follows the principle of First In, First Out (FIFO).
A queue is better visualized as a row rather than a pile. Unlike a stack, where items are added to the top, in a queue, items are added to the back and removed from the front, similar to a line of people.
In fact, a line of people is an excellent analogy for how a queue works as an abstract data type: people join the queue at the back and are attended to at the front. The last person to arrive must wait until everyone ahead of them has been served.
A queue typically has two primary methods:
- enqueue(): Adds an element to the back of the queue.
- dequeue(): Removes the element from the front of the queue and returns its value.
Additionally, there is an optional method:
- peek() or front(): Returns the element at the front of the queue without removing it.
Some languages may also implement the following (though these are not standardized):
- length() or size(): Returns the number of elements in the queue.
- empty() or isEmpty(): Returns true if the queue is empty.
If a dequeue() operation is called on an empty queue, the behavior depends on the language. Some languages return a null or default value, while others raise an exception.
You can freely interleave enqueue() and dequeue() operations as long as you avoid calling dequeue() on an empty queue.
In pseudo-code it would look like this:
queue = []
# empty queue
queue.enqueue('James')
# queue has one element
queue.enqueue('Mary')
# queue has 2 elements: 'Mary', 'James'
queue.enqueue('Victor')
# queue has 3 elements
print(queue.dequeue())
# prints 'James' and it has 'Victor' and 'Mary'
print(queue.peek())
# prints 'Mary' and it doesn't changes the queue
queue.enqueue('James')
# queue has 3 elements: 'James', 'Victor', 'Mary'How to implement a Queue in Java
Java doesn’t have a Queue class like it does for Stack, but it provides a Queue interface along with several classes that implement queue functionality, such as LinkedList, PriorityQueue, and ArrayDeque.
The choice of class depends on its intended usage and whether thread safety is required.
For example:
- The
LinkedListclass offers a simple and efficient way to implement a queue if multithreading isn’t needed. - As a learner,
LinkedListis often the best option to start with.
The Queue interface in Java also uses specific method names for queue operations:
offer(): Adds an element to the back of the queue.poll(): Removes and returns the element at the front of the queue.
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static void main(String[] args) {
Queue<String> peopleQueue = new LinkedList<>();
peopleQueue.offer("James");
peopleQueue.offer("Mary");
peopleQueue.offer("Victor");
System.out.println("Front person: " + peopleQueue.peek()); // Displays James
System.out.println("Removed person: " + peopleQueue.poll()); // Removes and displays James
System.out.println("New front person: " + peopleQueue.peek()); // Displays Mary
}
}How to implement a Queue in JavaScript
JavaScript does not have a built-in Queue class, but you can use an array to mimic queue operations using methods like push() and shift() to implement enqueue() and dequeue().
For better encapsulation, you can create a wrapper class to define enqueue() and dequeue() methods, preventing access to other array methods like pop(), which could break the queue's principles.
class Queue {
constructor() {
this.items = [];
}
enqueue(element) {
this.items.push(element);
}
dequeue() {
if (this.isEmpty()) {
return "Queue is empty";
}
return this.items.shift();
}
peek() {
if (this.isEmpty()) {
return "Queue is empty";
}
return this.items[0];
}
isEmpty() {
return this.items.length === 0;
}
}
const peopleQueue = new Queue();
peopleQueue.enqueue("James");
peopleQueue.enqueue("Mary");
peopleQueue.enqueue("Victor");
console.log("Front person: " + peopleQueue.peek()); // Displays James
console.log("Removed person: " + peopleQueue.dequeue()); // Removes and displays James
console.log("New front person: " + peopleQueue.peek()); // Displays MaryHow to implement a Queue in Python
Python offers multiple ways to implement a queue:
- Using the
Queueclass from thequeuemodule:
- This implementation is thread-safe, making it suitable for multithreaded environments.
- However, it doesn’t support a
peek()method and comes with the overhead of multithreading support.
- Using the
dequeclass from thecollectionsmodule:
- This is a faster implementation, supporting
peek()and other queue operations efficiently. - However, it does not enforce strict queue behavior, allowing deviations from the standard principles.
from collections import deque
import queue
people_queue = queue.Queue()
people_queue.put("James")
people_queue.put("Mary")
people_queue.put("Victor")
print(people_queue.get()) # Output: James
print(people_queue.get()) # Output: Mary
# ------------------------------------------------------
# Implementation using collections.deque
# ------------------------------------------------------
people_queue = deque()
people_queue.append("James")
people_queue.append("Mary")
people_queue.append("Victor")
print("Front person: " + people_queue[0]) # Displays James
print("Removed person: " + people_queue.popleft()) # Removes and displays James
print("New front person: " + people_queue[0]) # Displays MaryUse Cases of Queues
Queues operate on the FIFO (First In, First Out) principle, where the first element added is the first one removed. They are used in scenarios involving order preservation and sequential processing.
- Scheduling Tasks:
- CPU scheduling (e.g., round-robin).
- Print job management in a printer queue.
- Data Buffers:
- Buffers in IO operations or network communication.
- Streaming services like video or audio playback.
- Asynchronous Processing:
- Message queues in distributed systems (e.g., RabbitMQ, Kafka).
- Order Processing Systems:
- Task queues in online systems for order fulfillment.
- Simulation of Real-World Queues:
- Customer service lines, ticket counters.
- Load Balancing:
- Distributing tasks among multiple servers or processes.
- Real-Time Systems:
- Event-driven systems like real-time monitoring or logging.
Practical Example of Stack Operations
One common application of stacks is implementing an undo functionality. In the project below, JavaScript manages a draggable element that records each drop position in the positionStack variable. Each new position is pushed onto the stack as the element is moved. The undo button uses this stack to revert the element to its previous position by removing the last recorded entry. This project demonstrates how stacks can effectively track and manage changes, making them essential for handling undo operations in various applications.
You can see it in action on this CodePen.
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Draggable Div with Undo</title>
<style>
body {
margin: 0;
overflow: hidden;
}
.draggable {
position: absolute;
top: 100px;
left: 100px;
width: 100px;
height: 50px;
border: 2px solid black;
text-align: center;
line-height: 50px;
cursor: grab;
user-select: none;
}
button {
position: absolute;
top: 10px;
left: 10px;
padding: 10px;
}
</style>
</head>
<body>
<div id="draggable" class="draggable">Drag Me</div>
<button id="undo">Undo</button>
<script>
const draggable = document.getElementById('draggable');
const undoButton = document.getElementById('undo');
const positionStack = [];
let isDragging = false;
let offsetX = 0;
let offsetY = 0;
draggable.addEventListener('mousedown', (event) => {
isDragging = true;
offsetX = event.clientX - draggable.offsetLeft;
offsetY = event.clientY - draggable.offsetTop;
positionStack.push({ top: draggable.style.top, left: draggable.style.left });
});
document.addEventListener('mousemove', (event) => {
if (isDragging) {
draggable.style.top = `${event.clientY - offsetY}px`;
draggable.style.left = `${event.clientX - offsetX}px`;
}
});
document.addEventListener('mouseup', () => {
isDragging = false;
});
undoButton.addEventListener('click', () => {
if (positionStack.length > 0) {
const lastPosition = positionStack.pop();
draggable.style.top = lastPosition.top;
draggable.style.left = lastPosition.left;
}
});
</script>
</body>
</html>
