5/28 每日一題(定義堆疊)

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

Implement the MyStack class:

• void push(int x) Pushes element x to the top of the stack.
• int pop() Removes the element on the top of the stack and returns it.
• int top() Returns the element on the top of the stack.
• boolean empty() Returns true if the stack is empty, false otherwise.

Notes:

• You must use only standard operations of a queue, which means that only push to back, peek/pop from front, size and is empty operations are valid.
• Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue's standard operations.

 

Example 1:

Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]

Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False

 

Constraints:

• 1 <= x <= 9
• At most 100 calls will be made to push, pop, top, and empty.
• All the calls to pop and top are valid.

 

Follow-up: Can you implement the stack using only one queue?

------並沒有成功完成stack using only one queue的要求

class MyStack:

    def __init__(self):

        self.item=list() #初始劃一個空列表

       

    def push(self, x: int) -> None:

        self.item.append(x) #將value放入堆疊中,保持後進先出的順序

       

    def pop(self) -> int:

        if not self.empty():    #如果不是空list,就彈出最後一項

            return self.item.pop()

       

    def top(self) -> int:

        return self.item[-1]  #返回最後一項的索引值

       

    def empty(self) -> bool:

        return len(self.item)==0  #檢查是否為空

       

# Your MyStack object will be instantiated and called as such:

# obj = MyStack()

# obj.push(x)

# param_2 = obj.pop()

# param_3 = obj.top()

# param_4 = obj.empty() ---------------------------------

class Stack:

    def __init__(self,Max_item):

        self.item=list()

        #初始item為沒有資料的空list

        self.Max_item=Max_item

        #設定容量限制

       

       

    def isFull(self):

        '''檢查容器是否已滿'''

        return len(self.item) >= self.Max_item

    def isEmpty(self):

        return len(self.item) == 0 #檢查是否為空堆棧

    def top(self):

        return self.item[-1] #返回最後一項

    def push(self,value):

        if not self.isFull():

            self.item.append(value)

    def pop(self):

        #先確認是否為空,不是就取出最後一項

        if not self.isEmpty():

            self.item.pop()

---------------修正後

from collections import deque
class MyStack:

    def __init__(self):
        self.item=deque() #初始化一個空列表
        

    def push(self, x: int) -> None:

        self.item.append(x)
        for i in range(len(self.item)-1):
            self.item.append(self.item.popleft())
        

    def pop(self) -> int:

        '''
        因為deque是雙端點,
        我們把新增的項目移動到首項,
        使用popleft()將前面的元素全部放在剛新增的後面,
        ex: q=[1,2,3,4] , q.popleft() 回傳1 , q變為[2,3,4]
         '''
        return self.item.popleft() #
        

    def top(self) -> int:

        return self.item[0]  #也就是首項,因為加入的項目已經放在第一項
        

    def empty(self) -> bool:
        return len(self.item)==0  #檢查是否為空
        

參考解答

----------------------------------------------

使用from collections import deque

該解決方案還使用了來自 collections 模塊的雙端隊列，但它沒有使用兩個隊列，而是只使用了一個隊列。訣竅是使用 push 操作將新添加的元素移動到隊列的前面，有效地使其成為堆棧的頂部元素。

以下是對代碼的逐步解釋：

1. 構造函數初始化一個空的雙端隊列。

2. push 操作將元素添加到雙端隊列的末尾，然後通過對雙端隊列中的所有其他元素進行出隊和入隊，將其移動到前面。這使得新添加的元素成為雙端隊列中的第一個元素，即堆棧的頂部。

3. pop 操作只是將 deque 中的第一個元素從隊列中取出，這是堆棧的頂部。

4. top 操作返回雙端隊列中的第一個元素，即棧頂。

5. empty 操作檢查雙端隊列是否為空並相應地返回 True 或 False。

該解決方案的推送操作時間複雜度為 O(n)，彈出、頂部和清空操作時間複雜度為 O(1)，其中 n 是雙端隊列的大小。存儲雙端隊列的空間複雜度為 O(n)。

複雜

• 時間複雜度：

• 空間複雜度：

代碼

from collections import deque

class MyStack:

    def __init__(self):
        self.q = deque()

    def push(self, x: int) -> None:
        self.q.append(x)
        # Move the newly added element to the front
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())

    def pop(self) -> int:
        return self.q.popleft()

    def top(self) -> int:
        return self.q[0]

    def empty(self) -> bool:
        return len(self.q) == 0

------------------------------------

ps 雙端柱列