✍️ Note
Some codes and contents are sourced from Udemy. This post is for personal notes where I summarize the original contents to grasp the key concepts (🎨 some images I draw it)
Introduction
You may think Stack and Queue is very basic structure and It’s very easy. Yes that’s true but utilizing them together is bit tricky. That’s why I summarized these data structure. (As I mentioned earlier, all the contents are sourced from Udemy lecture, I rewrite sample code in Swift)
Stack
A stack is a data structure to hold elements such that the last element you add to the stack is the first one you access
LIFO: Last In First Out
Always focused on the end of the stack, called the POP
Push – Push an element to the top of a stack
Pop – Pop an element from the top of a stack
Peek – Peet at the top element of a stack (Don’t remove an element!) You access the top element in the stack without actually changing the data structure
Other operations which are useful
IsEmpty, IsFull, Size
Exception case
- When you try to pop from an empty stack -> throw an exception
- Push into a full stack -> throw an exception, Yes It is stack overflow!
Summary
- The most common operations on a stack involve pushing and popping elements from the top.
- The operations are confined to one end of the stack
- A linked list lends itself perfectly to build a stack
Performance and Complexity
- Push and Pop (Using Linked List or Array) is O(1)
- isEmpty, isFull also O(1)
- check size -> O(1)
Space Complexity
- O(N)
Where can stacks be used?
https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8463684#overview
- Implementing undo in an application
- Implementing the back button on the web browser
- Holding the memory for recursive calls in a programming language
- Translating infix notation (a+b) for expressions to postfix (ab+)
- programming languages converts infix to postfix
Example 1. Use a Single Linked List
//A Single Element in the linked list
class Element<T> {
var data: T
var next: Element?
init(data: T, next: Element?) {
self.data = data
self.next = next
}
}
enum StackError: Error {
//Pushing into a full stack
case stackOverflow
//Popping from or peeking into an empty stack
case stackUnderflow
}
class Stack<T> {
private let maxSize: Int
//Topmost element in the stack
private var top: Element<T>?
//Track the size of the stack at every push, pop
//This means the stack size operation can be constant time
private var size = 0
init(maxSize: Int) {
self.maxSize = maxSize
}
func push(data: T) throws {
if size == maxSize {
throw StackError.stackOverflow
}
//Create a new element to hold the data and point top to it. Make sure you increment the size of the stack
var newElement = Element(data: data, next: top)
top = newElement
size += 1
}
func pop() throws -> T {
if size == 0 {
throw StackError.stackUnderflow
}
guard let topElement = top else {
throw StackError.stackUnderflow
}
let data = topElement.data
//Remove the top element from the stack and return it's data
top = topElement.next
size -= 1
return data
}
func peek() throws -> T {
if size == 0 {
throw StackError.stackUnderflow
}
guard let topElement = top else {
throw StackError.stackUnderflow
}
//Just return the data of the top element, do not remove it
return topElement.data
}
var isEmpty: Bool {
size == 0
}
var isFull: Bool {
size == maxSize
}
}
Example 2. Use an Array (It’s more simple, In swift array can increased the size at runtime)
Every array reserves a specific amount of memory to hold its contents. When you add elements to an array and that array begins to exceed its reserved capacity, the array allocates a larger region of memory and copies its elements into the new storage. The new storage is a multiple of the old storage’s size. This exponential growth strategy means that appending an element happens in constant time, averaging the performance of many append operations. Append operations that trigger reallocation have a performance cost, but they occur less and less often as the array grows larger.
If you know approximately how many elements you will need to store, use the
reserveCapacity(_:)method before appending to the array to avoid intermediate reallocations. Use thecapacityandcountproperties to determine how many more elements the array can store without allocating larger storage.For arrays of most
https://developer.apple.com/documentation/swift/arrayElementtypes, this storage is a contiguous block of memory. For arrays with anElementtype that is a class or@objcprotocol type, this storage can be a contiguous block of memory or an instance ofNSArray. Because any arbitrary subclass ofNSArraycan become anArray, there are no guarantees about representation or efficiency in this case.
enum StackError: Error {
//Pushing into a full stack
case stackOverflow
//Popping from or peeking into an empty stack
case stackUnderflow
}
class Stack<T> {
private let maxSize: Int
private(set) var array = Array<T>()
//Topmost element in the stack
private var top: T?
//Track the size of the stack at every push, pop
//This means the stack size operation can be constant time
private var size = 0
init(maxSize: Int) {
self.maxSize = maxSize
}
func push(data: T) throws {
if size == maxSize {
throw StackError.stackOverflow
}
array.append(data)
top = data
size += 1
}
func pop() throws -> T {
if size == 0 {
throw StackError.stackUnderflow
}
//Remove the top element from the stack and return it's data
let topElement = array.removeLast()
top = array.last
size -= 1
return topElement
}
func peek() throws -> T {
if size == 0 {
throw StackError.stackUnderflow
}
guard let topElement = top else {
throw StackError.stackUnderflow
}
//Just return the data of the top element, do not remove it
return topElement
}
var isEmpty: Bool {
size == 0
}
var isFull: Bool {
size == maxSize
}
}
let stack = Stack<Int>(maxSize: 10)
try? stack.push(data: 1)
try? stack.push(data: 2)
try? stack.push(data: 3)
try? stack.pop()
try? stack.pop()
try? stack.pop()
Exercise 1. Match parenthesis in an expression
Check whether an expression has well-formed parenthesis I.E The opening and the closing brackets match
Use a Stack to store the opening brackets each time you encounter one
For every closing bracket compare to the last element pushed onto the stack
https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8463688#overview
Example
- (ABC){DEF}[XYZ(LMN)] -> Match
- (ABC{DEF}[XYZ(LMN)] -> Mismatch
- (ABC){DEF}[XYZ(LMN)]} -> Mismatch
//Key is closed brackets, value is open brackets
var brackets = [")": "(", "]": "[", "}": "{"]
var openBrackets = Set(brackets.values)
print(openBrackets)
func matchingParenthesis(input: String) -> Bool {
let stack = Stack<String>(maxSize: input.count)
var inputStringArray = input.compactMap { String($0)}
for c in inputStringArray {
if openBrackets.contains(c) {
try? stack.push(data: c)
}
//Check close bracket
if brackets.keys.contains(c) {
//Pop open brackets
let poppedValue = try? stack.pop()
//Check Is poppedValue openBracket or not
if poppedValue != brackets[c] {
return false
}
}
}
return stack.isEmpty
}
matchingParenthesis(input: "(ABC){DEF}[XYZ(LMN)]")
matchingParenthesis(input: "(ABC{DEF}[XYZ(LMN)]")
matchingParenthesis(input: "(ABC){DEF}[XYZ(LMN)]}")
Exercise 2. Find the minimum element in a stack in constant time
Keep track of the minimum element for each element pushed on to the stack
Have 2 stacks, one to hold the actual elements, and another to hold the minimum element corresponding to every element added to the stack
When each element is pushed onto the stack compare it with the last minimum element and push both the main stack and the minimum element stack together
Do the same when popping an element from the stack
https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8463690#overview
func findMinValue(input: [Int]) -> Int? {
let stack = Stack<Int>(maxSize: input.count)
let minStack = Stack<Int>(maxSize: input.count)
for n in input {
try? stack.push(data: n)
if minStack.isEmpty == true {
try? minStack.push(data: n)
}
else {
if let peekMinValue = try? minStack.peek() {
//Compare peekValue from MinStack and current value in input
let currentMinValue = n < peekMinValue ? n : peekMinValue
try? minStack.push(data: currentMinValue)
}
}
}
return try? minStack.peek()
}
findMinValue(input: [4, 5, 3, 2, 9])
Or you can create a MinimumStack class like below
enum StackError: Error {
//Pushing into a full stack
case stackOverflow
//Popping from or peeking into an empty stack
case stackUnderflow
}
class Stack<T> {
private let maxSize: Int
private(set) var array = Array<T>()
//Topmost element in the stack
private var top: T?
//Track the size of the stack at every push, pop
//This means the stack size operation can be constant time
private var size = 0
init(maxSize: Int) {
self.maxSize = maxSize
}
func push(data: T) throws {
if size == maxSize {
throw StackError.stackOverflow
}
array.append(data)
top = data
size += 1
}
func pop() throws -> T {
if size == 0 {
throw StackError.stackUnderflow
}
//Remove the top element from the stack and return it's data
let topElement = array.removeLast()
top = array.last
size -= 1
return topElement
}
func peek() throws -> T {
if size == 0 {
throw StackError.stackUnderflow
}
guard let topElement = top else {
throw StackError.stackUnderflow
}
//Just return the data of the top element, do not remove it
return topElement
}
var isEmpty: Bool {
size == 0
}
var isFull: Bool {
size == maxSize
}
}
class MinimumStack<T: Comparable> {
private let maxSize: Int
private let stack: Stack<T>
private let minimumStack: Stack<T>
init(maxSize: Int) {
self.maxSize = maxSize
self.stack = Stack<T>(maxSize: maxSize)
self.minimumStack = Stack<T>(maxSize: maxSize)
}
func push(data: T) throws {
var min = data
if !minimumStack.isEmpty {
let peekMinValue = try minimumStack.peek()
if min > peekMinValue {
min = peekMinValue
}
}
try stack.push(data: data)
try minimumStack.push(data: min)
}
func pop() throws -> T {
try minimumStack.pop()
return try stack.pop()
}
func minimumValue() throws -> T {
return try minimumStack.peek()
}
}
let input = [4, 5, 3, 2, 9]
let minimumStack = MinimumStack<Int>(maxSize: input.count)
for n in input {
try? minimumStack.push(data: n)
}
try? minimumStack.minimumValue()
Queue
A queue is a data structure where you add elements to the end of the queue and remove elements from the beginning of the queue
FIFO: First In First Out == LILO: List In Last Out
The operations on a Queue are performed at two ends, removal is at the beginning and addition is at the end of the Queue.
Operations
- Enqueue
- Adding a new element to the end of the queue is called
- Enqueue an element from the queue
- Dequeue
- Removing an element from the beginning of a queue is called
- Dequeue an element from the queue
- Peek
- Similar to a stack you might just want to see what the first element in a queue is without removing it
- Peek at the first element in a queue
- Offer
- The queue implementation in Java has another useful method
- Add to a queue if space is available
Edge case
- What if you try to dequeue from an empty queue?
- Or Enqueue into a full queue?
- -> Throw an exception!
Underlying Data Structure
https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8463696#overview
- Linked List is commonly used
- The most common operations on a queue involve enqueuing and dequeuing elements
- The operations are on both ends of the queue
- A linked list with a pointer to head and the tail works well
- A common data structure used is a circular queue with pointers to the head and to the tail
Enqueue
Dequeue
Exercise 1. Circular Queue
It can be implemented using an array where the last element wraps around to the first element
Implementation
https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8463698#overview
- Head = -1
- A special value to denote an empty list
- Tail
- Always indicates last index
Enqueue datas until It is full
Dequeue n items
enum QueueError: Error {
case queueOverflow
case queueUnderflow
}
class Queue {
private let specialEmptyValue = -1
private let size: Int
private var items = Array<Int?>()
//Initialize both the head and the tail indices to the special value
private var headIndex: Int
private var tailIndex: Int
init(size: Int) {
headIndex = specialEmptyValue
tailIndex = specialEmptyValue
self.size = size
//Create an array with fixed size
self.items = Array(repeating: nil, count: size)
}
//Enqueue doesn't affect headIndex except for empty case
func enqueue(data: Int) throws {
if isFull {
throw QueueError.queueOverflow
}
//Get the next tail index and insert the new element there
tailIndex = (tailIndex + 1) % items.count
items[tailIndex] = data
//This is the first element enqueued, set the head index to the tail index
if headIndex == specialEmptyValue {
headIndex = tailIndex
}
}
func dequeue() throws -> Int {
if isEmpty {
throw QueueError.queueUnderflow
}
guard let firstElement = items[headIndex] else {
throw QueueError.queueUnderflow
}
//Edge case - This element is the last item in a queue (It means there is only one item in a queue)
if headIndex == tailIndex {
headIndex = specialEmptyValue
}
else {
headIndex = (headIndex + 1) % items.count
}
return firstElement
}
//Headindex is always set to special marker value when the queue is empty
var isEmpty: Bool {
headIndex == specialEmptyValue
}
//WHen the queue is full this means that the head index and tail index are right next to one another
var isFull: Bool {
let nextIndex = (tailIndex + 1) % items.count
//Check whether the next position of the tail is the head index
return nextIndex == headIndex
}
}
The Queue – Performance and Complexity
https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8463698#overview
- Enqueuing and Dequeuing implemented in this way is O(1)
- IsEmpty and IsFull is also O(1)
- Space complexity is O(N)
Exercise 2. Build a Queue with Two Stack
Where can a queue be used?
- Customer service hotline, calls are assigned to representatives in the order that they are received
- Queueing jobs to be printed
- Any order processing systems like in e-commerce websites or bank transaction systems
Implement a Queue using two stacks
https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8463700#overview
- Forward Stack
- It used to push the enqueued elements
- Enqueue operations are always performed on the forward stack
- Enqueue requires moving all elements to the forward stack and pushing the last element in I.E. The top
- Reverse Stack
- Holds the elements in reverse order from the forward stack
- Dequeue operations are always performed on the reverse stack
- Dequeue requires moving all elements to the reverse track and popping the last element in I.E the Top
So It looks tricky. It has 2 stacks to implement Enqueue and Dequeue operation like a Queue.
enum StackError: Error {
//Pushing into a full stack
case stackOverflow
//Popping from or peeking into an empty stack
case stackUnderflow
}
class Stack<T> {
private let maxSize: Int
private(set) var array = Array<T>()
//Topmost element in the stack
private var top: T?
//Track the size of the stack at every push, pop
//This means the stack size operation can be constant time
private var size = 0
init(maxSize: Int) {
self.maxSize = maxSize
}
func push(data: T) throws {
if size == maxSize {
throw StackError.stackOverflow
}
array.append(data)
top = data
size += 1
}
func pop() throws -> T {
if size == 0 {
throw StackError.stackUnderflow
}
//Remove the top element from the stack and return it's data
let topElement = array.removeLast()
top = array.last
size -= 1
return topElement
}
func peek() throws -> T {
if size == 0 {
throw StackError.stackUnderflow
}
guard let topElement = top else {
throw StackError.stackUnderflow
}
//Just return the data of the top element, do not remove it
return topElement
}
var isEmpty: Bool {
size == 0
}
var isFull: Bool {
size == maxSize
}
}
class QueueUsingTwoStack<T> {
let forwardStack: Stack<T>
let reverseStack: Stack<T>
init(size: Int) {
self.forwardStack = Stack<T>(maxSize: size)
self.reverseStack = Stack<T>(maxSize: size)
}
var isFull: Bool {
forwardStack.isFull || reverseStack.isFull
}
var isEmpty: Bool {
forwardStack.isEmpty && reverseStack.isEmpty
}
func enqueue(data: T) throws {
if isFull {
throw StackError.stackOverflow
}
if forwardStack.isEmpty {
//Push all elements from the reverse stack to the forward stack, enqueue always happens on the forward stack
while !reverseStack.isEmpty {
let popedValue = try reverseStack.pop()
try forwardStack.push(data: popedValue)
}
}
//Finally do the enqueue - A push on the forward stack
try forwardStack.push(data: data)
}
func dequeue() throws -> T {
if isEmpty {
throw StackError.stackUnderflow
}
if reverseStack.isEmpty {
//Push all elements from the forward stack to the reverse stack, dequeue alwyas happens on the reverse stack
while !forwardStack.isEmpty {
let poppedValue = try forwardStack.pop()
try reverseStack.push(data: poppedValue)
}
}
//Finally do the dequeue - A pop on the reverse stack
return try reverseStack.pop()
}
}
let queue = QueueUsingTwoStack<Int>(size: 4)
try? queue.enqueue(data: 1)
try? queue.enqueue(data: 2)
try? queue.enqueue(data: 3)
try? queue.enqueue(data: 4)
queue.isFull
try? queue.dequeue()
Performance
All enqueues and then all dequeues are O(1) – If only one of these operations are performed
Notice that each element is pushed no more than twice
- Once onto the forward stack to enqueue it and once onto the reverse stack just before dequeueing
Each element is popped no more than twice
- Once to move to the reverse from the forward stack just before dequeuing and then to actually dequeue it
Time complexity is O(M) where M is the number of operations we perform on the queue.
https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8463700#overview
Shawn 
You must be logged in to post a comment.