【數據結構】棧

什么是棧

LIFO：后進者先出，先進者后出

“操作受限”的線性表，只允許在一端插入和刪除數據。

理解：一摞疊在一起的盤子。我們平時放盤子的時候，都是從下往上一個一個放；取的時候，我們也是從上往下一個一個地依次取，不能從中間任意抽出。

棧操作

Stack() 創建一個空的新棧。 它不需要參數，并返回一個空棧。

push(item)將一個新項添加到棧的頂部。它需要 item 做參數并不返回任何內容。

pop() 從棧中刪除頂部項。它不需要參數并返回 item 。棧被修改。

peek() 從棧返回頂部項，但不會刪除它。不需要參數。 不修改棧。

is_empty() 測試棧是否為空。不需要參數，并返回布爾值。

size() 返回棧中的 item 數量。不需要參數，并返回一個整數。

python實現

1.利用列表自定義棧

class Stack(object): #底層數據結構為列表 def __init__(self): self.stack = [] def push(self, value): # 入棧 self.stack.append(value) def pop(self): # 彈出棧頂元素 if self.stack: self.stack.pop() else: raise LookupError('stack is empty!') def is_empty(self): # 判斷棧是否為空 return bool(self.stack) def peek(self): # 獲取目前stack中最新的元素 return self.stack[-1] def size(self): # 返回棧的元素個數 return len(self.stack)

2.利用鏈表自定義棧

class Node(object): """節點的實現""" def __init__(self,elem): self.elem = elem self.next = None class Stack(object): def __init__(self): """ 初始化，鏈表頭head""" self.__head = None def is_empty(self): """ 初始化，鏈表頭head""" return self.__head is None def push(self,item): """ 壓棧""" node = Node(item) node.next = self.__head self.__head = node def pop(self): """ 彈棧""" if self.is_empty(): return else: p = self.__head self.__head = p.next return p.elem

3.queue模塊

內部也是用的列表，方法繼承自queue，支持線程安全

（這里不做多講解，【python】queue模塊已講解）

import queue stack = queue.LifoQueue() # 內部使用列表;

棧的實際應用

括號匹配問題

給定一個只包括?(，)，{，}，[，]?的字符串，判斷字符串是否有效。有效字符串需滿足：1、左括號必須用相同類型的右括號閉合。2、左括號必須以正確的順序閉合。注意空字符串可被認為是有效字符串。

def brace_match(s): match = {'}':'{', ')':'(', ']':'['} stack = Stack() for ch in s: if ch in ['(', '[', '{']: stack.push(ch) else: if stack.is_empty(): return False elif stack.peek() == match[ch]: stack.pop() else: return False return True if stack.is_empty() else False

迷宮問題

返回從入口發到出口的迷宮路徑

# 迷宮問題：深度優先搜索 maze = [ [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 0, 1, 1, 1, 1, 1, 1, 1, 1], [1, 0, 1, 0, 0, 0, 0, 0, 0, 1], [1, 0, 1, 0, 1, 0, 1, 1, 0, 1], [1, 0, 1, 0, 1, 0, 1, 1, 0, 1], [1, 0, 0, 0, 1, 0, 0, 1, 0, 1], [1, 1, 1, 0, 1, 1, 1, 1, 0, 1], [1, 1, 1, 0, 1, 1, 0, 0, 0, 1], [1, 1, 1, 1, 1, 1, 1, 1, 0, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], ] dirs = [ lambda x, y: (x+1, y), lambda x, y: (x, y+1), lambda x, y: (x-1, y), lambda x, y: (x, y-1), ] def maze_path(x1,y1,x2,y2): stack = [] stack.append((x1, y1)) while len(stack)>0: curNode = stack[-1] if curNode == (x2,y2): print(stack) return True for dir in dirs: nextNode = dir(curNode[0], curNode[1]) if maze[nextNode[0]][nextNode[1]] == 0: stack.append(nextNode) maze[nextNode[0]][nextNode[1]] = 2 break else: maze[nextNode[0]][nextNode[1]] = 2 # 表示走過 stack.pop() else: return False maze_path(1,1,8,8)

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。