Back
ADT - abstract data type
- a type of object whose behavior is defined by a set of values and operations
- eg. Stack ADT, Queue ADT, Trees ADT
Stack
- last-in-first-out order
- only one end is open to be added or removed (which is top)
- methods which a Stack should have includes
how to build a stack!!
class Stack:
def __init__(self):
self._theItems = list()
def isEmpty(self):
return True if self.__len__() == 0 else False
def __len__(self):
return len(self._theItems)
def pop(self):
# assert throws an exception when the value after it is a false
# in this case, isEmpty() will return a false if the stack is not empty
# Although isEmpty() should be a false, assert will throw an err instead of running
# so must put a "not" before isEmpty(), so that it could be a true when the stack is
# not empty, and runs smoothly
assert not isEmpty(), "Cannot remove from empty stack"
return self._theItems.pop()
def push(self,val):
self._theItems.append(val)
def peek(self):
assert not isEmpty(), "Cannot peek from empty stack"
return self._theItems[self.__len__() - 1] # shows the top valueInfix, Postfix, Prefix mathematical expressions
- 2 * 5 - 1 (infix) = 9
- 25*1- (postfix) (which uses stack)
- prefix
The advantage of using prefixes and postfixes is need not to use parentheses while infix needs.
- for same lvl of operation, just go left to right
Conversion of infix to postfix
eg. A * B + C / D
Steps:
- put parentheses in the correct places
- For each set of parentheses, move the operator from the middle to the
- remove parentheses
Conversion of infix to prefix
eg. A * B + C / D
Steps:
- (A*B)+(C/D)
- ((*AB)+(/CD))
- +*AB/CD
Exercises for infix to postfix AND prefix
A * (B + C) / D
postfix = (A*(B+C))/D ⇒ (A(BC+)*)D/ ⇒ ABC+*D/
prefix = (A*(B+C))/D ⇒ /(*A(+BC))D ⇒ /*A+BCD
( ( AX + ( B * CY ) ) / ( D - E ) )
postfix = ((AX(BCY*)+)(DE-)/ ⇒ AXBCY*+DE-/
prefix = /(+ AX(*BCY))(-DE) ⇒ /+ AX * BCY - DE
( AX + ( B * C ) )
postfix = AXBC*+
prefix = + AX*BC
A+B∗C/D−E
= (A + ((B * C)/ D)) - E
postfix
= (A(BC*D/ )+)E - ⇒ ABC*D/+E-
prefix
= - (+ A(/(*BC)D))E ⇒ -+ A/ * BCDE
Evaluating postfix expressions
How to evaluate postfix/prefix expression
Queue
- first in first out ADT
- add at one end (back) and remove from front
Queue with python list
Enqueue
- array has the capacity
- when the capacity of the array is full, we will create a new temp array with double the capacity
- then we need to copy everything from the prev array
- hence, it will take O(n) time in the worst case
Dequeue
- removing item from the array also takes O(n) time because the first value (index 0 ) of the array will be removed and so the items behind need to shift their positions
To improve, we come up with Circular array.
Circular array queue
def __init__( self, maxSize ) :
self._count = 0
self._front = 0
self._back = maxSize - 1
self._qArray = [None] * maxSize
# Returns True if the queue is empty.
def isEmpty( self ) :
return self._count == 0
# Returns True if the queue is full.
def isFull( self ) :
return self._count == self._qArray
# Returns the number of items in the queue.
def __len__( self ) :
return self._count
# Adds the given item to the queue.
def enqueue( self, item ):
assert not self.isFull(), "Cannot enqueue to a full queue."
maxSize = len(self._qArray)
# here we use( self._back + 1 ) % maxSize
# because we want it to be circular
# when the self._back + 1 exceeds maxSize
# it will restart from 0
self._back = (self._back+1) % maxSize
self._qArray[self._back] =item
self._count += 1
# Removes and returns the first item in the queue.
def dequeue( self ):
assert not self.isEmpty(), "Cannot dequeue from an empty queue."
item = self._qArray[self._front]
maxSize = len(self._qArray) - 1
self._front = (self._front+1) % maxSize
self._count -= 1
return item
# Return the content of the queue (with array index in square
# brackets].
def __str__( self ) :
maxSize = len(self._qArray)
outStr = ''
for i in range(self._count):
outStr += ('[' + str((self._front + i) % maxSize) + ']:')
outStr += (str(self._qArray[(self._front + i) % maxSize]) + ' ')
return outStr