Stacks

Introduction

In the world of computer science, data structures are fundamental building blocks that help organize and manage data efficiently. One such essential data structure is the stack. A stack is a linear data structure that follows the Last In First Out (LIFO) principle, meaning that the last element added to the stack will be the first one to be removed. This unique property makes stacks particularly useful in various applications.

Concept

A stack can be visualized as a vertical pile of objects where you can only access the top object. The two primary operations associated with a stack are:

1. Push: Adds an element to the top of the stack.
2. Pop: Removes the element from the top of the stack.

Additionally, there is a third operation that is often useful:

3. Peek/Top: Returns the element at the top of the stack without removing it.

Stacks can be implemented using arrays or linked lists. Here, we will explore both methods to give you a comprehensive understanding.

Examples

Implementing a Stack Using an Array

Let's start by implementing a simple stack using an array in Python.

1class Stack:
2  def __init__(self):
3      self.items = []
4 
5  def is_empty(self):
6      return len(self.items) == 0
7 
8  def push(self, item):
9      self.items.append(item)
10 
11  def pop(self):
12      if not self.is_empty():
13          return self.items.pop()
14      raise IndexError("pop from empty stack")
15 
16  def peek(self):
17      if not self.is_empty():
18          return self.items[-1]
19      raise IndexError("peek from empty stack")
20 
21  def size(self):
22      return len(self.items)
23 
24# Example usage
25stack = Stack()
26stack.push(1)
27stack.push(2)
28stack.push(3)
29print(stack.peek())  # Output: 3
30print(stack.pop())   # Output: 3
31print(stack.size())  # Output: 2

Implementing a Stack Using a Linked List

Now, let's implement the same stack using a linked list.

1class Node:
2  def __init__(self, value):
3      self.value = value
4      self.next = None
5 
6class LinkedListStack:
7  def __init__(self):
8      self.head = None
9      self.size = 0
10 
11  def is_empty(self):
12      return self.head is None
13 
14  def push(self, item):
15      new_node = Node(item)
16      new_node.next = self.head
17      self.head = new_node
18      self.size += 1
19 
20  def pop(self):
21      if not self.is_empty():
22          popped_value = self.head.value
23          self.head = self.head.next
24          self.size -= 1
25          return popped_value
26      raise IndexError("pop from empty stack")
27 
28  def peek(self):
29      if not self.is_empty():
30          return self.head.value
31      raise IndexError("peek from empty stack")
32 
33  def size(self):
34      return self.size
35 
36# Example usage
37stack = LinkedListStack()
38stack.push(1)
39stack.push(2)
40stack.push(3)
41print(stack.peek())  # Output: 3
42print(stack.pop())   # Output: 3
43print(stack.size())  # Output: 2

Applications of Stacks

Stacks have numerous applications in computer science and software engineering. Here are a few examples:

1. Function Call Management: When a function is called, its execution context (local variables, return address, etc.) is pushed onto the call stack. When the function returns, its context is popped from the stack.

2. Expression Evaluation: Stacks are used to evaluate expressions in both infix and postfix notations.

3. Backtracking Algorithms: Stacks are often used in algorithms that require backtracking, such as solving mazes or puzzles like Sudoku.

4. Undo Mechanism: Many applications use a stack to implement an undo feature, where each action is pushed onto the stack, and the last action can be undone by popping it from the stack.

What's Next?

Now that you have a solid understanding of stacks, the next topic in our curriculum will be Queues. Queues are another fundamental data structure that follows the First In First Out (FIFO) principle and have their own set of applications and use cases. Stay tuned!