cf. pp. 60 McDowell, 6th Ed. What you Need to Know, Core data Structures, Algorithms, and Concepts
| Data Structures | Algorithms | Concepts |
|---|---|---|
| Linked Lists | Breadth-First Search | Bit Manipulation |
| Trees, Tries, & Graphs | Depth-First Search | Memory (Stack vs. Heap) |
| Stacks & Queues | Binary Search | Recursion |
| Heaps | Merge Sort | Dynamic Programming |
| Vectors/ArrayLists | QuickSort | Big O Time & Space |
| Hash Tables |
http://interactivepython.org/runestone/static/pythonds/BasicDS/ImplementingaStackinPython.html
In [1]:
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)
In [3]:
s=Stack()
print(s.isEmpty())
In [4]:
s.push(4)
s.push('dog')
print(s.peek())
In [5]:
s.push(True)
print(s.size())
print(s.isEmpty())
s.push(8.4)
print(s.items)
In [6]:
print(s.pop())
print(s.pop())
print(s.size())
cf. 3 Stacks and Queues, Cracking the Coding Interview, 6th Ed., McDowell, stack uses LIFO - as in a stack of dinner plates, the most recent item added to the stack is the 1st item to be removed.
In [7]:
class Queue:
def __init__(self):
self.items = []
def add(self,item):
self.items.append( item )
def remove(self):
self.items.remove( self.items[0])
def peek(self):
return self.items[0]
def isEmpty(self):
return self.items == []
In [10]:
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
In [11]:
print(parChecker('((()))'))
In [12]:
print(parChecker('(()'))
In [13]:
def parChekcer(symbolString):
s = Stack()
balanced = True
index = 0
while index < len(symbolString) and balanced:
symbol = symbolString[index]
if symbol in "([{":
s.push(symbol)
else:
if s.isEmpty():
balanced = False
else:
top = s.pop()
if not matches(top,symbol):
balanced = False
index = index + 1
if balanced and s.isEmpty():
return True
else:
return False
def matches(open,close):
opens = "([{"
closers = ")]}"
return opens.index(open) == closers.index(close)
print(parChecker('{{([][])}()}') )
In [14]:
print(parChecker('[{()]'))
In [15]:
def divideBy2(decNumber):
remstack = Stack()
while decNumber >0:
rem = decNumber % 2
remstack.push(rem)
decNumber = decNumber // 2
binString = ""
while not remstack.isEmpty():
binString = binString + str(remstack.pop())
return binString
print(divideBy2(42))
In [16]:
divideBy2(233)
Out[16]:
In [17]:
def baseConverter(decNumber,base):
digits = "0123456789ABCDEF"
remstack=Stack()
while decNumber >0:
rem = decNumber % base
remstack.push(rem)
decNumber = decNumber // base
newString = ""
while not remstack.isEmpty():
newString = newString + digits[remstack.pop()]
return newString
In [18]:
print(baseConverter(25,2))
print(baseConverter(25,16))
In [20]:
print(baseConverter(25,8))
In [22]:
print(baseConverter(256,16))
print(baseConverter(26,26))
In [26]:
# Node class
class Node:
# Function to initialize the node object
def __init__(self,data):
self.data = data # Assign data
self.next= None # Initialize
# next as null
# Linked List class
class LinkedList:
# Function to initialize the Linked
# List object
def __init__(self):
self.head = None
# This function prints contents of linked list
# starting from head
# traversal of a linked list
def printList(self):
temp = self.head
while (temp):
print temp.data
temp = temp.next
In [27]:
# Start with the empty list
llist = LinkedList()
llist.head = Node(1)
second = Node(2)
third = Node(3)
llist.head.next = second; # Link 1st node with second
second.next = third
In [28]:
llist.printList()
In [29]:
class Node:
def __init__(self,val):
self.val = val
self.next = None
class LinkedList:
def __init__(self,val=None):
if val is None:
self.head = None
else:
self.head = Node(val)
def insertEnd(self,val):
temp = self.head
while(temp.next): # check if temp has a next
temp = temp.next # keep traversing
temp.next = Node(val)
def printList(self):
temp = self.head
while (temp): # stop when temp is a None, which could happen with next in Node
print temp.val
temp = temp.next
In [34]:
llist = LinkedList(1)
llist.printList()
llist.insertEnd(2)
llist.printList()
llist.insertEnd(4)
llist.printList()
llist.insertEnd(2)
llist.printList()
llist.insertEnd(6)
llist.printList()
llist.insertEnd(7)
llist.printList()
In [ ]: