Bài giảng Cấu trúc dữ liệu và giải thuật: Ngăn xếp và hàng đợi - Nguyễn Mạnh Hiển

Chia sẻ: Hấp Hấp | Ngày: | Loại File: PDF | Số trang:33

Thêm vào BST

Báo xấu

73
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Cấu trúc dữ liệu và giải thuật: Ngăn xếp và hàng đợi" cung cấp cho người học các kiến thức về ngăn xếp, cài đặt ngăn xếp, các ứng dụng của ngăn xếp, định giá biểu thức hậu tố, ngăn xếp thời gian chạy, cài đặt hàng đợi,... Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu và giải thuật: Ngăn xếp và hàng đợi - Nguyễn Mạnh Hiển

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