StacksQueues/Python
From charlesreid1
Notes
Goodrich et al Data Structures in Python Chapter 6
Stacks
Stack abstract data type:
- Stacks are the simplest data types, yet among the most important.
- Used as a tool in many more sophisticated data structures and algorithms.
Definition:
- A stack is an ADT such that an instance S supports the following two methods:
- S.push(e): add element e to the top of the stack S
- S.pop(): remove and return the top element from the stack S. An error occurs if the stack is empty.
Additionally, we define accessor methods:
- S.top: return a reference to the top element of stack S, without removing it. An error occurs if the stack is empty.
- S.is_empty(): return True if stack S does not contain any elements
- len(S): return the number of elements in stack S, Pyton Python we implement this with
__len__method
Stack ADT implementation approaches
Can use one of several underlying data types to store the stack, starting with an array.
The array-based structure can either utilize a ctype array (as with the Arrays/Python/DynamicArray class), or can just utilize a list, which the DynamicArray class was meant to emulate.
Here is the code for an array-based stack: https://charlesreid1.com:3000/cs/python/src/master/stacks-queues-deques/stacks/ArrayStack.py