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

Being able to focus on a single comment would allow focusing one character at a time.

$ cat MatchDelimiters.py
"""
Matching Parentheses

Consider arithmetic expressions that may contain various pairs of grouping symbols, such as
({[
)}]

Determine if these expressions are correct.
"""

from ArrayStack import ArrayStack

def is_matched(expr):
    left = '({['
    right = ')}]'
    stack = ArrayStack()
    for c in expr:
        if c in left:
            stack.push(c)
        if c in right:
            if stack.is_empty():
                return False
            right_index = right.index(c)
            left_index = left.index(stack.pop())
            if(right_index is not left_index):
                return False
    return stack.is_empty()

if __name__=="__main__":
    assert(  is_matched("()(()){([()])}")     )
    assert(  is_matched("((()(()){([()])}))") )
    assert(  not is_matched(")(()){([()])}")  )
    assert(  not is_matched("({{[])}")        )
    assert(  not is_matched("(")              )
    print("Tests all passed.")

Markup language

To check html:

Look for opening <, then closing >

Find token between

push

Look for </, then >

Find token between

pop, if neq, false

Queues

Many examples. stores, theaters, reseeervations, wait lists, ustomer serivce, computing devices

communication, networking, messaging, printers, server requests

Queue abstract data type:

The queue ADT supports the following two fundamenal methos for a queue Q:

• Q.enqueue(e): add element e to the back of the queue Q
• Q.dequeue(): remove and return teh first element from queue Q. An error occurs if the queue is empty.

Further supporting methods:

• Q.first() returns reference to element at front, but does not remove it
• Q.is_empty(): returns True if queue Q does not contain any elements
• len(Q): implemented via __len__, number of elements in queue

Here is the implementation with a list: StacksQueues/Python/ArrayQueue class