Learning Outcomes

• Understand what an Abstract Data Type is
• Realize that many of Python's types are ADTs
• Become familiar with Stacks & Queues
• Be able to write a program that uses a stack
• Be able to write a program that uses a queue
• Be able to make good data structure choices

Abstract data types

• Abstract data types or ADTs are a mathematical specification of a set of data and the set of operations that can be performed on the data.
• We think of an abstract data type as a type defined in terms of its behavior rather than its implementation.
• Technically, we define an abstract data type as a mathematical object and the operations on that object.

The ADTs we've worked with so far are :

• strings
• lists
• sets
• dictionaries

all of which are built-in data types of Python.

ADT - Example

Abstract data types do not have to be large data collections, as the ones are that we've worked with so far.

Whenever we define an ADT, we need to give a definition and a list of operations.

Fractions

A fraction consists of a numerator and denominator and is used when discussing parts of a whole.

Example: The fraction 1/2 means that if an object is divided into two equal parts, then we are working with one of those parts.

The 1 is known as the numerator and the 2 is known as the denominator. Both the numerator and denominator of a fraction are integers. The denominator cannot be 0.

When working with fractions, we are sometimes interested in a whole number as well, as in 5/4 = 1 1/4. Numbers expressed as fractions can have a whole number part as well as a fractional part.

The operations on fractions include :

• addition
• subtraction
• multiplication
• division
• reduce to lowest terms
• find least common denominator
• etc.

Since we have just defined a mathematical object (the fraction) and the operations on that object, we can say that a fraction is an abstract data type.

Notice that we haven't discussed the implementation of any of our ADTs

ADTs typically can be implemented in many different ways, and often are implemented differently when using different languages.

Complete the Operations

In order to work with your new type, you will probably have to write functions that will allow you to :

• inititalize a variable of this new type
• assign some values into a variable of the new type
• print this new type in a meaningful way

For instance, to print a fraction you would need:

    print '%d %d/%d' % (whole, numerator, denominator)

When writing the code to implement your new type, you should try to give it all of the functionality you can foresee. For instance, if you are writing a program using fractions, and it is only necessary for this program to be able to add and subtract fractions, you should also implement multiplication and division, to produce a fully-usable ADT.

The Queue

Background

A queue is what Americans commonly refer to as a line. The example is that you get into a line at the grocery store. In Great Britain, lines, like the line of customers waiting at the checkout, are called queues. The word queue is more specific. The word line can also mean, a line between two points, the line down the middle of the road, etc.

People have been exposed to the idea of getting in line, or "queueing up", as the Brits say, since their mothers took them to the bank or the grocery store in their strollers. So we all know the rules of a queue.

A queue is a linear collection, where something to be added to the queue must be placed at the end of the queue. Items are removed from the queue from the front. To keep with the analogy, when you walk into the bank you go to the end of the queue. When the teller is ready to help the next person, the person at the beginning of the queue is removed from the queue. Each person then moves one position closer to the beginning of the queue. Eventually, you will be the first person in the queue and the teller will call you up causing you to be removed from the queue.

A queue is refered to as a FIFO data structure: First In, First Out.

The Queue ADT

The definition

A queue is a linear collection of items, where an item to be added to the queue must be placed at the end of the queue and items that are removed from the queue must be removed from the front. The end of the queue is known as the tail and the front of the queue is known as the front. The term enqueue means to add an item to the queue, and the term dequeue means to remove an item from the queue.

The operations

There are actually very few operations on a queue.

• enqueue - add an item to the queue
• dequeue - remove an item from the queue
• front - access the first item at the front of the queue

A queue is NOT a built-in data type in Python, however you could write these functions that make use of Python's list methods.

The Stack

Background

A stack is a little harder to define than a queue, since there isn't a common term that will relate how a stack works. It is definitely a linear collection of similar items. Stacks have access rules too, but the rules are different than the rules for queues.

You have been exposed to the idea of a stack before. When you go to a cafeteria to get lunch you take a tray from the stack of trays. You must always take the tray that is on the top of the stack. The cafeteria personnel put clean trays on the stack. The clean trays are always added to the top of the stack, so the tray that's on top is the last one that was added.

A stack is refered to as a LIFO data structure: Last In, First Out.

The Stack ADT

The definition

A stack is a linear collection of similar items, where an item to be added to the stack must be placed on top of the stack and items that are removed from the stack must be removed from the top. The top of the stack is known as the top. The term push means to add an item to the stack, and the term pop means to remove an item from the stack.

The operations

There are actually very few operations on a stack.

• push - add an item to the stack
• pop - remove an item from the stack
• top - access item at the top of the stack

A stack is NOT a built-in data type in Python, however you could write these functions that make use of python's list methods.

Queues, Stacks, & Priority Queues

• The purpose of a queue is to keep items in the same order as they were enqueued.
  • A print queue is one place a queue is used that you may be familiar with. The jobs that are sent to the printer are kept in the order they are received until and printed one at a time.
  • A non-CS queue example: Waiting list for tables at a restaurant
• The purpose of a stack is to reverse the order of items
  • When a program is executing and functions are called, a stack is used to keep track of the program's position and values of local variables.
• There is another often used ADT known as a priority queue, where items are added to the list in sorted order according to their priority.

Use cases:

What data structures would you use for these programs?

• Simulation of waiting times at a bank
• Program that helps you figure out what order to load materials onto a truck (heaviest items first)
• Backtracking maze solver
• Program that stores hits from a search engine and then reports the top 10 most relevant hits

Using a stack

• Let's write a program to get names of cars from the user and print out the names in reverse order at the end. You should write the
  • push() function to push a generic item onto the stack
  • pop() function to pop a generic item from the stack
  • top() function that returns the item at the top of the stack, BUT does not pop that item from the stack.
  • isEmpty() function checks to see if stack is empty

# Filename: stack.py
# Contains the code to implement a Stack

# stack()  
# creates a new stack 
# Inputs: None 
# Output: an empty stack 
def stack(): 
    return [] 

# top()
# returns the item on top of the stack without popping
# Inputs: items, a stack
# Output: an item from the stack, if not empty
def top(items):
    if isEmpty(items):
        return None
    else:
        return items[-1]
 
# isEmpty(items)  
# checks to see if stack is empty 
# Inputs: items, a stack 
# Output: True is stack is empty, False if not 
def isEmpty(items): 
    return len(items) == 0 

# push(items, item) 
# pushes the item passed in onto the stack passed in, items.
# Inputs: items, a stack
#         item,  an item to push onto the stack 
# Output: None
def push(items, item):
    items.append(item)

    
# pop(items) 
# pops an item from the stack passed in and returns it.
# Input: items, a stack
# Output: popped, the item popped from the stack or 
#         "Empty Stack" if the stack was empty
def pop(items):
    size = len(items)

    if size > 0:
        popped = items[-1]
        del(items[-1])
        return popped
    else:
        return "Empty Stack"

# Filename: pop.py
# Driver program to test Stack functions

# import statement allows us to use the stack functions
# contained in stack.py
from stack import *

def main():
    cars = stack()
    push(cars, 'Audi')
    print 'pushing Audi'
    push(cars, 'Buick')
    print 'pushing Buick'
    push(cars, 'Chevy')
    print 'pushing Chevy'
    push(cars,  'Dodge')
    print 'pushing Dodge'
    print
    
    while not isEmpty(cars):
        print 'popping', pop(cars)

main()

Let's run it!

ite207-pc-01.cs.umbc.edu[138] python pop.py
pushing Audi
pushing Buick
pushing Chevy
pushing Dodge

popping Dodge
popping Chevy
popping Buick
popping Audi
ite207-pc-01.cs.umbc.edu[139] 

ADT Exercise

• Write enqueue()







• Write dequeue()