棧
- 限制：僅允許對(duì)棧的一端操作行拢，并且元素先進(jìn)先出
- 功能：進(jìn)棧（push）渣慕、出棧（pop）、返回棧頂（peek）
- 實(shí)現(xiàn)思路
初始化：創(chuàng)建一個(gè)大小為initSize的數(shù)組arr（initSize必須大于0，否則拋出異常）眶根，棧內(nèi)元素個(gè)數(shù)為size = 0
進(jìn)棧：判斷size與arr大小（添加元素為obj）
a. size < len(arr)边琉，size += 1属百，arr[size] = obj
b. size == len(arr)， 拋出異常
出棧：判斷size大小
a. size > 0 艺骂，size -= 1诸老， 返回arr[size]（元素個(gè)數(shù)為size，由于元素位置是從0號(hào)位開始钳恕，所以size的大小剛好是棧頂位置）
b. size == 0别伏，拋出異常
返回棧頂：判斷size大小
a. size > 0，返回arr[size - 1]
b. size == 0忧额， 返回null
- 代碼實(shí)現(xiàn)
class Stack():
def __init__(self, len):
self.len = len
self.arr = [0,]*len
self.size = 0
def push(self, obj):
if(self.size == self.len):
print('棧已滿')
return
self.arr[self.size] = obj
self.size += 1
def pop(self):
if(self.size == 0):
print('棧已空')
return
self.size -= 1
return self.arr[self.size]
def peek(self):
if(self.size == 0):
print('棧已空')
return
return self.arr[self.size - 1]
隊(duì)列
- 限制：只能在隊(duì)尾添加元素厘肮，在隊(duì)頭彈出元素，元素先進(jìn)先出
- 功能：進(jìn)隊(duì)（push）出隊(duì)（pop）
- 實(shí)現(xiàn)思路
初始化：創(chuàng)建一個(gè)長度為len的數(shù)組arr睦番，隊(duì)頭位置為head = 0类茂，隊(duì)尾位置為rear = 0，元素個(gè)數(shù)為size
進(jìn)隊(duì)：判斷size大型邢（添加元素為obj）
a. size < len巩检，arr[rear] = obj， rear = (rear + 1) % len 示启， size += 1
b. size == len兢哭， 拋出異常
出隊(duì)：判斷size大小
a. size > 0， head = (head + 1) % len夫嗓，size -= 1迟螺，返回arr[head - 1]
b. size == 0冲秽，拋出異常
- 代碼實(shí)現(xiàn)
class Queue():
def __init__(self, len):
self.len = len
self.arr = [0]*len
self.head = 0
self.rear = 0
self.size = 0
def push(self, obj):
if(self.size == self.len):
print('隊(duì)列已滿')
return
self.arr[self.rear] = obj
self.size += 1
self.rear += 1
if(self.rear == self.len):
self.rear = 0
def pop(self):
if(self.size == 0):
print('隊(duì)列已空')
return
self.size -= 1
self.head += 1
if(self.head == self.len):
self.head = 0
return self.arr[self.head - 1]
棧實(shí)現(xiàn)隊(duì)列
- 含義：棧（后進(jìn)先出）實(shí)現(xiàn)先進(jìn)先出
- 功能：進(jìn)隊(duì)（push）出隊(duì)（pop）
- 實(shí)現(xiàn)思路
初始化：創(chuàng)建兩個(gè)長度為len的數(shù)組push_arr以及pop_arr，其中矩父，元素進(jìn)隊(duì)push到push_arr中锉桑，出隊(duì)從pop_arr中popl，push_arr元素個(gè)數(shù)為push_size=0窍株，pop_arr元素個(gè)數(shù)為pop_size=0
進(jìn)隊(duì)：判斷push_size + pop_size大忻裰帷（添加元素為obj）
a. push_size + pop_size < len，push_arr[push_size] = obj夹姥，push_size +=1
b. push_size + pop_size == len杉武， 拋出異常
出隊(duì)：分別判斷判斷push_size、pop_size大小
a. pop_size > 0辙售，pop_size -= 1轻抱， 返回arr[size]
b. pop_size < 0，push_size > 0旦部， 將push_arr所有元素逐一彈出祈搜，放進(jìn)pop_arr中，然后再進(jìn)行出隊(duì)操作
c. pop_size < 0士八，push_size < 0容燕，拋出異常
備注：為什么要等pop_arr棧空后才將push_arr棧中元素彈進(jìn)pop_arr棧婚度，并且要一次性彈進(jìn)蘸秘？防止后進(jìn)隊(duì)元素在pop_arr棧頂位置，導(dǎo)致出棧順序出錯(cuò)蝗茁。
- 代碼實(shí)現(xiàn)
# 以下為將push_arr所有元素逐一彈出醋虏，放進(jìn)pop_arr
def transfer():
while(self.push_size > 0):
self.push_size -= 1
self.pop_arr[self.pop_size] = self.push_arr[self.push_size]
self.pop_size += 1
隊(duì)列實(shí)現(xiàn)棧
- 含義：隊(duì)列（先進(jìn)先出）實(shí)現(xiàn)后進(jìn)先出功能
- 功能：進(jìn)隊(duì)（push）出隊(duì)（pop）返回棧頂（peek）
- 實(shí)現(xiàn)思路
初始化：創(chuàng)建一個(gè)長度為len的數(shù)組arr，隊(duì)列頭部為head = 0哮翘，尾部為rear = 0颈嚼，元素個(gè)數(shù)為size = 0，出棧位置pop_place
進(jìn)棧：判斷size的大小(添加元素為obj)
a. size < len饭寺，arr[rear ] = obj阻课，size += 1 如果rear + 1 < len，則rear += 1艰匙，否則rear = 0
b. size == 0限煞，拋出異常
出棧：判斷size大小
a. size > 0，pop_place = rear - 1(記錄隊(duì)尾元即彈出元素位置)员凝，當(dāng)head < pop_place時(shí)晰骑，隊(duì)列元素逐一出隊(duì)，并且再次進(jìn)隊(duì)，當(dāng)head == pop_place時(shí)硕舆，head = head + 1 if head + 1 < len else 0， 返回arr[head - 1]
b. size ==0骤公，拋出異常
返回棧頂：判斷size大小
a. size > 0抚官，返回arr[rear]
b. size ==0，拋出異常
- 代碼實(shí)現(xiàn)
def pop(self):
if(self.size == 0):
print('棧已空')
return
self.pop_place = self.rear - 1
while(self.head != self.pop_place):
self.head = self.head + 1 if self.head + 1 < self.len else 0
self.arr[self.rear] = self.arr[self.head - 1]
self.rear = self.rear + 1 if self.rear + 1 < self.len else 0
self.head = self.head + 1 if self.head + 1 < self.len else 0
return self.arr[self.head - 1]
