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://git.charlesreid1.com/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://git.charlesreid1.com/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 double-ended queue

Link to code on git.charlesreid1.com: https://git.charlesreid1.com/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)

Python collections.deque class

Better to just use the collections.deque:

len(D) : number of elements
D.appendleft() : add to beginning
D.append() : add to end
D.popleft() : remove from beginning
D>pop() : remove from end
D[0] : first element
D[-1] : last element
D[j] : access arbitrary entry by index
D[j] = val : modify arbitrary entry by index
D.clear() : clear contents
D.remove(e) : remove first matching element
D.count(e) : count number of matches for e

currently, collections deque uses hybrid approach. Circular arrays, but organized into blocks that are themselves organized into doubly-linked list.

O(1) time operations at either end and O(n) worst case time when using middle of deque.

Questions

Questions from Goodrich Python Chapter 6 Stacks and Queues

Recursive method to remove all items from stack

Question C.6-11: The recursive method simply calls pop then calls itself, for as long as the stack remains non-empty.

    def clear(self):
        """
        Recursive clear method
        """
        if(self.is_empty()):
            return
        else:
            self.pop()
            self.clear()

Monty hall problem with stacks

Question C-6.15: translates the Monty Hall problem to be based on Stacks.

Select 3 distint integers, place them in a stack S in random order.

Short, straight-line pseudocode (no loops, no recursion) that uses ONE comparison and ONE variable x,

that will result in x storing the larger of the 3 integers with probabilty 2/3 (that is, 2/3 probabilty of being the largest integer)

Answer: This is the Monty Hall problem, applied with stacks.

The premise of the Monty Hall problem is that you have 3 doors, behind each of which there lies a prize. You are asked to select a door, and you do. The host then says, let's show him one of the doors he did not choose, and there is the door, it's empty. What should you do? You should always change your decision. Each door has probability 1/3 to begin with. When you select your door, it has probability 1/3. But when you are shown one of the two remaining doors, the 1/3 probability it was that door has to go somewhere, so it actually goes into the other door. Now, the other door has a 2/3 chance of being correct.

Now, in our case, we have a stack.

If you pop the first item, then that's you choosing a door.

Then you peek at the next item - and there are two possibilities.

If we're shown a number that's SMALLER, we were just shown a losing guess (that is, the middle element of this stack is not the largest element). That means the probability it was one of the first two numbers, which was 2/3 to begin with, must still be 2/3, but now is definitely 2/3 chance of being correct by just keeping current choice.

If we're shown a number that's BIGGER, the peeked-at value is the larger of the first two items in the three-item stack. The probability one of those two was the largest of the three was 2/3 to begin with, and it must still be 2/3 -- but now your choice (the smaller) has a 0% chance of being the largest, so all 2/3 of the possibility went to the peeked-at value. So, switch to the peeked-at value.

Modifications to ArrayStack

Question C-6.16) Make modifications to ArrayStack class so that it has a fixed size. ArrayStackFS.

Exception patterns

class Empty(Exception):
    pass

class Full(Exception):
    pass

Preallocating a list

C-6.17) Preallocating an underlying list (as opposed to having it grow from zero dynamically) requires more substantial changes to ArrayStack code.

class ArrayStack updates:

front index
length
data
when init: [None]*n
when pushing, increment front index
if not full
when popping, setting element to None

Swapping stacks

C-6.18) How to use transfer function to reverse order of stack?

transfer(S,T) transfers the contents, in reverse, of one stack onto another.

// Stack init already initialized
Stack temp1
transfer(init, temp1)
Stack temp2
transfer(temp1, temp2)
Stack final
transfer(temp2, final)
return final

Nonrecursive Enumerations

C-6.20) Give a non-recursive algorithm for enumerating all permutations of the numbers 1, 2, ...., n using an explicit stack.

def enumerate_all(n)

$P(n,k)={\dfrac {n!}{(n-k)!}}$

1 2 3 4 - 24 ways of permuting them

$P(4,3)={\dfrac {4!}{(4-3)!}}=24$

All possible subsets

Question C-6.20) Use stacks S and queues Q to generate all possible subsets of an n-element set T without using recursion.

Example: T = {1, 2, 3, 4}

All possible subsets: {1, 2, 3} , {1, 2, 4}, {1, 3,4}, {2, 3, 4}

The formula for this operation, subsets for which order is not important, we use the choose function, or n-choose-k function,

$C(n,k)={\dfrac {n!}{(n-k)!k!}}$

For the example given, there are 4 total elements, from which are are choosing 3, order ignored. That is 4 choose 3, for 4 outcomes:

$C(4,3)={\dfrac {4!}{(4-3)!3!}}=4$

corresponding to the 4 possible subsets given above.

This relates to the N Queens Problem, in which we use backtracking and Recursion to answer the question of how many non-attacking configurations of N queens can be found on an NxN chessboard. In the case of a standard chessboard, we are placing 8 queens on 64 possible squares - so n = 64 possible squares to choose, from which we select k = 8 - which we can express as 64 choose 8 (that's if we choose to ignore any solutions that are simply rotations of prior solutions, and not consider them "new".)

$C(64,8)={\dfrac {64!}{(64-8)!8!}}=4,426,165,368$

or about 4e9, or 4 billion.

Note that if we had considered each rotation of a given solution to count as a solution, we would have been using the n-pick-k function, which is substantially larger:

$P(64,8)={\dfrac {64!}{(64-8)!}}=178,462,987,637,760$

or around 2e14, or 178 trillion. That's 1e5 or 100,000 x bigger. Remember, this is the total number of possible solutions.

The algorithm to solve this using a stack, and doing in-place permutations in a sorted and methodical order, is as follows:

Sort string and give this as first permutation
Let i be the last index such that input[i] < input[i+1]
Let j be the last index such that input[i] < input[j]
Swap i and j
Reverse input i+1 thru end

See StacksQueues/Subsets for continued analysis and implementation.

Flags

StacksQueues/Python

From charlesreid1

Contents