棧

棧（stack），有些地方稱為堆棧，是一種容器，可存入數據元素、訪問元素、刪除元素，它的特點在于只能允許在容器的一端（稱為棧頂端指標，英語：top）進行加入數據（英語：push）和輸出數據（英語：pop）的運算。沒有了位置概念，保證任何時候可以訪問、刪除的元素都是此前最后存入的那個元素，確定了一種默認的訪問順序。

由于棧數據結構只允許在一端進行操作，因而按照后進先出（LIFO, Last In First Out）的原理運作。

棧結構實現

棧可以用順序表實現，也可以用鏈表實現。

棧的操作

• Stack() 創建一個新的空棧
• push(item) 添加一個新的元素item到棧頂
• pop() 彈出棧頂元素
• peek() 返回棧頂元素
• is_empty() 判斷棧是否為空
• size() 返回棧的元素個數

class Stack(object):"""棧"""def __init__(self):self.items = []def is_empty(self):"""判斷是否為空"""return self.items == []def push(self, item):"""加入元素"""self.items.append(item)def pop(self):"""彈出元素"""return self.items.pop()def peek(self):"""返回棧頂元素"""return self.items[len(self.items)-1]def size(self):"""返回棧的大小"""return len(self.items)if __name__ == "__main__":stack = Stack()stack.push("hello")stack.push("world")stack.push("itcast")print stack.size()print stack.peek()print stack.pop()print stack.pop()print stack.pop()

隊列

隊列（queue）是只允許在一端進行插入操作，而在另一端進行刪除操作的線性表。

隊列是一種先進先出的（First In First Out）的線性表，簡稱FIFO。允許插入的一端為隊尾，允許刪除的一端為隊頭。隊列不允許在中間部位進行操作！假設隊列是q=（a1，a2，……，an），那么a1就是隊頭元素，而an是隊尾元素。這樣我們就可以刪除時，總是從a1開始，而插入時，總是在隊列最后。這也比較符合我們通常生活中的習慣，排在第一個的優先出列，最后來的當然排在隊伍最后。

隊列的實現

同棧一樣，隊列也可以用順序表或者鏈表實現。

操作

• Queue() 創建一個空的隊列
• enqueue(item) 往隊列中添加一個item元素
• dequeue() 從隊列頭部刪除一個元素
• is_empty() 判斷一個隊列是否為空
• size() 返回隊列的大小

class Queue(object):"""隊列"""def __init__(self):self.items = []def is_empty(self):return self.items == []def enqueue(self, item):"""進隊列"""self.items.insert(0,item)def dequeue(self):"""出隊列"""return self.items.pop()def size(self):"""返回大小"""return len(self.items)if __name__ == "__main__":q = Queue()q.enqueue("hello")q.enqueue("world")q.enqueue("itcast")print q.size()print q.dequeue()print q.dequeue()print q.dequeue()

隊列的應用

1.windows中的消息機制就是通過隊列來實現的
2.操作系統的進程、作業管理中的先進先出服務
3.異步消息機制，如celery異步任務

約瑟夫斯問題（熱土豆游戲）

這場比賽是一個現代的相當著名的約瑟夫斯問題。基于對第一世紀著名歷史學家Flavius Josephus的傳說，故事說的是，在對羅馬猶太人起義，約瑟夫斯和39名戰友頂住了羅馬人在一個山洞里。隨著失敗迫在眉睫，他們決定，他們寧愿死也不愿做羅馬人的奴隸。他們安排自己在一個圓圈里。一個人被劃為第一號，順時針方向，每第七個男人就殺了一個。約瑟夫斯，根據傳說，是一個有成就的數學家。他立刻想出了他應該坐的地方是最后一個去的地方。當時間來了，而不是殺死自己，他加入了羅馬的一邊。

#打印機任務（拓展不要求會）

圖書館中有一臺打印機，打印機有兩種工作模式：每分鐘10頁（但打印質量較低），每分鐘5頁（打印效果較好）。打印機一次只能處理一個任務，其余任務可排隊等候。
每個小時最多有10位學生在圖書館，他們在一小時終最多提交2次打印任務，每個打印任務的頁數為1至20頁不等。
問：綜合分析兩種打印模式，分析學生的平均等待打印時間和是否能在1小時內完成所有學生提交的打印任務

雙端隊列應用

一個有趣的問題，可以很容易地解決了使用隊列的數據結構是典型的回文問題。回文數是一個字符串，讀取相同的向前和向后的，例如,"sbbs"我們想構造一個算法，輸入一個字符串是否回文。這個問題的解決方案將使用一個隊列來存儲字符串的字符。我們將從左到右弦和添加的每個字符的雙端隊列后。在這一點上，deque將會表現的非常像一個普通的隊列。然而，我們現在可以利用該容器的雙重功能。該容器前將字符串和該容器后的第一個字符將舉行的最后一個字符

雙端隊列

雙端隊列（deque，全名double-ended queue），是一種具有隊列和棧的性質的數據結構。

雙端隊列中的元素可以從兩端彈出，其限定插入和刪除操作在表的兩端進行。雙端隊列可以在隊列任意一端入隊和出隊。

操作

• Deque() 創建一個空的雙端隊列
• add_front(item) 從隊頭加入一個item元素
• add_rear(item) 從隊尾加入一個item元素
• remove_front() 從隊頭刪除一個item元素
• remove_rear() 從隊尾刪除一個item元素
• is_empty() 判斷雙端隊列是否為空
• size() 返回隊列的大小

實現

class Deque(object):"""雙端隊列"""def __init__(self):self.items = []def is_empty(self):"""判斷隊列是否為空"""return self.items == []def add_front(self, item):"""在隊頭添加元素"""self.items.insert(0,item)def add_rear(self, item):"""在隊尾添加元素"""self.items.append(item)def remove_front(self):"""從隊頭刪除元素"""return self.items.pop(0)def remove_rear(self):"""從隊尾刪除元素"""return self.items.pop()def size(self):"""返回隊列大小"""return len(self.items)if __name__ == "__main__":deque = Deque()deque.add_front(1)deque.add_front(2)deque.add_rear(3)deque.add_rear(4)print deque.size()print deque.remove_front()print deque.remove_front()print deque.remove_rear()print deque.remove_rear()

企業面試題

用兩個棧來實現一個隊列，完成隊列的Push和Pop操作。 隊列中的元素為int類型

class Solution:def __init__(self):self.stack1 = []self.stack2 = []def push(self,node):self.stack1.append(node)def pop(self):if self.stack2 == []:while self.stack1:self.stack2.append(self.stack1.pop())return self.stack2.pop()return self.stack2.pop()

兩個隊列實現一個棧

思路:

進棧：元素入隊列A

出棧：判斷如果隊列A只有一個元素，則直接出隊。否則，把隊A中的元素出隊并入隊B，直到隊A中只有一個元素，再直接出隊。為了下一次繼續操作，互換隊A和隊B。

class Solution:def __init__(self):self.queue1 = []self.queue2 = []def add(self, node):# write code hereself.queue1.append(node)def dele(self):# return xxif self.queue1 == []:return Nonewhile len(self.queue1) != 1:self.queue2.append(self.queue1.pop(0))self.queue1,self.queue2 = self.queue2,self.queue1##交換是為了下一次的popreturn self.queue2.pop()

總結

以上是生活随笔為你收集整理的Python--栈和队列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。