Stack

Overview

Think of a stack as a collection of books stacked on top of each other. You have a pile of books on your desk, and you can only interact with the book on the top. This pile follows the Last In, First Out (LIFO) principle, similar to how a stack data structure operates.

Now that we understand the LIFO principle and we can imagine how a stack data structure can look like in real life ("stacked" books), let's see what can we do with it.

Push: Imagine you want to add a new book to the stack. You take a new book and place it on top of the existing pile. The book you just added becomes the topmost book, and any books already in the pile are now below it.

Pop: When you want to remove a book from the stack, you can only take the book from the top of the pile. You remove the topmost book, and now the book below it becomes the new top book.

Peek (or Top): To see which book is at the top of the stack without removing it, you simply look at the topmost book in the pile. Think of it like looking at the topmost book and reading its cover.

So what's the purpose of a stack?
Let's explore some practical applications of the stack using this book analogy:

Undo History: Think of each book representing a state in a document or drawing. As users make changes, new states (books) are added to the stack. When they want to undo an action, the topmost state (book) is removed, effectively "going back" to the previous state.

Function Calls: Picture a stack of books representing functions in a program. When a function is called, a new book is added to the stack. When the function finishes executing, its corresponding book is removed from the stack, and the program returns to the previous function (book) in the call chain.

Expression Evaluation: Suppose you have a mathematical expression with parentheses. You can use a stack to keep track of opening and closing parentheses. When encountering an opening parenthesis, you "push" it onto the stack, and when you encounter a closing parenthesis, you "pop" the last opening parenthesis from the stack.

Backtracking: Imagine you're exploring a maze, and you want to keep track of your path. Each time you move to a new location, you push your current position onto the stack. If you reach a dead-end, you can "pop" the last position from the stack to backtrack and try a different path.
A famous example of this is the Depth First Search traversal algorithm. If you haven't heard it or simply don't know much about it, don't worry - we will learn it in the Graphs section later!

As a conclusion - by understanding the concept of a stack through different analogies, you can grasp its usefulness and versatility in solving various problems in computer science, data processing, and algorithmic design. Whether you think of it as a stack of plates or a pile of books, the fundamental principles remain the same and it's a generally simple yet incredibly useful concept.

Code

*For Java and C++, we have used the integrate 'stack' in the languages for illustration purposes but if needed, by association with the other code examples, stack can be manually implemented in Java and C++ too.

class Stack:
    def __init__(self):
        self.stack_items = []
 
    def push(self, item):
        self.stack_items.append(item)
 
    def pop(self):
        if not self.is_stack_empty():
            return self.stack_items.pop()
 
    def peek(self):
        if not self.is_stack_empty():
            return self.stack_items[-1]
 
    def is_stack_empty(self):
        return len(self.stack_items) == 0
 
    def get_stack_size(self):
        return len(self.stack_items)
 
# Example usage:
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())  # Output: 3
print(stack.peek())  # Output: 2
print(stack.get_stack_size())  # Output: 2

class Stack {
  constructor() {
    this.stackItems = [];
  }
 
  push(item) {
    this.stackItems.push(item);
  }
 
  pop() {
    if (!this.isStackEmpty()) {
      return this.stackItems.pop();
    }
  }
 
  peek() {
    if (!this.isStackEmpty()) {
      return this.stackItems[this.stackItems.length - 1];
    }
  }
 
  isStackEmpty() {
    return this.stackItems.length === 0;
  }
 
  getStackSize() {
    return this.stackItems.length;
  }
}
 
// Example usage:
const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.pop());  // Output: 3
console.log(stack.peek()); // Output: 2
console.log(stack.getStackSize()); // Output: 2

import java.util.Stack;
 
public class CustomStack {
    public static void main(String[] args) {
        Stack<Integer> customStack = new Stack<>();
 
        customStack.push(1);
        customStack.push(2);
        customStack.push(3);
 
        System.out.println(customStack.pop()); // Output: 3
        System.out.println(customStack.peek()); // Output: 2
        System.out.println(customStack.size()); // Output: 2
    }
}

#include <stdio.h>
#define MAX_SIZE 100
 
typedef struct {
    int stack_items[MAX_SIZE];
    int top;
} CustomStack;
 
void init(CustomStack* customStack) {
    customStack->top = -1;
}
 
void push(CustomStack* customStack, int item) {
    if (customStack->top < MAX_SIZE - 1) {
        customStack->stack_items[++customStack->top] = item;
    }
}
 
int pop(CustomStack* customStack) {
    if (customStack->top >= 0) {
        return customStack->stack_items[customStack->top--];
    }
    return -1; // Or some error value
}
 
int peek(CustomStack* customStack) {
    if (customStack->top >= 0) {
        return customStack->stack_items[customStack->top];
    }
    return -1; // Or some error value
}
 
int isStackEmpty(CustomStack* customStack) {
    return customStack->top == -1;
}
 
int getStackSize(CustomStack* customStack) {
    return customStack->top + 1;
}
 
// Example usage:
int main() {
    CustomStack customStack;
    init(&customStack);
 
    push(&customStack, 1);
    push(&customStack, 2);
    push(&customStack, 3);
 
    printf("%d\n", pop(&customStack));  // Output: 3
    printf("%d\n", peek(&customStack)); // Output: 2
    printf("%d\n", getStackSize(&customStack)); // Output: 2
 
    return 0;
}

<?php
class CustomStack {
    private $stack_items = [];
 
    public function push($item) {
        array_push($this->stack_items, $item);
    }
 
    public function pop() {
        if (!$this->isStackEmpty()) {
            return array_pop($this->stack_items);
        }
    }
 
    public function peek() {
        if (!$this->isStackEmpty()) {
            return end($this->stack_items);
        }
    }
 
    public function isStackEmpty() {
        return empty($this->stack_items);
    }
 
    public function getStackSize() {
        return count($this->stack_items);
    }
}
 
// Example usage:
$customStack = new CustomStack();
$customStack->push(1);
$customStack->push(2);
$customStack->push(3);
 
echo $customStack->pop() . "\n";  // Output: 3
echo $customStack->peek() . "\n"; // Output: 2
echo $customStack->getStackSize() . "\n"; // Output: 2
?>

We always try to improve this course so if you spot errors, inconsistencies or other issues, contact us.

Intro Queue