1.list實(shí)現(xiàn) enqueue append() dequeue pop(0) 或 enqueue insert(0,item) dequeue pop()
MAX_SIZE = 100
class MyQueue1(object):
"""模擬隊(duì)列"""
def __init__(self):
self.items = []
self.size = 0
def is_empty(self):
"""判斷是否為空"""
return self.size == 0
def size(self):
"""返回隊(duì)列的大小"""
return self.size
def enqueue(self, item):
"""入隊(duì)(加入元素)"""
self.items.append(item)
self.size += 1
def dequeue(self):
"""出隊(duì)(彈出元素)"""
if self.size < MAX_SIZE and self.size >= 0:
self.size -= 1
return self.items.pop(0)
else:
print("隊(duì)列已經(jīng)為空")
return None
def getFront(self):
if not self.is_empty():
return self.items[0]
else:
return None
def getRear(self):
if not self.is_empty():
return self.items[self.size-1]
else:
return None
def __str__(self):
return str(self.items)
class MyQueue2(object):
"""模擬隊(duì)列"""
def __init__(self):
self.items = []
self.size = 0
def is_empty(self):
"""判斷是否為空"""
return self.size == 0
def size(self):
"""返回隊(duì)列的大小"""
if self.size <= MAX_SIZE:
return self.size
def enqueue(self, item):
"""入隊(duì)(加入元素)"""
if self.size <= MAX_SIZE:
self.items.insert(0, item)
self.size += 1
def dequeue(self):
"""出隊(duì)(彈出元素)"""
if self.size > 0 and self.size <= MAX_SIZE:
self.size -= 1
return self.items.pop()
else:
print("隊(duì)列已經(jīng)為空")
return None
def getFront(self):
"""返回隊(duì)頭元素"""
if not self.is_empty():
return self.items[0]
else:
return None
def getRear(self):
if not self.is_empty():
return self.items[self.size-1]
else:
return None
def __str__(self):
return str(self.items)
def test(obj):
i = obj()
for x in range(0,6):
i.enqueue(x)
print(i)
i.dequeue()
print(i, i.getFront(), i.getRear(), i.size)
if __name__ == "__main__":
test(MyQueue1)
test(MyQueue2)
運(yùn)行結(jié)果：
2.鏈隊(duì) 前文已介紹
首尾指針實(shí)現(xiàn)
鏈隊(duì) 首尾指針實(shí)現(xiàn)鏈隊(duì)
class Node():
def __init__(self, value=None):
self.value = value
self.next = None
class StcakQueue():
def __init__(self):
self.front = Node()
self.rear = Node()
self.size = 0
def enqueue(self, value):
node = Node(value)
if self.size == 0:
self.front = node
self.rear = node
else:
self.rear.next = node
self.rear = node
self.size += 1
def dequeue(self):
if self.size == 0:
raise Exception('queue is empty')
else:
temp = self.front.value
self.front = self.front.next
self.size -= 1
return temp
def is_empty(self):
if self.size == 0 :
return False
else:
return True
def top(self):
if self.size == 0 :
raise LookupError('queue is empty')
else:
return self.front.value
def size(self):
return self.size
def __str__(self):
if self.size == 0:
return None
else:
stack_list = []
temp, count = self.front, self.size
while count > 0 :
stack_list.append(temp.value)
temp = temp.next
count -= 1
return str(stack_list)
if __name__ == "__main__":
i = StcakQueue()
for x in range(0,6):
i.enqueue(x)
print(i)
i.dequeue()
print(i, i.size)
尾插有頭結(jié)點(diǎn)實(shí)現(xiàn)鏈隊(duì)
鏈隊(duì) 尾插法 有頭結(jié)點(diǎn)實(shí)現(xiàn)鏈隊(duì)文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-801808.html
class Node(): #結(jié)點(diǎn)類(lèi)
def __init__(self,elem):
self.elem = elem # 數(shù)據(jù)域，用來(lái)存放數(shù)據(jù)元素
self.next = None # 指針域，指向下一個(gè)結(jié)點(diǎn)
def __str__(self):
return str(self.elem)
class Queue(): # 隊(duì)列
def __init__(self): # 隊(duì)列初始化
self.head = None # 構(gòu)造私有頭結(jié)點(diǎn)
def is_empty(self):
return self.head == None
def enqueue(self,elem): # 進(jìn)隊(duì)列（正常向后填元素）
node = Node(elem) # 創(chuàng)建新結(jié)點(diǎn)
if self.is_empty(): # 如果為空, 新建head結(jié)點(diǎn)
self.head = Node
self.head.next = node
node = self.head
else:
current = self.head
while current.next is not None:
current = current.next
current.next = node
def dequeue(self): # 出隊(duì)列（頭出）
if not self.is_empty():
current = self.head.next
self.head.next = self.head.next.next
return current.elem
else:
raise IndexError('pop from a empty stack')
def size(self):
current = self.head
count = 0
while current.next is not None:
current = current.next
count += 1
return count
def __repr__(self):
stack_list = []
current = self.head
while current.next is not None:
stack_list.append(current.next.elem)
current = current.next
return str(stack_list)
__str__ = __repr__
if __name__ == "__main__":
i = Queue()
for x in range(0, 6):
i.enqueue(x)
print(i)
i.dequeue()
print(i, i.size())
3.兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列 O(1)
兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列 list棧文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-801808.html
class CQueue:
def __init__(self):
self.stack1 = []
self.stack2 = []
def append_tail(self, elem):
self.stack1.append(elem)
def delete_head(self):
if not self.stack2:
if self.stack1:
while self.stack1:
elem = self.stack1.pop()
self.stack2.append(elem)
else:
raise Exception("Queue is empty.")
elem = self.stack2.pop()
return elem
#學(xué)習(xí)中遇到問(wèn)題沒(méi)人解答？小編創(chuàng)建了一個(gè)Python學(xué)習(xí)交流群：711312441
def unitest():
# Create an instance of class CQueue
que = CQueue()
print("Push 1, 2, 3 successively into CQueue.")
for i in range(1, 4):
que.append_tail(i)
print("Pop the head of the queue:", que.delete_head())
print("Pop the head of the queue:", que.delete_head())
print("Push 4, 5, 6 successively into CQueue.")
for i in range(4, 7):
que.append_tail(i)
# Pop the rest elements in the queue
for i in range(4):
print("Pop the head of the queue:", que.delete_head())
if __name__ == '__main__':
unitest()
到了這里，關(guān)于python數(shù)據(jù)結(jié)構(gòu)中實(shí)現(xiàn)隊(duì)列的幾種方法的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
