StacksQueues/Python

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

See StacksQueues/Python/ArrayStack

Stack tricks

Reversing data using a stack

Exception handling/corner case handling:

• If a file has, or does not have, a newline at the end of the file - then if you print it in reverse order and put it in a new file, last->first line will be messed up

Stack - can provide solution for reversing contents of Python list. Recursive solutions also possible. More challenging task: reverse the order in which elements are stored within a stack (Use 3 stacks.

Stack matching applications

Syntax and matching applications: if a symbol is in an opening structure {[(, push the stack. if a symbol is in a closing structure, )]}, pop the stack. if not matching, fail.

At end, return isEmpty()

Left-to-right scan of original sequence using a stack S to facilitate matching of grouping symbols.

This was also the subject of "Igor" in the Google Code Jam problem "Ignore My Comments," who wanted to put C-style /* */ comments in every file, and wanted help building his own file parser to remove them.

https://charlesreid1.com:3000/charlesreid1/code-jam/src/master/ignore-my-comments