Python Programming

Lecture 16 Basic Data Structure

16.1 Stacks

Linear Structures
  • Stacks queues, deques, and lists are examples of data collections whose items are ordered depending on how they are added or removed.
  • Once an item is added, it stays in that position relative to the other elements that came before and came after it. Collections such as these are often referred to as linear data structures.
Stacks (栈)
  • A stack is an ordered collection of items where the addition of new items and the removal of existing items always takes place at the same end.
  • This ordering principle is sometimes called LIFO, last-in first-out.
The Stack Abstract Data Type
  • The stack abstract data type is defined by the following structure and operations.
  • Stack() creates a new stack that is empty. It needs no parameters and returns an empty stack.
  • push(item) adds a new item to the top of the stack. It needs the item and returns nothing.
  • pop() removes the top item from the stack. It needs no parameters and returns the item. The stack is modified.
  • peek() returns the top item from the stack but does not remove it. It needs no parameters. The stack is not modified.
  • is_empty() tests to see whether the stack is empty. It needs no parameters and returns a boolean value.
  • size() returns the number of items on the stack. It needs no parameters and returns an integer.
Implementing a Stack in Python
  • To implement a stack, which is a collection of elements, it makes sense to utilize the power and simplicity of the primitive collections provided by Python. We will use a list.

class Stack:
     def __init__(self):
         self.items = []

     def isEmpty(self):
         return self.items == []

     def push(self, item):
         self.items.append(item)

     def pop(self):
         return self.items.pop()

     def peek(self):
         return self.items[len(self.items)-1]

     def size(self):
         return len(self.items)

class Stack:
    def __init__(self):
        self.items = []
    def isEmpty(self):
        return self.items == []
    def push(self, item):
        self.items.append(item)
    def pop(self):
        return self.items.pop()
    def peek(self):
        i = len(self.items)-1
        return self.items[i]
    def size(self):
        return len(self.items)

s=Stack()

print(s.isEmpty())
s.push(4)
s.push('dog')
print(s.peek())
s.push(True)
print(s.size())
print(s.isEmpty())
s.push(8.4)
print(s.pop())
print(s.pop())
print(s.size())

True
dog
3
False
8.4
True
2
Simple Balanced Parentheses
  • Parentheses must appear in a balanced fashion. Balanced parentheses means that each opening symbol has a corresponding closing symbol and the pairs of parentheses are properly nested. Consider the following correctly balanced strings of parentheses:

(()()()())
(((())))
(()((())()))
  • Compare those with the following, which are not balanced:

((((((())
()))
(()()(()

def parChecker(symbolString):
    s = Stack()
    balanced = True
    index = 0
    while index < len(symbolString) and balanced:
        symbol = symbolString[index]
        if symbol == "(":
            s.push(symbol)
        else:
            if s.isEmpty():
                balanced = False
            else:
                s.pop()
        index = index + 1

    if balanced and s.isEmpty():
        return True
    else:
        return False

print(parChecker('((()))'))
print(parChecker('(()'))

16.2 Queues and Deques

Queues (队列)
  • A queue is an ordered collection of items where the addition of new items happens at one end
  • The most recently added item in the queue must wait at the end of the collection. The item that has been in the collection the longest is at the front. This ordering principle is sometimes called FIFO, first-in first-out.
The Queue Abstract Data Type
  • Queue() creates a new queue that is empty. It needs no parameters and returns an empty queue.
  • enqueue(item) adds a new item to the rear of the queue. It needs the item and returns nothing
  • dequeue() removes the front item from the queue. It needs no parameters and returns the item. The queue is modified.
  • is_empty() tests to see whether the queue is empty. It needs no parameters and returns a boolean value.
  • size() returns the number of items in the queue. It needs no parameters and returns an integer.

class Queue:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def enqueue(self, item):
        self.items.insert(0,item)

    def dequeue(self):
        return self.items.pop()

    def size(self):
        return len(self.items)

>>> q.size()
3
>>> q.isEmpty()
False
>>> q.enqueue(8.4)
>>> q.dequeue()
4
>>> q.dequeue()
'dog'
>>> q.size()
2
Simulation: Hot Potato
  • One of the typical applications for showing a queue in action is to simulate a real situation that requires data to be managed in a FIFO manner.
  • To begin, let's consider the children's game Hot Potato.
  • This game is a modern-day equivalent of the famous Josephus problem. Based on a legend about the famous first-century historian Flavius Josephus, the story is told that in the Jewish revolt against Rome, Josephus and 39 of his comrades held out against the Romans in a cave. With defeat imminent, they decided that they would rather die than be slaves to the Romans. They arranged themselves in a circle. One man was designated as number one, and proceeding clockwise they killed every seventh man.
  • We will implement a general simulation of Hot Potato. Our program will input a list of names and a constant, call it "num" to be used for counting. It will return the name of the last person remaining after repetitive counting by num.

def hotPotato(namelist, num):
    simqueue = Queue()
    for name in namelist:
        simqueue.enqueue(name)

    while simqueue.size() > 1:
        for i in range(num):
            simqueue.enqueue(simqueue.dequeue())

        simqueue.dequeue()

    return simqueue.dequeue()

print(hotPotato(["Bill","David","Susan","Jane","Kent","Brad"],7))
Deques (双端队列, not dequeue!)
  • A deque, also known as a double-ended queue, is an ordered collection of items similar to the queue.
  • What makes a deque different is the unrestrictive nature of adding and removing items. New items can be added at either the front or the rear. Likewise, existing items can be removed from either end.
  • It is important to note that even though the deque can assume many of the characteristics of stacks and queues, it does not require the LIFO and FIFO orderings that are enforced by those data structures. It is up to you to make consistent use of the addition and removal operations.
The Queue Abstract Data Type
  • Deque() creates a new deque that is empty. It needs no parameters and returns an empty deque.
  • add_front(item) adds a new item to the front of the deque. It needs the item and returns nothing.
  • add_rear(item) adds a new item to the rear of the deque. It needs the item and returns nothing.
  • remove_front() removes the front item from the deque. It needs no parameters and returns the item. The deque is modified.
  • remove_rear() removes the rear item from the deque. It needs no parameters and returns the item. The deque is modified.
  • is_empty() tests to see whether the deque is empty. It needs no parameters and returns a boolean value.
  • size() returns the number of items in the deque. It needs no parameters and returns an integer.
Implementing a Deque in Python

class Deque:
    def __init__(self):
        self.items = []
    def isEmpty(self):
        return self.items == []

    def addFront(self, item):
        self.items.append(item)

    def addRear(self, item):
        self.items.insert(0,item)

    def removeFront(self):
        return self.items.pop()

    def removeRear(self):
        return self.items.pop(0)
    def size(self):
        return len(self.items)

Summary

  • Stacks
  • Queues
  • Deques