1/16
A set of vocabulary terms covering the definition, operations, implementation, and applications of the Stack Abstract Data Type based on the provided lecture transcript.
Abstract Data Type (ADT)
An abstraction of a data structure that specifies the data stored, operations on the data, and error conditions associated with those operations.
Stacks
A type of container with restricted access that stores linear collections and follows a last-in first-out (LIFO) scheme.
Last-In First-Out (LIFO)
A scheme for insertions and deletions where the last item inserted into the collection is the first one to be removed.
push(object)
A main stack operation that inserts an element onto the top of the stack.
pop()
A main stack operation that removes and returns the last inserted element from the stack.
top()
An auxiliary stack operation that returns the last inserted element without removing it from the stack.
len()
An auxiliary stack operation that returns the integer number of elements stored in the stack.
is_empty()
An auxiliary stack operation that returns a boolean indicating whether no elements are stored in the stack.
Direct applications of Stacks
Page-visited history in a Web browser, Undo sequences in a text editor, and the chain of method calls in languages supporting recursion.
Indirect applications of Stacks
Use as an auxiliary data structure for algorithms or as a component of other data structures.
Array-based Stack implementation (Python)
A stack implementation using the Python list class, utilizing the append method for push operations and the pop method for removing the last element.
Space Complexity of Array-based Stack
The space used by the stack is O(n), where n is the number of elements in the stack.
Performance of Stack Operations
Each main and auxiliary stack operation runs in time O(1).
ArrayStack class
A LIFO Stack implementation provided in the lecture notes that uses a Python list as underlying storage and raises an Empty exception if methods like top or pop are called on an empty stack.
ParenMatch(X,n) Algorithm
A stack-based algorithm that processes a string to ensure every opening symbol (, {, [ is matched by a corresponding closing symbol ), }, ] in the correct order.
lefty
In the Python is_matched implementation, the string variable representing the set of opening delimiters: '({['.
righty
In the Python is_matched implementation, the string variable representing the set of closing delimiters: ')}]'.