###### tags: `LeetCode筆記`

# stack💻

[TOC]

Stack in Python can be implemented using the following ways:
============================================================

- list
- Collections.deque
- queue.LifoQueue
- **linked list:**

用list 實作 stack (不手刻)
--------------------

- 時間複雜度為 o(n)，因為python list這個資料結構的特性 本身就需要travel all element 去找到最尾端，但通常實作的時候都會用list 因為最方便，然後有個小技巧就是
1. list.pop()就會是取尾端的值=stack 概念
2. list.pop(0)就會是取list最前面=queue的概念

所以stack &queue可以用list做互換

# Python program to
# demonstrate stack implementation
# using list
 
stack = []
 
# append() function to push
# element in the stack
stack.append('a')
stack.append('b')
stack.append('c')
 
print('Initial stack')
print(stack)
 
# pop() function to pop
# element from stack in
# LIFO order
print('\\nElements popped from stack:')
print(stack.pop())
print(stack.pop())
print(stack.pop())
 
print('\\nStack after elements are popped:')
print(stack)
 
# uncommenting print(stack.pop())
# will cause an IndexError
# as the stack is now empty

---

用deque 去實作stack
---------------

> The same methods on deque as seen in the list are used, append() and pop().

- _deque_，全名double-ended queue (念：deck )
- deque =O(1) > list =o(n) 相較於list的時間複雜度 是更快的
- as deque provides an O(1) time complexity for append and pop operations as compared to list which provides O(n) time complexity.The same methods on deque as seen in the list are used, append() and pop().

from collections import deque
 
stack = deque() #建立deuqe物件 就可以開始用他的methond 了
 
# append() function to push
# element in the stack
stack.append('a')
stack.append('b')
stack.append('c')
 
print('Initial stack:')
print(stack)
 
# pop() function to pop
# element from stack in
# LIFO order
print('\\nElements popped from stack:')
print(stack.pop())
print(stack.pop())
print(stack.pop())
 
print('\\nStack after elements are popped:')
print(stack)
 
# uncommenting print(stack.pop())
# will cause an IndexError
# as the stack is now empty

---

用**queue module 實作stack**
-------------------------

queue module 有以下的funciton 可以去使用。
- **maxsize** – Number of items allowed in the queue.
- **empty()** – Return True if the queue is empty, False otherwise.
- **full()** – Return True if there are _maxsize_ items in the queue. If the queue was initialized with maxsize=0 (the default), then full() never returns True.
- **get()** – Remove and return an item from the queue. If the queue is empty, wait until an item is available.
- **get_nowait()** – Return an item if one is immediately available, else raise QueueEmpty.
- **put(item)** – Put an item into the queue. If the queue is full, wait until a free slot is available before adding the item.
- **put_nowait(item)** – Put an item into the queue without blocking. If no free slot is immediately available, raise QueueFull.
- **qsize()** – Return the number of items in the queue.
- Python3

---

# Python program to
# demonstrate stack implementation
# using queue module

from queue import LifoQueue

# Initializing a stack
stack = LifoQueue(maxsize=3)

# qsize() show the number of elements
# in the stack
print(stack.qsize())

# put() function to push
# element in the stack
stack.put('a')
stack.put('b')
stack.put('c')

print("Full: ", stack.full())
print("Size: ", stack.qsize())

# get() function to pop
# element from stack in
# LIFO order
print('\\nElements popped from the stack')
print(stack.get())
print(stack.get())
print(stack.get())

print("\\nEmpty: ", stack.empty())

用**linked list 實作 stack**
-------------------------

### 概念

linked list 的stack 的head 是指bucket 的頂端，也就是最後練加入的那個，就是top啦，所以你每次在push的時候，就是等於往鏈結串列的頭加，pop也是往鏈結串列的頭拔 。

- **getSize()**– Get the number of items in the stack.
- **isEmpty()** – Return True if the stack is empty, False otherwise.
- **peek()** – Return the top item in the stack. If the stack is empty, raise an exception.
- **push(value)** – Push a value into the head of the stack.
- **pop()** – Remove and return a value in the head of the stack. If the stack is empty, raise an exception.

#   Created by Elshad Karimov on 23/05/2020.
#   Copyright © 2020 AppMillers. All rights reserved.

class Node:
    def __init__(self, value = None):
        self.value = value
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None # 因為不會用到Tail 就不用設定了
    
    def __iter__(self):
        curNode = self.head
        while curNode:
            yield curNode
            curNode = curNode.next

class Stack:
    def __init__(self):
        self.LinkedList = LinkedList()
    
    def __str__(self):
        values = [str(x.value) for x in self.LinkedList]
        return '\\n'.join(values)
    
    def isEmpty(self):
        if self.LinkedList.head == None:
            return True
        else:
            return False

    def push(self, value):
        node = Node(value)
        node.next = self.LinkedList.head
        self.LinkedList.head = node
    
    def pop(self):
        if self.isEmpty():
            return "There is not any element in the stack"
        else:
            nodeValue = self.LinkedList.head.value
            self.LinkedList.head = self.LinkedList.head.next
            return nodeValue
    
    def peek(self):
        if self.isEmpty():
            return "There is not any element in the stack"
        else:
            nodeValue = self.LinkedList.head.value
            return nodeValue
    
    def delete(self):
        self.LinkedList.head = None
    

customStack = Stack()
customStack.push(1)
customStack.push(2)
customStack.push(3)

print(customStack.peek())