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 be the number of elements in the stack. * Space Usage: The space complexity is . * Time Complexity: Every operation (push, pop, top, len, is_empty) runs in constant time, denoted as .
Array-Based Stack in Python: * A simple method for implementing the Stack ADT is using a Python list. * The list's
appendmethod serves aspush, and the list'spopmethod serves aspop(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]; outputs25.print(S.pop()): contents[5]; outputs36.print(S.is_empty()): contents[5]; outputsFalse7.print(S.pop()): contents[]; outputs58.print(S.is_empty()): contents[]; outputsTrue9.S.push(7): contents[7]10.S.push(9): contents[7, 9]11.print(S.top()): contents[7, 9]; outputs912.S.push(4): contents[7, 9, 4]13.print(len(S)): contents[7, 9, 4]; outputs314.print(S.pop()): contents[7, 9]; outputs415.S.push(6): contents[7, 9, 6]16.S.push(8): contents[7, 9, 6, 8]17.print(S.pop()): contents[7, 9, 6]; outputs8
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 stackS. 4. If a closing symbol (),}, or]) is encountered: * Check if the stack is empty. If it is, returnfalse(nothing to match with). * Otherwise, pop a symbol fromS. * Compare the popped symbol and the current closing symbol. If they are not of the same type, returnfalse. 5. After the entire sequence is processed: * If the stack is empty, returntrue(all symbols matched). * If the stack is not empty, returnfalse(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"}