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 (2 temporary) to reverse order.

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

Array queue teachable aspects

There are several aspects of the array queue object that are teachable.

First is that we have to be careful with our index math. Computing the location of the next opening is:

avail = (self._front + self._)%(len(self._data))

Using the size prior to the addition of the new element.

Resizing queue:

• The queue size may be equal to the underlying list size. If this is the case, we need to expand the list. We make it double in size.
• The process of resizing the queue is also an opportunity to put everything in order starting at the front of the queue.

Shrinking queue:

• We want to shrink the queue by half when the number of elements is less than a quarter of the total capacity.

Deque

Link to code on git.charlesreid1.com: https://charlesreid1.com:3000/cs/python/src/master/stacks-queues-deques/deque/ArrayDeque.py

Details of deque implementation: StacksQueues/Python/ArrayDeque

Double ended queue abstract data type implements the methods.

A deque object D implements the following core methods:

• D.add_first : add the item to the front of the deque
• D.add_last : add the item to the end of the deque
• D.delete_first : remove and return the ifrst item from the deque
• D.delete_last : remove and return the last item from the deque

Additional convenience methods:

• D.first : peek at first item
• D.last : peek at last item
• D.is_empty : returns True if deque has no elements
• D.__len__ : length
• D.__str__ : turn into string)

Private utility methods:

• D._resize : resize the deque (dynamic growth/shrinkage)