Class Notes (1,100,000)
CA (620,000)
UTSC (30,000)
Lecture 1

CSCA48H3 Lecture Notes - Lecture 1: Init


Department
Computer Science
Course Code
CSCA48H3
Professor
Brian Harrington
Lecture
1

This preview shows half of the first page. to view the full 2 pages of the document.
class EmptyQueueError(Exception):
pass
def dequeue(self: 'Queue') -> object:
if self.isempty():
raise EmptyQueueError
Exceptions:
An abstract data type specifies a set of operations (or methods) and the semantics of the
operations, but it does not specify the implementation of the operations.
It simplifies the task of specifying an algorithm if you can denote the operations you
need without having to think at the same time about how the operations are
performed
Since there are usually many ways to implement an ADT, it might be useful to write
an algorithm that can be used with any of the possible implementation
Well-known ADTS, such as the Stack ADT are often implemented in standard
libraries so they can be written once and used by many programmers
The operations on ADTs provide a common high level language for specifying and
talking about algorithms
Why is it useful?:
Initialize a new empty stack.
__init__
Add a new item to the stack.
push
Remove and return an item from the stack. The item that is returned is always
the last one that was added.
pop
Check whether the stack is empty.
is_empty
An ADT is defined by the operations that can be performed on it, which is called
an interface. The interface for a stack consists of these operations:
A stack is a generic data structure, which means that we can add any type of item to it.
>>> s =Stack()
>>> s.push(54)
>>> s.push(45)
>>> s.push("+")
Example: pushes two integers and a string onto the stack:
We can use is_empty and pop to remove and print all of the items on the stack:
The output is + 45 54
1
2
while not s.is_empty():
print(s.pop(), end=" ")
1
2
3
4
5
6
7
8
9
10
11
12
class Stack:
def __init__(self):
self.items =[]
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def is_empty(self):
return (self.items == [])
Implementing a Stack ADT:
The Stack ADT:
A queue is a line of people waiting for something, in most cases first person in line is the
next one to be served
The Queue ADT:
CSCA48 Week 1 (ADT, Stacks, Queue)
February 5, 2016
7:31 PM
CSCA48 Page 1
You're Reading a Preview

Unlock to view full version