## Stack and queue (Python)

The art of deceiving Hu 2020-11-13 03:19:56
stack queue python

Catalog

【 Stack 】

Order of the stack

Chain stack

Related topics

【 queue 】

Sequential queue

Circular queue

Chain queue

Related topics

【 recursive 】

## 【 Stack 】

• ### Order of the stack

Implementation and operation .

notes ： The difference with a linear table is that the position of data input and output is fixed .

``````import ctypes
# Order of the stack
class Stack():
def __init__(self):
self._capacity = 10
self._top = 0
self._A = self._make_array(self._capacity)
def isEmpty(self):
return self._top == 0
def push(self,value):
if self._top == self._capacity:
self._resize(self._capacity*2)
self._A[self._top] = value
self._top += 1
def pop(self):
if self.isEmpty():
raise Exception("no value")
else:
# value = self._A[self._top]
self._top -= 1
# return value
def clear(self):
while self._top:
self.pop()
def _make_array(self, c):
return (c* ctypes.py_object)()
def _resize(self, c):
B = self._make_array(c)
for i in range(self._top):
B[i] = self._A[i]
self._A = B
self._capacity = c
def _print(self):
for i in range(self._top):
print self._A[i],' ',
print ''``````

test ：

``````mystack = Stack()
mystack.push(1)
mystack.push(2)
mystack.push(3)
mystack.push(4)
mystack.push(5)
mystack.push(1)
mystack.push(2)
mystack.push(3)
mystack.push(4)
mystack.push(5)
mystack.push(1)
mystack.push(2)
mystack.push(3)
mystack.push(4)
mystack.push(5)
mystack._print()
mystack.pop()
mystack._print()
mystack.pop()
mystack._print()
mystack.pop()
mystack._print()
mystack.clear()
mystack._print()``````
• ### Chain stack

Implementation and operation .

``````# Order one first node Class
class Node(): #value + next
def __init__ (self, value = None, next = None):
self._value = value
self._next = next
def getValue(self):
return self._value
def getNext(self):
return self._next
def setValue(self,new_value):
self._value = new_value
def setNext(self,new_next):
self._next = new_next``````
``````# Chain stack
def __init__(self):
self._count = 0
self._top = None
def isEmpty(self):
def push(self,value):
new_node = Node(value,self._top)
self._top = new_node
self._count += 1
def pop(self):
last = self._top
self._top = self._top.getNext()
self._count -= 1
last.next = None
def clear(self):
while self._top:
self.pop()
def _print(self):
current = self._top
while current:
print current.getValue(),'<-',
current = current.getNext()
print ''``````

test ：

``````my_linkstack = LinkStack()
• ### Related topics

according to Reverse Polish notation , Find the value of the expression .

``````class Solution(object):
def evalRPN(self, tokens):
"""
:type tokens: List[str]
:rtype: int
"""
ret_list =[]
token = ['-','+','*','/']
for n in tokens:
if n in token:
second = ret_list.pop(-1)
first = ret_list.pop(-1)
if n == '-':
ret_list.append(first-second)
elif n=='+':
ret_list.append(first+second)
elif n=='*':
ret_list.append(first*second)
elif n=='/':
ret_list.append(int(first*1.0/second))
# if first*second<0 and first%second != 0:
# ret_list.append(first/second+1)
# else:
# ret_list.append(first/second)
else:
ret_list.append(int(n))
# print ret_list
return ret_list.pop(-1)``````

## 【 queue 】

• ### Sequential queue

Implementation and operation ：

``````import ctypes
# Sequential queue
class Queue():
def __init__(self):
self._capacity = 10
self._last = 0
self._A = self._make_array(self._capacity)
def isEmpty(self):
return self._last==0
def isFull(self):
return self._last == self._capacity
def enterqueue(self,value):
if self.isFull():
raise Exception("full")
else:
self._A[self._last] = value
self._last += 1
def delqueue(self):
if self.isEmpty():
raise Exception("empty")
else:
for i in range(self._last-1):
self._A[i] = self._A[i+1]
self._last -= 1
def clear(self):
while self._last:
self.delqueue()
def _make_array(self, c):
return (c* ctypes.py_object)()
def _print(self):
for i in range(self._last):
print self._A[i],' ',
print ''``````

test ：

``````myqueuq = Queue()
myqueuq.enterqueue(1)
myqueuq.enterqueue(2)
myqueuq.enterqueue(3)
myqueuq.enterqueue(4)
myqueuq.enterqueue(5)
myqueuq.enterqueue(6)
myqueuq.enterqueue(7)
myqueuq.enterqueue(8)
myqueuq.enterqueue(9)
myqueuq.enterqueue(10)
myqueuq._print()
myqueuq.delqueue()
myqueuq._print()
myqueuq.delqueue()
myqueuq._print()
myqueuq.delqueue()
myqueuq.delqueue()
myqueuq._print()
myqueuq.clear()
myqueuq._print()``````
• ### Circular queue

``````# Circular queue
class CycleQueue():
def __init__(self):
self._capacity = 10
self._font = 0
self._rear = 0
self._A = self._make_array(self._capacity)
def isEmpty(self):
return self._rear==self._font
def isFull(self):
return (self._rear +1)%self._capacity==self._font
def enterqueue(self,value):
if self.isFull():
raise Exception("full")
else:
self._A[self._rear] = value
self._rear = (self._rear+1)%self._capacity
def delqueue(self):
if self.isEmpty():
raise Exception("empty")
else:
self._font = (self._font+1)%self._capacity
def clear(self):
while self._last:
self.delqueue()
def _make_array(self, c):
return (c* ctypes.py_object)()
def _print(self):
if self._font<self._rear:
print '<<<<<<<<'
for i in range(self._font,self._rear):
print self._A[i],' ',
elif self._font>self._rear:
print '>>>>>>>>>>>>'
for i in range(0,self._rear):
print self._A[i],' ',
print "zzz ",
for i in range(self._font,self._capacity):
print self._A[i],' ',
print ''``````

test ：

``````myqueuq = CycleQueue()
myqueuq.enterqueue(1)
myqueuq.enterqueue(2)
myqueuq.enterqueue(3)
myqueuq.enterqueue(4)
myqueuq.enterqueue(5)
myqueuq.enterqueue(6)
myqueuq.enterqueue(7)
myqueuq.enterqueue(8)
myqueuq.enterqueue(9)
myqueuq._print()
myqueuq.delqueue()
myqueuq._print()
myqueuq.enterqueue(100)
myqueuq._print()
myqueuq.delqueue()
myqueuq.delqueue()
myqueuq._print()
myqueuq.enterqueue(100)
myqueuq.enterqueue(100)
myqueuq._print()``````
• ### Chain queue

``````# Chain queues
def __init__(self):
self._font = Node()
self._rear = Node(next=self._font)
def isEmpty(self):
return self._rear.getNext()==self._font
def enterqueue(self,value):
new_node = Node(value)
self._rear.getNext().setNext(new_node)
self._rear.setNext(new_node)
def delqueue(self):
if self.isEmpty():
raise Exception("empty")
else:
del_node = self._font.getNext()
self._font.setNext(del_node.getNext())
del_node.setNext(None)
def clear(self):
while not self.isEmpty():
self.delqueue()
def _print(self):
current = self._font.getNext()
while current:
print current.getValue(),'->',
current = current.getNext()
print ''``````

test ：

``````myqueuq = LinkQueue()
myqueuq.enterqueue(1)
myqueuq.enterqueue(2)
myqueuq.enterqueue(3)
myqueuq.enterqueue(4)
myqueuq.enterqueue(5)
myqueuq.enterqueue(6)
myqueuq.enterqueue(7)
myqueuq.enterqueue(8)
myqueuq.enterqueue(9)
myqueuq._print()
myqueuq.delqueue()
myqueuq._print()
myqueuq.enterqueue(100)
myqueuq._print()
myqueuq.delqueue()
myqueuq.delqueue()
myqueuq._print()``````
• ### Related topics

Design circular double end queue 】 Design and implement double end queue

``````class MyCircularDeque(object):
def __init__(self, k):
"""
Initialize your data structure here. Set the size of the deque to be k.
:type k: int
"""
self._A = []
self._countmax = k
def insertFront(self, value):
"""
Adds an item at the front of Deque. Return true if the operation is successful.
:type value: int
:rtype: bool
"""
if self.isFull():
return False
else:
self._A.insert(0,value)
return True
def insertLast(self, value):
"""
Adds an item at the rear of Deque. Return true if the operation is successful.
:type value: int
:rtype: bool
"""
if self.isFull():
return False
else:
self._A.append(value)
return True
def deleteFront(self):
"""
Deletes an item from the front of Deque. Return true if the operation is successful.
:rtype: bool
"""
if self.isEmpty():
return False
else:
self._A.pop(0)
return True
def deleteLast(self):
"""
Deletes an item from the rear of Deque. Return true if the operation is successful.
:rtype: bool
"""
if self.isEmpty():
return False
else:
self._A.pop()
return True
def getFront(self):
"""
Get the front item from the deque.
:rtype: int
"""
if self.isEmpty():
return -1
else:
return self._A[0]
def getRear(self):
"""
Get the last item from the deque.
:rtype: int
"""
if self.isEmpty():
return -1
else:
return self._A[-1]
def isEmpty(self):
"""
Checks whether the circular deque is empty or not.
:rtype: bool
"""
return len(self._A) == 0
def isFull(self):
"""
Checks whether the circular deque is full or not.
:rtype: bool
"""
return len(self._A) == self._countmax
``````

## 【 recursive 】

Suppose you're climbing the stairs . need  n  You can reach the top of the building . Every time you climb 1 or 2 A stair . How many different ways can you climb to the top of the building ？

notes ： The emphasis is on the conditions of the iteration and the output of the iteration termination . Sometimes problems may arise because the iteration is too deep , The corresponding matrix or one-dimensional array can be used to store the calculation results .

``````class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
fun = [1]*n
for nn in range(n):
if nn == 0:
fun[nn] = 1
elif nn == 1:
fun[nn] = 2
else:
fun[nn] = fun[nn-1]+fun[nn-2]
return fun[-1]``````