CSCA48H3 Lecture Notes - Lecture 1: Init
This preview shows half of the first page. to view the full 2 pages of the document.
def dequeue(self: 'Queue') -> object:
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
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?:
Abstract Data Types (ADT):
Initialize a new empty stack.
Add a new item to the stack.
Remove and return an item from the stack. The item that is returned is always
the last one that was added.
Check whether the stack 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()
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
while not s.is_empty():
print(s.pop(), end=" ")
def push(self, item):
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
CSCA48 Page 1
You're Reading a Preview
Unlock to view full version