🚀️ Структура данных стека
- Линейная структура данных
- Работает по принципу «последним пришел — первым ушел» (LIFO).
- Последний элемент, вставленный в стек, удаляется первым.
🚀️ Операции стека:
- push: помещает элемент в верхнюю часть стека.
- pop: удалить и вернуть элемент с вершины стека.
- peek: возвращает элемент на вершину стека, не удаляя его.
- размер: возвращает общее количество элементов в стеке.
- isEmpty: проверяет, пуст ли стек.
- isFull: проверяет, заполнен ли стек.
🚀️ Реализация стека с использованием массивов
* Способ 1
stack = []
# append() function to push # element in the stack stack.append('a') stack.append('b') print('Initial stack:') print(stack)
# pop() fucntion to pop element from stack in LIFO order print('Elements poped from stack:') print(stack.pop()) print(stack.pop()) print('Stack after elements are poped:') print(stack) print(stack.pop())
Выход:
Initial stack: ['a', 'b'] Elements poped from stack: b a Stack after elements are poped: [] --------------------------------------------------------------------------- IndexError Traceback (most recent call last) /tmp/ipykernel_146307/3602183844.py in <module> 16 print('Stack after elements are poped:') 17 print(stack) ---> 18 print(stack.pop())
IndexError: pop from empty list
Недостатки
- По мере роста могут возникнуть проблемы со скоростью.
- Последняя команда вызовет IndexError после вызова .pop() для пустого стека.
* Способ 2
class Stack: def __init__(self): self.stack = []
# Use list append method to push element def push(self, val): self.stack.append(val) return val
# Stack is empty when stack size is 0 def isEmpty(self): return len(self.stack) == 0
# Use list pop method to remove element def pop(self): if self.isEmpty(): return ("No element in the Stack") else: return self.stack.pop()
# Use peek to look at the top of the stack def peek(self): if self.isEmpty(): return ("No element in the Stack") else: return self.stack[-1]
def print(self): return self.stack
stack = Stack() print("push:", stack.push(1)) print("push:", stack.push(2)) print(stack.print()) print("pop:", stack.pop()) print("pop:", stack.pop()) print("pop:", stack.pop()) print(stack.print()) print("peek:", stack.peek()) print("push:", stack.push(3)) print("push:", stack.push(4)) print(stack.print()) print("peek:", stack.peek())
Выход:
push: 1
push: 2
[1, 2]
pop: 2
pop: 1
pop: No element in the Stack
[]
peek: No element in the Stack
push: 3
push: 4
[3, 4]
peek: 4
* Способ 3 (Выполнение всех операций)
class Stack: def __init__(self, size): self.stack = [None] * size self.size = size self.top = -1
# Use list append method to push element def push(self, val): if self.isFull(): return ("Stack overflow") else: self.top += 1 self.stack[self.top] = val return val
# Stack is full when self.size is equal to top + 1 def isFull(self): return self.size == self.top + 1
# Stack is empty when top is -1 def isEmpty(self): return self.top == -1 # OR return self.size() == 0
# Use list pop method to remove element and set as None def pop(self): if self.isEmpty(): return ("Stack underflow") else: topVal = self.stack[self.top] self.stack[self.top] = None self.top -= 1 return topVal
# Use peek to look at the top of the stack def peek(self): if self.isEmpty(): return ("Stack empty") else: return self.stack[self.top]
# Stack size def size(self): return self.top + 1
def print(self): return self.stack
stack = Stack(3) print("push:", stack.push(1)) print("push:", stack.push(2)) print(stack.print()) print("pop:", stack.pop()) print("pop:", stack.pop()) print(stack.print()) print("pop:", stack.pop()) print("peek:", stack.peek()) print("push:", stack.push(3)) print("push:", stack.push(4)) print("push:", stack.push(5)) print("push:", stack.push(6)) print(stack.print()) print("peek:", stack.peek())
Выход:
push: 1
push: 2
[1, 2, None]
pop: 2
pop: 1
[None, None, None]
pop: Stack underflow
peek: Stack empty
push: 3
push: 4
push: 5
push: Stack overflow
[3, 4, 5]
peek: 5
🚀️ Реализация стека с использованием deque
from collections import deque stack = deque()
# append() function to push element in the stack stack.append(1) stack.append(2) stack.append(3) print(stack) # pop() fucntion to pop element from stack in LIFO order print("pop:", stack.pop()) # appendleft() function to push element in the left side of the stack stack.appendleft(11) print(stack) stack.append(12) print(stack) print("popleft:", stack.popleft()) print(stack) print("peek:", stack[-1]) print("pop:", stack.pop()) print(stack) print("popleft:", stack.popleft()) print(stack)
Выход:
deque([1, 2, 3])
pop: 3
deque([11, 1, 2])
deque([11, 1, 2, 12])
popleft: 11
deque([1, 2, 12])
peek: 12
pop: 12
deque([1, 2])
popleft: 1
deque([2])
🚀️ Реализация стека с помощью LifoQueue
from queue import LifoQueue
stack = LifoQueue(maxsize=3) # qsize() show the number of elements in the stack print("Size:",stack.qsize()) # put() function to push element in the stack stack.put(1) print("Full:", stack.full()) stack.put(2) stack.put(3) print("Full:", stack.full()) print("Size:", stack.qsize()) # get() fucntion to pop element from stack in LIFO order print("pop:",stack.get()) print("pop:",stack.get()) print("pop:",stack.get()) print("Empty:", stack.empty())
Выход:
Size: 0
Full: False
Full: True
Size: 3
pop: 3
pop: 2
pop: 1
Empty: True
Примечания
- И deque, и реализация LifoQueue выдают ошибку при извлечении элемента и поиске элемента peek из стека, если стек пуст.
🚀️ Реализация стека с помощью LinkedList
# node class class StackNode: def __init__(self, value): self.value = value self.next = None
class Stack: def __init__(self): self.head = None self.size = 0
# String representation of the stack def __str__(self): cur = self.head out = "" while cur: out += str(cur.value) + "->" cur = cur.next out += "None" return out
# Get the current size of the stack def getSize(self): return self.size
# Check if the stack is empty def isEmpty(self): return self.size == 0
# Get the top item of the stack def peek(self): if self.head is None: return "Empty stack" else: return self.head.value
# Push a value into the stack. def push(self, value): if self.head is None: self.head = StackNode(value) self.size += 1 else: node = StackNode(value) node.next = self.head self.head = node self.size += 1
# Remove a value from the stack and return. def pop(self): if self.head: remove = self.head self.head = self.head.next self.size -= 1 return remove.value else: return "Empty stack"
# Driver Code if __name__ == "__main__": stack = Stack() for i in range(1, 5): stack.push(i) print(f"Push: {i} | {stack}") print("Peek:", stack.peek()) for _ in range(1, 6): remove = stack.pop() print(f"Pop: {remove} | {stack}") print("Peek:", stack.peek())
Выход:
Push: 1 | 1->None
Push: 2 | 2->1->None
Push: 3 | 3->2->1->None
Push: 4 | 4->3->2->1->None
Peek: 4
Pop: 4 | 3->2->1->None
Pop: 3 | 2->1->None
Pop: 2 | 1->None
Pop: 1 | None
Pop: Empty stack | None
Peek: Empty stack
🚀️ Решение проблем
Решите не менее 50 задач, чтобы запачкать руки стеком.