0. 目標(biāo)
- To understand the abstract data types **stack, queue, deque, and list **.
- To be able to implement the ADT‘s stack, queue, and deque using Python lists.
- To understand the performance of the implementations of basic linear data structures.
- To understand prefix, infix, and postfix expression formats.
- To use stacks to evaluate postfix expressions.
- To use stacks to convert expressions from infix to postfix.
- To use queues for basic timing simulations.
- To be able to recognize problem properties where stacks, queues, and deques are appropriate data structures.
- To be able to implement the abstract data type list as a linked list using the node and reference pattern.
- To be able to compare the performance of our linked list implementation with Python’s list
implementation.
1. 課程筆記
1.1 線性數(shù)據(jù)結(jié)構(gòu)——stack 堆
- stack特點(diǎn)1：LIFO last-in-fist-out漆诽， 最近的在Top溜腐，最老的在Base （例如一堆書(shū)）榆骚。常見(jiàn)例子：瀏覽過(guò)的URL存儲(chǔ)在stack的數(shù)據(jù)結(jié)構(gòu)棠涮，點(diǎn)擊Back button可以退回到上一個(gè)谦炬。
- stack的實(shí)現(xiàn)
- stack( ): 空的stack
- push (item): 加入一個(gè)新數(shù)據(jù)在stack top，無(wú)返回
- pop ( ): 移除一個(gè)在stack top黍析，返回item
- peek( ): 返回top item卖怜，但對(duì)stack 沒(méi)有修改
- is_empty( ): 返回布爾值
- size( ): stack的大小，返回一個(gè)整數(shù)阐枣。
class Stack(): #最右邊是top
def __init__(self):
self.stack = []
def is_empty(self):
if self.stack == []:
return True
else:
False
def push(self, item):
self.stack.append(item)
return self.stack
def pop(self):
m =self.stack.pop()
return m
def peek(self):
last_num = len(self.stack) - 1
return self.stack[last_num]
def size(self):
num = len(self.stack)
return num
from Stack_function import Stack ##從相同工程下的Stack_function.py取出Stack class的定義
s = Stack()
print(s.is_empty())
print(s.push(4))
print(s.push(5))
print(s.push('dog'))
print(s.pop())
print(s.peek())
print(s.size())
-
stack應(yīng)用一：翻轉(zhuǎn)字符串
a20a5b41-53cd-4435-94c5-0030a377c06a.png
def reverse(self):
new_list = []
i = len(self.stack) - 1
while i >= 0:
m = self.stack[i]
new_list.append(m)
i = i - 1
return new_list
- stack 應(yīng)用二：檢查括號(hào)是否成對(duì)出現(xiàn)：將符號(hào)放入stack中
from Stack_function import Stack
def cheek_balance(list):
mystack = Stack() # 初始化一個(gè)stack的空間
index = 0
num = len(list)
while index < num and index >= 0:
i = list[index] #從list中取出一個(gè)需要判斷的符號(hào)
if i == '(': #push進(jìn)stack
mystack.push(i)
if i == ')' and mystack.is_empty():
return 'sorry, it is not balance'
if i == ')':
mystack.pop()
index = index + 1
if mystack.is_empty() == True:
return 'perfect'
else:
return 'sorry'
- stack 應(yīng)用三：十進(jìn)制轉(zhuǎn)化成二進(jìn)制：將余數(shù)放入stack中
from Stack_function import Stack
def dicimal_to_binary(k):
mystack = Stack()
new_string = ''
if k == 1: #排除0马靠、1的二進(jìn)制
return 1
if k == 0:
return 0
else:
while k != 0:
remainder = k % 2 # 余數(shù)
mystack.push(remainder)
k = k // 2 #除數(shù)
while not mystack.is_empty():
index = str(mystack.pop())
new_string = new_string + index #字符串可以通過(guò)加號(hào)連接
return new_string
print(dicimal_to_binary(20))
1.2 線性結(jié)構(gòu)——Queue 隊(duì)列
- 特點(diǎn)： FIFO
- 實(shí)現(xiàn)queue的數(shù)據(jù)結(jié)構(gòu)
class Queue():
def __init__(self):
self.queue = []
def enqueue(self, item):
self.queue.insert(0, item)
def dequeue(self):
return self.queue.pop()
def is_empty(self):
if len(self.queue) == 0:
return True
else:
return False
#return self.queue == []
def size(self):
return len(self.queue)
def print_queue(self):
return self.queue
- queue的應(yīng)用一：燙手的山芋(hot potato): 約瑟夫環(huán)問(wèn)題
from queue_structure import Queue
def hot_potato(List, num):
queue = Queue() # 初始化一個(gè)排隊(duì)
for i in List:
queue.enqueue(i)
print(queue.print_queue()) #放入queue，已將考慮了bill在最前面
while queue.size() > 1: #最后只剩下一個(gè)人
for k in range(num): # k = 1,2,3,4,5,6,7
name = queue.dequeue()
queue.enqueue(name)
queue.dequeue() #達(dá)到7次后刪除第一個(gè)
return queue.print_queue()
Namelist = ["Bill","David","Susan","Jane","Kent","Brad"]
print (hot_potato(Namelist, 7))
- queue的應(yīng)用二：打印機(jī)任務(wù)建模
1.3 線性結(jié)構(gòu)——Dequeue 雙端隊(duì)列
- 特點(diǎn)： 兩端都可以插入和輸入
- 實(shí)現(xiàn)dequeue
class Dequeue():
def __init__(self):
self.dequeue = []
def add_front(self, item):
self.dequeue.append(item)
def add_back(self, item):
self.dequeue.insert(0, item)
def delete_front(self):
return self.dequeue.pop()
def delet_back(self):
return self.dequeue.pop(0)
def is_empty(self):
if self.dequeue == []:
return True
else:
return False
def size(self):
return len(self.dequeue)
def print_dequeue(self):
print(self.dequeue)
- 雙端隊(duì)列的應(yīng)用：回文檢測(cè)
① 一個(gè)數(shù)據(jù)結(jié)構(gòu)(list)侮繁， 不可能憑空變成另一種數(shù)據(jù)結(jié)構(gòu)(dequeue)虑粥，只能通過(guò)一個(gè)一個(gè)添加的方法，將數(shù)據(jù)錄入dequeue
②下面的dequeue的數(shù)據(jù)結(jié)構(gòu)宪哩，沒(méi)有dequeue[0]，因?yàn)闆](méi)有定義
from dequeue_structure import Dequeue
def Palindrome_check(list):
dequeue = Dequeue()
n = len(list)
for i in range(n):
dequeue.add_back(list[i]) #倒敘輸入到dequeue中
dequeue.print_dequeue()
while dequeue.size() > 1:
if dequeue.delete_back() == dequeue.delete_front():
continue
else:
return "False"
return "True"
1.4 無(wú)序隊(duì)列(節(jié)點(diǎn)存儲(chǔ)的數(shù)字大小是隨機(jī)的)——鏈表(liked list)
- 為什么要使用鏈表第晰？
list插入的時(shí)候耗時(shí)太長(zhǎng)（需要向后移動(dòng)） - 存儲(chǔ)特點(diǎn)：
① 節(jié)點(diǎn)：一個(gè)具體存放的數(shù)值&下一個(gè)節(jié)點(diǎn)的地址
② head = none锁孟，既是代表了每個(gè)節(jié)點(diǎn)next node
③ 先add的當(dāng)作old list，將最近添加的node連接到old list - 構(gòu)造鏈表結(jié)構(gòu)
class Node:
def __init__(self, initdata):
self.data = initdata
self.next = None
def get_data(self):
return self.data
def get_next(self): #type:Node
return self.next
def set_data(self, new_data):
self.data = new_data
def set_next_node(self, new_next):
self.next = new_next
- 實(shí)現(xiàn)鏈表
class UnorderList:
def __init__(self):
self.head = None #!! the end of structure / the entrance point
def is_empty(self):
return self.head == None #查看是否有head之后有node連接
def add(self, item):
temp = Node(item) #初始化一個(gè)節(jié)點(diǎn)
temp.set_next_node(self.head) #連接上end茁瘦， 或者old list node
self.head = temp
def print_link_list(self):
current = self.head
list = []
while current != None:
item = current.get_data()
list.append(item)
current = current.get_next()
return list
def size(self):
current = self.head
sum_node = 1
while current.get_next() != None:
sum_node = sum_node + 1
current = current.get_next()
return sum_node
def search(self, item):
current = self.head # star at the head
while current.get_next() != None:
if current.get_data() == item:
return "Find" , item
else:
current = current.get_next()
return "Not find"
def remove(self, item):
current = self.head
pro_node = None
found = False
while not found:
if current.get_data() == item:
found = True
else:
pro_node = current
current = current.get_next()
if pro_node == None: #第一個(gè)節(jié)點(diǎn)刪除
self.head = current.get_next()
else: #其他節(jié)點(diǎn)或者最后一個(gè)節(jié)點(diǎn)
pro_node.set_next_node(current.get_next())
mylist = UnorderList()
print(mylist.is_empty())
mylist.add(31)
mylist.add(30)
mylist.add(29)
print(mylist.size())
print(mylist.remove(30))
print(mylist.print_link_list())
True
3
None
[29, 31]
- 擴(kuò)展其他的功能append, insert, index, and pop
## 在最后一個(gè)節(jié)點(diǎn)后面增加一個(gè)節(jié)點(diǎn)品抽，記錄消耗的時(shí)間
def append(self, item):
#search最后一個(gè)點(diǎn)
current = self.head #current is <class '__main__.Node'>
new_node = Node(item)
while current.get_next() != None:
current = current.get_next()
else:
current.set_next_node(Node)
return None
import time
mylist = UnorderList()
mylist.add(31)
mylist.add(30)
mylist.add(29)
tic = time.time()
mylist.append(10)
toc = time.time()
print('time is'+ str(1000*(toc-tic))+ 'ms')
---------------------------------------------------------------------------
AttributeError Traceback (most recent call last)
<ipython-input-21-29193cbe3960> in <module>()
5 mylist.add(29)
6 tic = time.time()
----> 7 mylist.append(10)
8 toc = time.time()
9 print('time is'+ str(1000*(toc-tic))+ 'ms')
AttributeError: UnorderList instance has no attribute 'append'
def insert(self, item, position):
# initialize a node
new_node = Node(item)
current = self.head
print(current.get_data())
pos = 0
pro_node = None
find = False
while not find:
if pos != position:
pro_node = current
current = current.get_next()
pos += 1
if position == 0: # Can I improve it?
self.head = new_node
new_node.set_next_node(current)
find = True
else:
pro_node.set_next_node(new_node)
new_node.set_next_node(current.get_next())
find = True
def index(self, num):
current = self.head
pos = 0
Find = False
while not Find:
if current.get_data() == num:
return pos
else:
current = current.get_next()
pos += 1
def pop(self):
current = self.head
Find = False
pro_node = None
while not Find:
if current.get_next() != None:
pro_node = current
current = current.get_next()
print(pro_node.get_data())
else:
pro_node.set_next_node(None)
Find = True
- 有序鏈表，例如從小到大排列
class OrderList():
def __init__(self):
self.head = None
def add(self, item):
node = Node(item)
node.set_next_node(self.head)
self.head = node
def print_list(self):
current = self.head
list = []
while current != None:
item = current.get_data()
list.append(item)
current = current.get_next()
return list
def search(self, item):
current = self.head
while current != None:
if current.get_data() == item:
return 'Find it'
if current.get_data() > item:
return 'Sorry, you dont find it'
else:
print('serch:', current.get_data())
current = current.get_next()
return 'Dont find it'
def add_new_node(self, item):
current = self.head
pro_node = None
print(type(pro_node))
Find = False
new_node = Node(item)
pos = 0
while not Find :
if current.get_data() >= item:
if pos == 0: # 在位置0加入
self.head = new_node
new_node.set_next_node(current)
Find = True
else: #在中間其他位置加入|
pro_node.set_next_node(new_node)
new_node.set_next_node(current)
Find = True
else:
pro_node = current
print ('through:', current.get_data())
current = current.get_next()
pos += 1
if current.get_next() == None: #最后一個(gè)節(jié)點(diǎn)加入
current.set_next_node(new_node)
Find = True
order_list = OrderList()
order_list.add(11)
order_list.add(9)
order_list.add(6)
print('1:', order_list.print_list())
# search
print('2:', order_list.search(8))
#add
order_list.add_new_node(12)
print('3:',order_list.print_list())
('1:', [6, 9, 11])
('serch:', 6)
('2:', 'Sorry, you dont find it')
<type 'NoneType'>
('through:', 6)
('through:', 9)
('3:', [6, 9, 11, 12])
