class Stack:
# Python list implementation of stacks
def __init__(self):
# construct an empty stack
self._data = []
def __str__(self):
# string representation of stack
return str(self._data)
# Left as homework; Use accumulator pattern
# self._data = [10,20,30,40,50] should be converted to the string "TOP: 10 20 30 40 50 :BOTTOM"
#return "HELLO"
def __len__(self):
# returns number of items in stack
return len(self._data)
def is_empty(self):
# returns True if stack is empty and False otherwise
return len(self._data) == 0
def top(self):
# returns top item of stack it stack is not empty; otherwise returns None
if len(self._data) != 0:
return self._data[0]
else:
return None
def pop(self):
# similar to top, except this also deletes top item from stack.
if len(self._data) != 0:
return self._data.pop(0)
else:
return None
def push(self,e):
# puts new item e on top of stack
self._data.insert(0,e)
def reverse():
# implements the Reverse program
while True:
s = input("input a string (q to quit): ")
if s == "q":
break
stack = Stack()
for c in s:
stack.push(c)
result = "reverse of string: "
for i in range(len(s)):
c = stack.pop()
result = result + c
print(result)
reverse()
$ python3 Reverse.py
input a string (q to quit): abcdef
reverse of string: fedcba
input a string (q to quit): madam
reverse of string: madam
input a string (q to quit): q
s1 = Stack()
s1.push(5)
s1.push(7)
s1.push(2)
e = s1.pop()
s1.push(8)
print(s1)
x = [20, 30, 40]
x.insert(0,10)
x.insert(0,90)
item = x.pop(0)
print(x)
print(x[1])
print(item)
nums = []
for i in range(10):
nums.insert(0,i)
print(nums)
print(len(nums))
if ????:
return True
else:
return False
same as
????
[None,None,30,40,50,60,None,None,None,None]
"TOP: 10 20 30 40 50 :BOTTOM"
GRACEFUL EXIT NON-GRACEFUL EXIT
class Queue:
# Circular List Implementation
CAPACITY = 10
def __init__(self):
# instance variables: _data, _size, _front
self._data = [None]*CAPACITY
self._front = 0
self._size = 0
def __str__(self):
# string representation of queue
return str(self._data)+" "+str(self._front) + " "+str(self._size)
# modify this to show "FRONT: 20 30 50 :BACK"
def __len__(self):
# return length of queue
return self._size
def is_empty(self):
# return True if queue is empty otherwise return False
return self._size == 0
def first(self):
# return first item of queue if it is not empty; otherwise return None
if self._size != 0:
return self._data[self._front]
else:
return None
def dequeue(self):
# remove and return first item in queue; return None if queue is empty
if self._size == 0:
return None
item = self._data[self._front]
self._data[self._front] = None
self._size = self._size = 1
self._front = (self._front + 1)%len(self._data)
return item
def enqueue(self,e):
# add item e to the end of queue. If list is full, resize the list by
# creating a new list of twice the size and moving items from old list
# to new list; Do not forget to adjust _size and _front
if self._size == len(self._data):
self._resizeUp(2*len(self._data))
pos = (self._front + self._size)%len(self._data) # please verify that pos is the position of the None after the last item in queue
self._data[pos] = e
self._size = self._size + 1
def _resizeUp(self,cap):
# method to resize
???
???
[1,2]*5