Stacks and Queues
Stacks and Queues are two sides of the same coin in computer science. They are both simple data structures that hold multiple elements, but allow you to use a single element at a time. The biggest difference between the two structures is the order in which you can access the elements in the data structure.
In stacks, data follows Last In, First Out (LIFO), which basically means that whichever element you put in last will be the first element you take out. It acts exactly like a stack in real life. If you put a book on a stack of other books, the first book you will look at when sifting through the stack will be the book you just put on the stack.
In Queues, data follows First In, First Out (FIFO), which means that whichever element you put in first will be the first element you take out. Imagine a queue of people. It would be unfair if the first person in line for groceries were not the first person to receive attention once the attendant finally shows up.
For the most part, though, queues and stacks are treated the same way. There must be a way to:
- look at the first element (
top()) - to remove the first element (
pop()) - to push elements onto the data structure (
push())
The notation for this depends on the language you are using. Queues, for example, will often use dequeue() instead of pop() and front() instead of top(). You will see the language-specific details in the source code under the algorithms in this book, so for now it's simply important to know what stacks and queues are and how to access elements held within them.
Example Code
Here is a simple implementation of a stack:
interface IStack<T> {
/**
* `pop` removes last element from the stack and returns the same
*/
pop(): T;
/**
* `push` adds element to last of the stack and returns the size
*/
push(data: T): number;
/**
* `size` return size or length of the stack
*/
size(): number;
/**
* `top` returns last element of the stack
*/
top(): T;
}
class Stack<T> implements IStack<T> {
private readonly list: Array<T> = [];
public push(data: T) {
return this.list.push(data);
}
public pop() {
return this.list.pop();
}
public size() {
return this.list.length;
}
public top() {
return this.list[this.list.length - 1];
}
}
function exampleStack() {
const numberStack = new Stack<number>();
numberStack.push(4);
numberStack.push(5);
numberStack.push(9);
console.log(numberStack.pop());
console.log(numberStack.size());
console.log(numberStack.top());
}
exampleStack();
import java.util.List;
import java.util.ArrayList;
public class StackTest {
public static void main(String[] args) {
IStack<Integer> intStack = new Stack<>();
intStack.push(4);
intStack.push(5);
intStack.push(9);
System.out.println(intStack.pop());
System.out.println(intStack.size());
System.out.println(intStack.top());
}
}
interface IStack<T> {
/*
* 'pop' removed the last element from the stack and returns it
*/
T pop();
/*
* 'push' adds an element to at the end of the stack and returns the new size
*/
int push(T element);
/*
* 'size' returns the length of the stack
*/
int size();
/*
* 'top' returns the first element of the stack
*/
T top();
}
class Stack<T> implements IStack<T> {
private List<T> list;
public Stack() {
this.list = new ArrayList<>();
}
public T pop() {
return this.list.remove(this.size() - 1);
}
public int push(T element) {
this.list.add(element);
return this.size();
}
public int size() {
return this.list.size();
}
public T top() {
return this.list.get(this.size() - 1);
}
}
#include<iostream>
#include<cassert>
#include<memory>
namespace my {
/**
* implementation using linked list
* [value][next] -> [value][next] -> ... -> [value][next]
* (top Node) (intermediat Nodes)
* left most Node represents top element of stack
*/
template<typename T>
struct Node {
/**
* next: will store right Node address
*/
T value;
std::unique_ptr<Node<T>> next;
Node(const T& V) : value(V) { }
};
template<typename T>
class stack {
private:
/**
* top_pointer: points to left most node
* count: keeps track of current number of elements present in stack
*/
std::unique_ptr<Node<T>> top_pointer;
size_t count;
public:
stack() : count(0ULL) { }
void push(const T& element) {
auto new_node = std::make_unique<Node<T>>(element);
new_node->next = std::move(top_pointer);
top_pointer = std::move(new_node);
count = count + 1;
}
void pop() {
if (count > 0) {
top_pointer = std::move(top_pointer->next);
count = count - 1;
}
}
T& top() {
assert(count > 0 and "calling top() on an empty stack");
return top_pointer->value;
}
// returning mutable reference can very be usefull if someone wants to modify top element
T const& top() const {
assert(count > 0 and "calling top() on an empty stack");
return top_pointer->value;
}
size_t size() const { return count; }
bool empty() const { return count == 0; }
~stack() {
while (top_pointer.get() != nullptr) {
top_pointer = std::move(top_pointer->next);
}
}
};
}
int main() {
my::stack<int> intStack;
intStack.push(4);
intStack.push(5);
intStack.push(9);
int topElement = intStack.top();
intStack.pop();
std::cout << topElement << '\n';
std::cout << intStack.size() << '\n';
std::cout << intStack.top() << '\n';
return 0;
}
struct Stack<T> {
list: Vec<T>
}
impl<T> Stack<T> {
fn new() -> Self {
Stack {
list: Vec::new(),
}
}
// Note that this returns a reference to the value
// This is in contrast to pop which gives ownership of the value
fn top(&self) -> Option<&T> {
self.list.last()
}
fn pop(&mut self) -> Option<T> {
self.list.pop()
}
fn push(&mut self, item: T) {
self.list.push(item);
}
fn size(&self) -> usize {
self.list.len()
}
}
fn main() {
let mut i32stack: Stack<i32> = Stack::new();
i32stack.push(4);
i32stack.push(5);
i32stack.push(6);
println!("{:?}", i32stack.pop().unwrap()); // 6
println!("{:?}", i32stack.size()); // 2
println!("{:?}", i32stack.top().unwrap()); // 5
}
#!/usr/bin/env python3
__author__ = "Michael Ciccotosto-Camp"
from typing import TypeVar, Generic
T = TypeVar("T")
class Stack(Generic[T]):
def __init__(self) -> None:
self.__list: list[T] = []
def pop(self) -> T:
return self.__list.pop()
def push(self, element: T) -> int:
self.__list.append(element)
return len(self)
def top(self) -> T:
return self.__list[-1]
def __len__(self) -> int:
return len(self.__list)
def __str__(self) -> str:
return str(self.__list)
def main() -> None:
int_stack: Stack[int] = Stack()
int_stack.push(4)
int_stack.push(5)
int_stack.push(9)
print(int_stack.pop())
print(len(int_stack))
print(int_stack.top())
if __name__ == "__main__":
main()
Here is a simple implementation of a queue:
interface IQueue<T> {
/**
* `dequeue` removes first element from the queue and returns the same
*/
dequeue(): T;
/**
* `enqueue` adds element to last of the queue and returns the size
*/
enqueue(data: T): number;
/**
* `size` return size or length of the queue
*/
size(): number;
/**
* `front` returns first element of the queue
*/
front(): T;
}
class Queue<T> implements IQueue<T> {
private readonly list: Array<T> = [];
public enqueue(data: T) {
return this.list.push(data);
}
public dequeue() {
return this.list.shift();
}
public size() {
return this.list.length;
}
public front() {
return this.list[0];
}
}
function exampleQueue() {
const numberQueue = new Queue<number>();
numberQueue.enqueue(4);
numberQueue.enqueue(5);
numberQueue.enqueue(9);
console.log(numberQueue.dequeue());
console.log(numberQueue.size());
console.log(numberQueue.front());
}
exampleQueue();
import java.util.List;
import java.util.ArrayList;
public class QueueTest {
public static void main(String[] args) {
IQueue<Integer> intQueue = new Queue<>();
intQueue.enqueue(4);
intQueue.enqueue(5);
intQueue.enqueue(9);
System.out.println(intQueue.dequeue());
System.out.println(intQueue.size());
System.out.println(intQueue.front());
}
}
interface IQueue<T> {
/*
* 'dequeue' removes the first element from the queue and returns it
*/
T dequeue();
/*
* 'enqueue' adds an element at the end of the queue and returns the new size
*/
int enqueue(T element);
/*
* 'size' returns the size of the queue
*/
int size();
/*
* 'front' returns the first element of the queue without removing it
*/
T front();
}
class Queue<T> implements IQueue<T> {
private List<T> list;
public Queue() {
this.list = new ArrayList<>();
}
public T dequeue() {
return this.list.remove(0);
}
public int enqueue(T element) {
this.list.add(element);
return this.size();
}
public int size() {
return this.list.size();
}
public T front() {
return this.list.get(0);
}
}
#include<iostream>
#include<memory>
#include<cassert>
namespace my {
/**
* implementation using linked list
* [value][next] -> [value][next] -> ... -> [value][next]
* (front Node) (intermediat Nodes) (rear Node)
*/
template<typename T>
struct Node {
/**
* next: will store right Node address
*/
T value;
std::shared_ptr<Node<T>> next;
Node(const T& V) : value(V) { }
};
template<typename T>
class queue {
private:
/**
* front_pointer: points to left most node
* count: keeps track of current number of elements present in queue
* rear_pointer: points to most recent Node added into the queue, which is right most Node
*/
std::shared_ptr<Node<T>> front_pointer;
std::shared_ptr<Node<T>> rear_pointer;
size_t count;
public:
queue() : count(0ULL) { }
void enqueue(const T& element) {
auto new_node = std::make_shared<Node<T>>(element);
if (count > 0) {
rear_pointer->next = new_node;
rear_pointer = new_node;
} else {
rear_pointer = front_pointer = new_node;
}
count = count + 1;
}
void dequeue() {
if (count > 1) {
front_pointer = front_pointer->next;
count = count - 1;
} else if (count == 1) {
front_pointer.reset();
rear_pointer.reset();
count = count - 1;
}
}
T& front() {
assert(count > 0 && "calling front on an empty queue");
return front_pointer->value;
}
T const& front() const {
assert(count > 0 && "calling front on an empty queue");
return front_pointer->value;
}
size_t size() const { return count; }
bool empty() const { return count == 0; }
~queue() {
while (front_pointer.get() != nullptr) {
front_pointer = front_pointer->next;
}
}
};
}
int main() {
my::queue<int> intQueue;
intQueue.enqueue(4);
intQueue.enqueue(5);
intQueue.enqueue(9);
int frontElement = intQueue.front();
intQueue.dequeue();
std::cout << frontElement << '\n';
std::cout << intQueue.size() << '\n';
std::cout << intQueue.front() << '\n';
return 0;
}
use std::collections::VecDeque;
struct Queue<T> {
list: VecDeque<T>
}
impl<T> Queue<T> {
fn new() -> Self {
Queue{
list: VecDeque::new(),
}
}
// Note that this returns a reference to the value
// This is in contrast to dequeue which gives ownership of the value
fn front(&self) -> Option<&T> {
self.list.front()
}
fn dequeue(&mut self) -> Option<T> {
self.list.pop_front()
}
fn enqueue(&mut self, item: T) {
self.list.push_back(item);
}
fn size(&self) -> usize {
self.list.len()
}
}
fn main() {
let mut i32queue = Queue::new();
i32queue.enqueue(4);
i32queue.enqueue(5);
i32queue.enqueue(6);
println!("{:?}", i32queue.dequeue().unwrap()); // 4
println!("{:?}", i32queue.size()); // 2
println!("{:?}", i32queue.front().unwrap()); // 5
}
#!/usr/bin/env python3
__author__ = "Michael Ciccotosto-Camp"
from typing import TypeVar, Generic
T = TypeVar("T")
class Queue(Generic[T]):
def __init__(self) -> None:
self.__list: list[T] = list()
def dequeue(self) -> T:
return self.__list.pop(0)
def enqueue(self, element: T) -> int:
self.__list.append(element)
return len(self)
def front(self) -> T:
return self.__list[0]
def __len__(self) -> int:
return len(self.__list)
def __str__(self) -> str:
return str(self.__list)
def main() -> None:
int_queue: Queue[int] = Queue()
int_queue.enqueue(4)
int_queue.enqueue(5)
int_queue.enqueue(9)
print(int_queue.dequeue())
print(len(int_queue))
print(int_queue.front())
if __name__ == "__main__":
main()
License
Code Examples
The code examples are licensed under the MIT license (found in LICENSE.md).
Text
The text of this chapter was written by James Schloss and is licensed under the Creative Commons Attribution-ShareAlike 4.0 International License.
Pull Requests
After initial licensing (#560), the following pull requests have modified the text or graphics of this chapter:
- none