Skip to main content

Stack & Queue

Stack

LIFO (Last In First Out)

 0  1  2
[4, 7, 8]

| 8 | 2
| 7 | 1
|_4_| 0

Declare

s = []

Add elements

s = []
s.push(1)

Delete last (most above) element

value = s.pop();

Get value of last (most above) element

value = s[-1]

Get stack's size

n = len(s)

Check if stack is empty

if len(s) == 0:
# statement

Swap 2 stacks

s1, s2 = s2, s1

Queue

FIFO (First In First Out)

   _________
=> 4 3 2 1 =>
---------

Một lợi thế queue so với stack là về mặt bộ nhớ. Queue có thể implement bằng linked list nên nằm rời rạc ở các vùng nhớ được \rightarrow tận dụng được vùng nhớ phân mảnh.

Declare

# There are many types like LIFO Queue, Queue, Priority Queue. So we need to
# import correct one.

# Python 2
import Queue
q = Queue.Queue()

# Python 3
import queue
q = queue.Queue()

# My favorite, only import what you need
from queue import Queue
q = Queue()

EnQueue (add element)

q.put(1)

Deque (delete element)

Delete here means remove the first element. Since queue is FIFO, we can only delete the first element. So we don't have pop() method like stack (get the last element).

value = q.get()

Get value of the first element

# Trick with Python, since queue is implemented using list.
value = q.queue[0]

Get queue's size

n = q.qsize()

Check if queue is empty

if q.empty():
# statement

Swap 2 queues

q1, q2 = q2, q1

Deque (double ended queue)

Deque thì thay vì như queue là thêm cuối lấy đầu thì dequeue có thể thêm lấy ở cả 2 đầu. Có thể nói là sự kết hợp giữa stack và queue.

Compare complexity

Ứng dụng của stack và queue

Lưu trữ và cơ chế hoạt động. Cơ chế hoạt động của đệ quy là stack (gọi dần xuống dưới, tới dưới cùng làm xong thì quay ngược lại)

\rightarrow Khử đệ quy thì dùng stack để lưu trữ function, info (vì dùng đệ quy phải tốn chi phí tạo lại function).