堆疊和佇列 ||蟒蛇 ||資料結構和演算法-Python教學-PHP中文網

Stack and Queue || Python || Data Structures and Algorithms

堆疊

Stack - 它是一個儲存容器，支援依後進先出 (LIFO) 順序擷取。當檢索順序根本不重要時（例如處理批次作業時），堆疊可能是正確的容器。

例如，考慮自助餐廳中使用的一疊盤子：從盤子中取出盤子的順序與添加盤子的順序相反，因為只有頂部的盤子可以訪問.

堆疊上的 INSERT 操作通常稱為 PUSH，而不帶有元素參數的 DELETE 操作通常稱為 POP。

壓入 (x,s): 將項目 x 插入堆疊 s 的頂部。

Pop(s) : 傳回（並刪除）堆疊 s 的頂部項目。

儘管有保存期限的激勵，放入冰箱的食物通常也會以同樣的方式取出。從演算法上來說，後進先出往往發生在執行遞歸演算法的過程中。

堆疊的應用 -

函數呼叫：用於管理函數執行和遞歸。
撤銷操作： 追蹤編輯器中「撤銷/重做」的變更。
瀏覽器歷史記錄：儲存造訪過的頁面以進行回溯。
表達式解析： 計算並轉換數學表達式。
語法驗證： 符合程式碼中的括號或標籤。
記憶體管理：在程式執行期間管理呼叫堆疊。
DFS： 在圖演算法中實作深度優先搜尋。

使用陣列實作堆疊 -

push() - 將元素插入堆疊
pop() - 從堆疊中移除一個元素
top() - 傳回堆疊的頂部元素。
isEmpty() - 如果堆疊為空則傳回 true，否則傳回 false。

class Stack:
    def __init__(self):
        #Initializes an empty stack 
        self.stack = []

    def isEmpty(self) -> bool:
        #Returns True if the stack is empty, False otherwise.

        return len(self.stack) == 0

    def push(self, item) -> None:
        #Pushes an item onto the stack.
        self.stack.append(item)

    def pop(self):
        #Removes and returns the top item from the stack.
        if self.isEmpty():
            return None
        return self.stack.pop()

    def peek(self):
        #Returns the top item from the stack without removing it.
        if self.isEmpty():
            return None
        return self.stack[-1]

登入後複製

佇列

佇列 - 它是一個儲存容器，支援以先進先出（FIFO）順序擷取。我們將佇列上的 INSERT 運算稱為 ENQUEUE，將 DELETE 運算稱為 DEQUEUE。與堆疊操作 POP 一樣，DEQUEUE 不帶元素參數。堆疊和佇列是動態集合，其中透過 DELETE 操作從集合中刪除的元素是預先定義的。

入隊(x,q):將項目x插入隊列q的後面。

出隊（q）： 返回（並刪除）隊列 q 中最前面的項。

隊列有頭和尾。

當一個元素入隊時，它會在隊列尾部佔據一席之地，就像新到達的顧客在隊列末尾佔據一席之地一樣。
出隊的元素總是排在隊伍最前面的那個，就像排在隊伍最前面的顧客，他等待的時間最長。

隊列的應用 -

任務排程：依序管理CPU進程與作業。
BFS： 在圖中實現廣度優先搜尋。
列印佇列： 依序處理列印作業。
網路路由：緩衝資料包的傳輸。
呼叫中心：管理等待訂單中的客戶呼叫。
串流媒體：即時緩衝視訊或音訊串流。
輸入事件： 處理 GUI 系統中的鍵盤和滑鼠輸入。

使用陣列實作佇列-

enqueue() – 將元素插入佇列。
dequeue() – 從佇列中刪除元素。
peek() 或 front()- 取得隊列前端節點可用的資料元素，但不刪除它。
isEmpty() – 檢查佇列是否為空。

class Stack:
    def __init__(self):
        #Initializes an empty stack 
        self.stack = []

    def isEmpty(self) -> bool:
        #Returns True if the stack is empty, False otherwise.

        return len(self.stack) == 0

    def push(self, item) -> None:
        #Pushes an item onto the stack.
        self.stack.append(item)

    def pop(self):
        #Removes and returns the top item from the stack.
        if self.isEmpty():
            return None
        return self.stack.pop()

    def peek(self):
        #Returns the top item from the stack without removing it.
        if self.isEmpty():
            return None
        return self.stack[-1]

登入後複製

使用堆疊實作佇列 -

push(x) - 將所有元素從 stack1 移至堆疊 2 以反轉其順序，然後一次又一次將所有元素從 stack2 移回堆疊 1。
pop() - 從隊列前面移除元素並回傳它
peek() - 傳回佇列前面的元素
empty() - 如果佇列為空則傳回 true，否則傳回 false

class MyQueue:
    def __init__(self):
        # Store elements
        self.queue = []
        # A pointer to indicate the start position
        self.p_start = 0

    def enQueue(self, x):
        #Insert an element into the queue. 
        self.queue.append(x)
        return True # Return True if the operation is successful

    def deQueue(self):
        #Delete an element from the queue. 
        if self.isEmpty():
            return False
        self.p_start += 1
        return True #Return True if the operation is successful

    def Front(self):
        #Get the front item from the queue.
        if not self.isEmpty():
            return self.queue[self.p_start]
        return None  # Return None if the queue is empty

    def isEmpty(self):
        #Checks whether the queue is empty or not
        return self.p_start >= len(self.queue)

登入後複製

使用佇列實作堆疊 -

push(x) - 將新元素新增至第二個佇列，然後將所有元素從佇列 1 移至佇列 2 以維持堆疊順序 (LIFO) 並交換佇列。
pop() - 移除堆疊頂部元素並回傳
peek 或 top() - 傳回佇列前面的元素
empty() - 如果佇列為空則傳回 true，否則傳回 false

class MyQueue:

    def __init__(self):
        self.stack_1 = []  # Main stack for enqueue operations
        self.stack_2 = []  # Temporary stack for dequeue operations
        self.front = None

    # Pushes element x to the back of the queue.
    def push(self, x):

        # Move all elements from stack1 to stack 2 to reverse their order
        while self.stack_1:
            self.stack_2.append(self.stack_1.pop())
        self.stack_2.append(x)

        # Move all elements back from stack2 to stack 1 as a queue
        while self.stack_2:
            self.stack_1.append(self.stack_2.pop())

    # Removes the element from the front of the queue and returns it
    def pop(self):
        return self.stack_1.pop()

    # Returns the element at the front of the queue
    def peek(self):
        return self.stack_1[-1]

    # Returns true if the queue is empty, false otherwise
    def empty(self):
        return not self.stack_1

登入後複製

以上是堆疊和佇列 ||蟒蛇 ||資料結構和演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！