Intro to Stacks and the Stack ADT

Abstract Data Types (ADTs) and Stack Foundations

  • Definition of an Abstract Data Type (ADT): An ADT represents an abstraction of a data structure. It specifies the following components without detailing the underlying implementation:     * Data Stored: The nature of the information contained within the structure.     * Operations: The specific actions that can be performed on the data.     * Error Conditions: The specific errors associated with operations (e.g., trying to remove an item from an empty container).

  • Conceptual Overview of Stacks:     * Stacks are a type of container with restricted access.     * They store linear collections of items.     * They are ubiquitous in computer science and used to solve a variety of algorithmic problems.     * Everyday Item Analogy: A stack of bowls. When you remove a bowl from the top, the others remain in place but the bowl previously underneath now becomes the new top.

The Stack ADT Specification

  • Storage and Access: The Stack ADT is designed to store many different types of objects. Access is restricted to one end, known as the "top."

  • LIFO Principle: Stacks follow the Last-In First-Out scheme. This means the last item inserted into the stack is the very first one to be removed.

  • Main Operations:     * push(object): Inserts an element onto the top of the stack.     * object pop(): Removes and returns the element that was most recently inserted.

  • Auxiliary Operations:     * object top(): Returns the element at the top of the stack without removing it (peeking).     * integer len(): Returns the total number of elements currently stored in the stack.     * boolean is_empty(): Returns a boolean value indicating whether the stack contains no elements.

  • Visualizing Operations:     * Pushing a value (e.g., 19) places it at the base.     * Pushing another value (e.g., 5) places it above the 19.     * The resulting stack for these two operations is [19, 5] (with 5 as the top).     * Popping the top value removes 5 and returns it to the user.

Performance and Implementation Strategy

  • Complexity Analysis:     * Let nn be the number of elements in the stack.     * Space Usage: The space complexity is O(n)O(n).     * Time Complexity: Every operation (push, pop, top, len, is_empty) runs in constant time, denoted as O(1)O(1).

  • Array-Based Stack in Python:     * A simple method for implementing the Stack ADT is using a Python list.     * The list's append method serves as push, and the list's pop method serves as pop (removing the last item).     * Mapping: The top of the stack is represented by the end of the Python list.     * Abstraction Note: Goodrich, Tamassia, and Goldwasser note that while a list can be used directly, performing stack operations via a custom class is necessary to preserve the ADT's integrity. Directly using a list allows insertions/removals at any index, which violates the restricted access property of a stack ADT.

Python Implementation: The ArrayStack Class

class ArrayStack:
    """LIFO Stack implementation using a Python list as underlying storage."""
    def __init__(self):
        """Create an empty stack."""
        self._data = [] # nonpublic list instance

    def len(self):
        """Return the number of elements in the stack."""
        return len(self._data)

    def is_empty(self):
        """Return True if the stack is empty."""
        return len(self._data) == 0

    def push(self, e):
        """Add element e to the top of the stack."""
        self._data.append(e) # new item stored at end of list

    def top(self):
        """Return (but do not remove) the element at the top of the stack.
        Raise Empty exception if the stack is empty.
        """
        if self.is_empty():
            raise Empty('Stack is empty')
        return self._data[-1] # the last item in the list

    def pop(self):
        """Remove and return the element from the top of the stack (i.e., LIFO).
        Raise Empty exception if the stack is empty.
        """
        if self.is_empty():
            raise Empty('Stack is empty')
        return self._data.pop() # remove last item from list

Trace of Stack Operations

  • Below is a step-by-step trace of operations on a newly created stack S:     1. S = ArrayStack(): contents []     2. S.push(5): contents [5]     3. S.push(3): contents [5, 3]     4. print(len(S)): contents [5, 3]; outputs 2     5. print(S.pop()): contents [5]; outputs 3     6. print(S.is_empty()): contents [5]; outputs False     7. print(S.pop()): contents []; outputs 5     8. print(S.is_empty()): contents []; outputs True     9. S.push(7): contents [7]     10. S.push(9): contents [7, 9]     11. print(S.top()): contents [7, 9]; outputs 9     12. S.push(4): contents [7, 9, 4]     13. print(len(S)): contents [7, 9, 4]; outputs 3     14. print(S.pop()): contents [7, 9]; outputs 4     15. S.push(6): contents [7, 9, 6]     16. S.push(8): contents [7, 9, 6, 8]     17. print(S.pop()): contents [7, 9, 6]; outputs 8

Stack Applications

  • Direct Applications:     * Web Browsers: Managing the history of visited pages (Back button functionality).     * Text Editors: Maintaining an undo sequence of user actions.     * Programming Languages: Managing the chain of method calls in languages that support recursion (the Call Stack).

  • Indirect Applications:     * Serving as an auxiliary data structure for broader algorithms.     * Acting as a core component for more complex data structures.

The Parentheses Matching Algorithm

  • The Problem: In mathematical expressions, delimiters like (), {}, and [] must be properly paired.     * Examples of Matching: ( )(( )){([( )])}, ((( )(( )){([( )])}     * Examples of Mismatching: )(( )){([( )])} (starts with closing), ({[ ])} (incorrect order), ( (unclosed opening).

  • Algorithm Logic (ParenMatch(X,n)):     1. Process the input sequence from left to right.     2. Create an empty stack S.     3. If an opening symbol ((, {, or [) is encountered, push it onto stack S.     4. If a closing symbol (), }, or ]) is encountered:         * Check if the stack is empty. If it is, return false (nothing to match with).         * Otherwise, pop a symbol from S.         * Compare the popped symbol and the current closing symbol. If they are not of the same type, return false.     5. After the entire sequence is processed:         * If the stack is empty, return true (all symbols matched).         * If the stack is not empty, return false (some symbols were never matched).

  • Python Implementation for Parentheses Matching:

def is_matched(expr):
    """Return True if all delimiters are properly matched; False otherwise."""
    lefty = '({['    # opening delimiters
    righty = ')}]'   # respective closing delims
    S = ArrayStack()
    for c in expr:
        if c in lefty:
            S.push(c) # push left delimiter on stack
        elif c in righty:
            if S.is_empty():
                return False # nothing to match with
            if righty.index(c) != lefty.index(S.pop()):
                return False # mismatched
    return S.is_empty() # were all symbols matched?

", "title": "Fundamentals and Applications of Stack Data Structures"}