Chapter 3.1

Stacks Data Structure

Table of Content

1. Introduction to Stacks

A stack is one of the most fundamental and widely used data structures in computer science. It follows the principle of Last In, First Out (LIFO), which means that the last element added to the stack is the first one to be removed. Stacks are used in various algorithms and applications, especially in scenarios where temporary storage is needed and retrieval should happen in the reverse order of insertion.

A Stack is indeed a non-primitive linear data structure, meaning it isn't directly provided by the language like primitive types (e.g., integers, floats) but is built using them. Its linear nature means that elements are arranged sequentially, one after another.

In a stack, both insertion and deletion of elements happen at a single point called the top. This characteristic is what defines its LIFO (Last In, First Out) behavior—whatever is added last will be the first to be removed.

Key Characteristics of a Stack:

Linear Order: The elements in a stack are stored in a linear fashion, which means they are placed one after another in a sequence.
Single Point of Access: All operations (push, pop, peek) happen at the top of the stack. This means the most recently added element is the first one to be removed.
Dynamic Size: In most implementations, the size of a stack can grow or shrink as needed (unless we are working with a fixed-size stack).
LIFO (Last In, First Out): The last element added to the stack is the first one to be removed. This is in contrast to FIFO (First In, First Out) structures like queues.

2. Historical Background

The concept of the stack was first formally described by German mathematician and computer scientist Friedrich L. Bauer in 1957. He used the stack in connection with recursive function evaluation, where function calls are placed onto a stack and retrieved in a LIFO manner. In 1958, Klaus Samelson and Friedrich Bauer together introduced the stack to be used for the translation of mathematical formulas into machine code in compilers. The concept became widely recognized after the development of the Algol programming language, which utilized stacks for managing function calls and recursion.

3. How Stacks Work

Stack Operations: A stack is like a stack of books: you can only remove the top book from the pile. When adding a new book, you place it on top. Similarly, in a stack:

Push: Add an element to the top of the stack.
Pop: Remove and return the element from the top.
Peek/Top: View the top element without removing it.
isEmpty: Check whether the stack is empty.
Size: Determine how many elements are in the stack.
Traverse: The Traverse operation in a stack involves visiting or accessing each element sequentially, starting from the top of the stack and moving toward the bottom. This is a common operation used to inspect or display the contents of the stack without altering the stack structure.

4. Problems Best Solved Using Stacks

By allowing operations only from one end, stacks provide a controlled, predictable mechanism to manage data in scenarios where the order of operations matters. Stacks are best used in situations where the order of operations is important, and you need to process the most recently added items first. Some common problems that are efficiently solved using stacks include:

Expression Evaluation and Parsing: Stacks are used to evaluate or transform expressions from infix to postfix and vice versa. Converting infix expressions (like a + b) to postfix (Reverse Polish Notation) and evaluating them. In compilers, stacks are used to convert expressions from infix to postfix notation or evaluate them directly.
Balancing Parentheses: Verifying if parentheses (or other symbols like {}, []) are balanced in a given expression. Stacks help in checking if brackets, parentheses, or curly braces are correctly balanced in expressions.
Backtracking Algorithms: Such as navigating mazes, solving puzzles like the N-Queens problem, and traversing trees or graphs (depth-first search). Algorithms like depth-first search (DFS) use stacks to explore possibilities by backtracking.
Web Browser History: When navigating through web pages, a stack stores the URLs, enabling the "back" and "forward" functionality.
Undo Mechanism or Operations: In text editors, stacks are used to implement the undo and redo functionality. Applications like word processors use stacks to store user actions, allowing them to undo or redo operations. Applications like word processors use stacks to store user actions, enabling undo and redo functionalities.
Function Call Management: Stacks manage function calls and recursion in programming languages. When a function is called, its details are pushed onto a call stack, and once the function completes, they are popped off.

5. Stack Operations (Pseudo Code)

5.1 Push Operation

procedure push(stack, element)
    if stack is full:
        print "Stack Overflow"
    else:
        increment top
        stack[top] = element
end procedure

5.2 Pop Operation

procedure pop(stack)
    if stack is empty:
        print "Stack Underflow"
    else:
        element = stack[top]
        decrement top
        return element
end procedure

5.3 Peek Operation

procedure peek(stack)
    if stack is empty:
        print "Stack is empty"
    else:
        return stack[top]
end procedure

5.4 isEmpty Operation

procedure isEmpty(stack)
    return top == -1
end procedure

5.5 Size Operation

procedure size(stack)
    return top + 1
end procedure

5.6 Traverse Operation

The Traverse operation in a stack involves visiting or accessing each element sequentially, starting from the top of the stack and moving toward the bottom. This is a common operation used to inspect or display the contents of the stack without altering the stack structure. Since a stack follows the Last In, First Out (LIFO) principle, traversing it involves accessing elements in reverse order from how they were added. You start at the top (where the most recent element was added) and move downwards.

Steps for Traversing a Stack:

Start from the top of the stack.
Access (or display) the top element.
Move to the next element (the one directly below the current top).
Continue until the bottom of the stack is reached (i.e., the stack is empty).

Pseudo Code for Traverse Operation

Procedure Traverse(stack)
    If stack is empty:
        Print "Stack is empty"
    Else:
        Set temp = top
        While temp is not None:
            Print stack[temp]  # Display the element
            temp = temp - 1    # Move to the next element (downwards)

6. Python Implementation of Stack

In Python, a stack can be implemented easily using a list or a custom class. Below is a class-based implementation of a stack, encapsulating the various stack operations:

class Stack:
    def __init__(self):
        # Initialize an empty stack
        self.stack = [] # Initialize an empty list to represent the stack
    
    # Push an element onto the stack
    # Add an element to the top of the stack
    def push(self, element):
        self.stack.append(element) # Add element to the top
    
    # Pop an element from the stack
    # Remove and return the top element of the stack if it's not empty
    # Use the list pop method to remove and return the last element
    def pop(self):
        if not self.is_empty():
            return self.stack.pop() # Remove and return top element
        else:
            print ("Stack Underflow")
            return None  # Return None if the stack is empty
    
    # Peek the top element of the stack
    # View the top element without removing it
    # Return the last element in the list
    # Return None if the stack is empty
    def peek(self):
        if not self.is_empty():
            # Return the last element in the list
            return self.stack[-1] # Return top element without removing
        else:
            print("Stack is empty")
            return None # Return None if the stack is empty
       
    # Check if the stack is empty
    # Return True if the stack is empty, else return False

    def is_empty(self):
        return len(self.stack) == 0  # Check if stack is empty
        #return(self.stack == [])    # Using len() is clearer and more efficient 
        
    # Return the size of the stack
    def size(self):
        return len(self.stack)
    
    def traverse(self):
        if self.is_empty():
            print("Stack is empty")
        else:
            print("Stack elements from top to bottom:")
            for i in range(len(self.stack)-1, -1, -1):
                print(self.stack[i])
                
    def __str__(self):
        # Custom string representation of the stack
        return str(self.stack)

# Example Usage
s = Stack()
s.push(10)
s.push(20)
s.push(30)
s.traverse()  # Output: 30, 20, 10 (from top to bottom)

print("Top element:", s.peek())   # Output: Top element: 30
print("Popped element:", s.pop()) # Output: Popped element: 30
print("Stack size:", s.size())    # Output: Stack size: 2

# Example usage
s = Stack()
s.push(10)
s.push(20)
s.push(30)
s.push(40)
print(s.pop())  # Output: 40 (topmost element)
print(s.pop())  # Output: 30 (next topmost element)
print(s)  # Output: [10, 20] (remaining elements in the stack)

Explanation:traverse() Method: The traverse() function starts at the top of the stack and iterates downwards, printing each element. In the Python code, it uses a for-loop that iterates from the top of the list (len(self.stack)-1, the last index) to the bottom (0), thus mimicking the LIFO behavior of a stack. If the stack is empty, it simply prints a message stating that the stack is empty. Key Points: (i) Traverse does not modify the stack; it just reads the elements. (ii) It can be useful for displaying the current state of the stack in scenarios like debugging or logging. The use cases for Stack Traversal include: Debugging: To print the stack's content for inspection at any point during a program's execution. Backtracking: When using a stack for backtracking (such as in depth-first search), traversing allows you to see all paths stored in the stack. Undo Operations: In applications that support undo functionality, traversing a stack can help show the sequence of operations that can be undone. Thus, the traverse operation in a stack provides a way to access or display elements in reverse order of insertion, helping visualize or process the stack’s content without modifying it.

Stack Data Structure: The stack is represented as a list (self.stack), and it follows the LIFO (Last In, First Out) principle, meaning the last element added to the stack is the first one removed. Operations:

push(v) method : Adds an element v to the top of the stack using the append() method.
pop method: Removes and returns the top element from the stack using the pop() method. If the stack is empty, it returns None.
peek method: A peek method, which allows us to view the top element without removing it. This method is particularly useful when you want to check what’s on the top of the stack without altering the structure.
isempty(): Returns True if the stack is empty (i.e., has no elements), otherwise returns False.

Method Names & Code Clarity:: Python convention for method names is snake_case (e.g., push instead of Push). This aligns with PEP 8, Python’s style guide, and makes the code easier to read. Add comments and enhance the overall clarity of the code.

7. Analysis of Stack Operations

7.1 Time Complexity:

Push: O(1) — Adding an element to the stack is done in constant time. The append() method adds an element to the end of the list, which takes constant time.
Pop: O(1) — Removing the top element also takes constant time. The pop() method removes and returns the last element of the list, also in constant time.
Peek: O(1) — Viewing the top element requires no traversal. Accessing the last element is constant time, as it only involves indexing the list.
isEmpty: O(1) — Simply checking if the stack is empty is a constant-time operation. Simply checks the length of the list, which is a constant time operation.
Size: O(1) — Retrieving the size of the stack is done in constant time.
Traverse: The time complexity for traversing a stack is O(n), where n is the number of elements in the stack. This is because we have to visit every element once.

7.2 Space Complexity:

The space complexity depends on the number of elements stored in the stack. For n elements, the space complexity is O(n).

8. Conclusion

Stacks are one of the most versatile and widely used data structures in computer science. Their LIFO nature makes them suitable for problems where you need to reverse the order of operations. By understanding the basic operations of a stack and implementing them in Python, we can solve a variety of problems efficiently. Stacks also form the foundation of many algorithms used in software development, data parsing, and system design.

PreviousWeek 3 NextWeek 4

Last updated 6 months ago