Ngăn xếp & Hàng đợi (Stack & Queue)
Nguyễn Mạnh Hiển Khoa Công nghệ thông tin hiennm@tlu.edu.vn
Ngăn xếp (stack)
• Một danh sách theo kiểu vào sau ra trước
LIFO (Last In First Out)
• Các thao tác chỉ xảy ra ở đỉnh ngăn xếp (topOfStack)
− push: Thêm phần tử − pop: Xóa phần tử − top: Truy nhập phần tử
ở đỉnh ngăn xếp ba thao tác đều chỉ mất thời gian hằng O(1)
Cài đặt ngăn xếp (1)
• Bằng danh sách liên kết đơn:
head
• Các thao tác:
− push: chèn vào đầu danh sách (push_front) − pop: xóa khỏi đầu danh sách (pop_front) − top: truy nhập phần tử ở đầu danh sách (front)
Cài đặt ngăn xếp (2)
• Cài đặt bằng mảng (theArray):
0 1 2 3 4 5 6 7 8
2
8
3
5
theArray
topOfStack = 3
• push: topOfStack++, theArray[topOfStack] = x • pop: topOfStack-- • top: return theArray[topOfStack] • Chú ý khi ngăn xếp rỗng: topOfStack = -1
Các ứng dụng của ngăn xếp
• Cân bằng ký hiệu trong mã nguồn, cân bằng
thẻ (trong một trang HTML)
• Định giá biểu thức hậu tố • Chuyển biểu thức từ trung tố sang hậu tố • Tổ chức các lời gọi hàm
Định giá biểu thức hậu tố
• Ví dụ: cần định giá biểu thức (trung tố) sau:
4,99 ∗ 1,06 + 5,99 + 6,99 ∗ 1,06
− Máy tính khoa học 18,69 đúng − Máy tính giản đơn (tính tuần tự từ trái sang
phải) 19,37 sai !
• Nếu tổ chức biểu thức dưới dạng hậu tố và
ứng dụng ngăn xếp sẽ tính đúng mà không cần biết độ ưu tiên của các toán tử
4,99 1,06 ∗ 5,99 + 6,99 1,06 ∗ +
Định giá: 6 5 2 3 + 8 ∗ + 3 + ∗
• Quy tắc:
− Gặp toán hạng đặt vào ngăn xếp − Gặp toán tử lấy hai toán hạng ra khỏi
ngăn xếp và áp dụng toán tử đặt kết quả trở lại ngăn xếp
Định giá: 6 5 2 3 + 8 ∗ + 3 + ∗
• Đặt bốn toán hạng đầu vào ngăn xếp
Định giá: 6 5 2 3 + 8 ∗ + 3 + ∗
• Đọc “+”, lấy 3 và 2 ra, cộng lại được 5 và đặt 5
vào ngăn xếp
Định giá: 6 5 2 3 + 8 ∗ + 3 + ∗
• Đặt 8 vào ngăn xếp
Định giá: 6 5 2 3 + 8 ∗ + 3 + ∗
• Đọc “∗”, lấy ra 8 và 5, nhân vào được 40 và đặt
vào ngăn xếp
Định giá: 6 5 2 3 + 8 ∗ + 3 + ∗
• Đọc “+”, lấy ra 40 và 5, cộng lại được 45 và đặt
vào ngăn xếp
Định giá: 6 5 2 3 + 8 ∗ + 3 + ∗
• Đặt 3 vào ngăn xếp
Định giá: 6 5 2 3 + 8 ∗ + 3 + ∗
• Đọc “+”, lấy ra 3 và 45, cộng lại được 48 và đặt
vào ngăn xếp
Định giá: 6 5 2 3 + 8 ∗ + 3 + ∗
• Đọc “∗”, lấy ra 48 và 6, nhân vào được 288 và
đặt vào ngăn xếp
• Thời gian định giá biểu thức hậu tố là O(n)
Chuyển biểu thức từ trung tố sang hậu tố Đọc thêm trong sách!
Ngăn xếp thời gian chạy
heap
• Môi trường thời gian chạy: − Bộ nhớ tĩnh (static):
• Mã thực thi • Các biến toàn cục
− Ngăn xếp (stack):
ngăn xếp
bộ nhớ tĩnh
• push cho mỗi lời gọi hàm • pop cho mỗi lần hàm trở về (return) • Các biến cục bộ
bộ nhớ chương trình
− Heap:
• Các khối nhớ được cấp phát động • new và delete
Hàng đợi (queue)
• Một danh sách theo kiểu vào trước ra trước
FIFO (First In First Out)
• Hai thao tác cơ bản:
− enqueue: chèn phần tử vào cuối danh sách − dequeue: xóa phần tử ở đầu danh sách
2
8
3
5
7
4
dequeue ở đầu
enqueue ở cuối
Cài đặt hàng đợi
• Như trường hợp ngăn xếp, có thể dùng mảng hoặc danh sách liên kết để cài đặt hàng đợi
theArray
currentSize = 4
• Các thao tác đều rất nhanh: O(1) • Ở đây chúng ta chỉ xem xét cài đặt bằng mảng:
Cài đặt hàng đợi bằng mảng
theArray
currentSize = 4
• enqueue: currentSize++, back++, theArray[back] = x • dequeue: currentSize--, front++ • Hàng đợi này chỉ chứa được 10 phần tử nhanh chóng đầy ! thực tế hàng đợi thường chỉ cần nhỏ nếu các thao tác enqueue và dequeue xảy ra thường xuyên
• Sau 10 lần enqueue, back ở vị trí cuối cùng không thể
enqueue thêm giải pháp mảng vòng tròn !
Mảng vòng tròn
Trạng thái ban đầu
Sau enqueue(1)
Mảng vòng tròn
Sau enqueue(3)
Sau dequeue (trả về 2)
Mảng vòng tròn
Sau dequeue (trả về 4)
Sau dequeue (trả về 1)
Mảng vòng tròn
Sau dequeue (trả về 3)
Chú ý: hàng đợi rỗng khi currentSize = 0
Ứng dụng của hàng đợi
• Xếp vào hàng đợi các tác vụ in ấn khi gửi tới
máy in
• Các cuộc gọi tới một công ty khi tất cả các
nhân viên trực đều bận
• Các gói tin gửi từ nguồn tới đích, được xếp vào
hàng đợi để chờ xử lý
