Data Structures & Algorithms – Stacks and queues
Stacks and queues are two commonly used data structures that have different behavior for adding and removing elements.
- Stacks: A stack is a Last In First Out (LIFO) data structure, where the last element added is the first one to be removed. It has two main operations: push and pop. Push adds an element to the top of the stack and pop removes the element from the top. The element at the top of the stack is called the top element.
Here is an example of how to implement a stack in Python:
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()
def is_empty(self):
return len(self.items) == 0
def peek(self):
if not self.is_empty():
return self.items[-1]
And here is an example of how to implement a stack in JavaScript:
class Stack {
constructor() {
this.items = [];
}
push(item) {
this.items.push(item);
}
pop() {
if (!this.isEmpty()) {
return this.items.pop();
}
}
isEmpty() {
return this.items.length === 0;
}
peek() {
if (!this.isEmpty()) {
return this.items[this.items.length - 1];
}
}
}
And here is an example of how to implement a stack in Java:
import java.util.ArrayList;
import java.util.List;
class Stack {
List<Integer> stack;
public Stack() {
stack = new ArrayList<>();
}
public void push(int item) {
stack.add(item);
}
public int pop() {
if (!isEmpty()) {
return stack.remove(stack.size() - 1);
}
return -1;
}
public boolean isEmpty() {
return stack.isEmpty();
}
public int peek() {
if (!isEmpty()) {
return stack.get(stack.size() - 1);
}
return -1;
}
}
And here is an example of how to implement a stack in Rust:
struct Stack {
items: Vec<i32>
}
impl Stack {
fn new() -> Self {
Stack { items: Vec::new() }
}
fn push(&mut self, item: i32) {
self.items.push(item);
}
fn pop(&mut self) -> Option<i32> {
self.items.pop()
}
fn is_empty(&self) -> bool {
self.items.is_empty()
}
fn peek(&self) -> Option<&i32> {
self.items.last()
}
}
- Queues: A queue is a First In First Out (FIFO) data structure, where the first element added is the first one to be removed. It has two main operations: enqueue and dequeue. Enqueue adds an element to the back of the queue and dequeue removes the element from the front. The element at the front of the queue is called the front element.
Here is an example of how to implement a queue in Python:
class Queue:
def __init__(self):
self.items = []
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
if not self.is_empty():
return self.items.pop(0)
def is_empty(self):
return len(self.items) == 0
def peek(self):
if not self.is_empty():
return self.items[0]
And here is an example of how to implement a queue in JavaScript:
class Queue {
constructor() {
this.items = [];
}
enqueue(item) {
this.items.push(item);
}
dequeue() {
if (!this.isEmpty()) {
return this.items.shift();
}
}
isEmpty() {
return this.items.length === 0;
}
peek() {
if (!this.isEmpty()) {
return this.items[0];
}
}
}
And here is an example of how to implement a queue in Java:
import java.util.LinkedList;
import java.util.Queue;
class Queue {
private Queue<Integer> queue;
public Queue() {
queue = new LinkedList<>();
}
public void enqueue(int item) {
queue.add(item);
}
public int dequeue() {
if (!isEmpty()) {
return queue.remove();
}
return -1;
}
public boolean isEmpty() {
return queue.isEmpty();
}
public int peek() {
if (!isEmpty()) {
return queue.peek();
}
return -1;
}
}
And here is an example of how to implement a queue in Rust:
struct Queue {
items: Vec<i32>
}
impl Queue {
fn new() -> Self {
Queue { items: Vec::new() }
}
fn enqueue(&mut self, item: i32) {
self.items.push(item);
}
fn dequeue(&mut self) -> Option<i32> {
self.items.pop()
}
fn is_empty(&self) -> bool {
self.items.is_empty()
}
fn peek(&self) -> Option<&i32> {
self.items.first()
}
}
In conclusion, stacks and queues are two commonly used data structures that have different behavior for adding and removing elements. A stack is a LIFO data structure where the last element added is the first one to be removed while a queue is a FIFO data structure where the first element added is the first one to be removed. Both data structures have their own use cases and trade-offs, and it is important to understand the requirements of your application before choosing a data structure. The examples provided are basic implementations of the data structures and may not be suitable for production use without additional error handling and optimization.