intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

STACK & QUEUE NGĂN XẾP & HÀNG ĐỢI

Chia sẻ: Batman_1 Batman_1 | Ngày: | Loại File: PPT | Số trang:58

Thêm vào BST
Báo xấu
111
lượt xem 19
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

• Trình bày khái niệm Stack và Queue • Minh họa các ứng dụng • Các phương pháp xây dựng Stack và Queue dựa trên nh ững cấu trúc dữ liệu đã

Chủ đề:

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

Lưu

Nội dung Text: STACK & QUEUE NGĂN XẾP & HÀNG ĐỢI

  1. STACK & QUEUE NGĂN XẾP & HÀNG ĐỢI
  2. Nội dung • Trình bày khái niệm Stack và Queue • Minh họa các ứng dụng • Các phương pháp xây dựng Stack và Queue dựa trên nh ững cấu trúc dữ liệu đã biết •Stack •Queue –Ví dụ –Ví dụ –Định nghĩa –Định nghĩa –Các thao tác cơ bản –Các thao tác cơ bản –Xây dựng Stack –Xây dựng Queue
  3. Ngăn xếp (Stack) Chồng khay Chồng tiền Chồng sách Chồng áo sơ cà phê xu mi Các ví dụ về Ngăn xếp
  4. Ngăn xếp - Định nghĩa • Stack là 1 cấu trúc: • gồm nhiều phần tử có thứ tự • hoạt động theo cơ chế “Vào sau – Ra trước” (LIFO – Last In, First Out) Đỉnh ngăn xếp
  5. Ngăn xếp - Định nghĩa Push Pop • Các thao tác cơ bản trên Stack: • InitStack: khởi tạo Stack rỗng • IsEmpty: kiểm tra Stack rỗng ? • IsFull: kiểm tra Stack đầy ? • Push: thêm 1 phần tử vào đỉnh Stack, có th ể làm Stack đầy • Pop: lấy ra 1 phần tử từ đỉnh Stack, có thể làm Stack rỗng • StackTop: kiểm tra phần tử đầu Stack
  6. Ngăn xếp • Minh họa thao tác Push Data Top
  7. Ngăn xếp • Minh họa thao tác Pop Data Top
  8. Ngăn xếp • Minh họa thao tác StackTop  Ngăn xếp không thay đổi ? Data ? Top
  9. Ngăn xếp • Có hai cách để xây dựng ngăn xếp • Sử dụng mảng 1 chiều • Sử dụng danh sách liên kết đơn Mảng 1 chiều Danh sách liên kết đơn - Viết chương trình dễ Phức tạp khi triển khai chương trình dàng, nhanh chóng - Bị hạn chế do số lượng Không bị cố định về số phần tử cố định phần tử, phụ thuộc vào bộ nhớ - Tốn chi phí tái cấp phát và sao chép vùng nhớ nếu sử dụng mảng động
  10. Ngăn xếp – Sử dụng mảng Xây dựng ngăn xếp bằng mảng 1 chiều Top 6 3 StkTop 9 Đỉnh ngăn xếp Stack 9 3 6 0 1 2 3 4 5 6 7 8 9 Ngăn xếp có 3 phần tử
  11. Ngăn xếp – Sử dụng mảng • // Giả sử Stack chứa các phần tử kiểu nguyên • // (int) - Khai báo cấu trúc Stack struct STACK { int* StkArray; // mảng chứa các phần tử int StkMax; // số phần tử tối đa int StkTop; // vị trí đỉnh Stack };
  12. Ngăn xếp – Sử dụng mảng • Thao tác “Khởi tạo Stack rỗng” int InitStack(STACK& s, int MaxItems) { s.StkArray = new int[MaxItems]; if (s.StkArray == NULL) return 0; // Không cấp phát được bộ nhớ s.StkMax = MaxItems; s.StkTop = -1; // chưa có phần tử nào trong Stack return 1; // khởi tạo thành công }
  13. Ngăn xếp – Sử dụng mảng • Thao tác “Kiểm tra Stack rỗng” int IsEmpty(const STACK &s) { if (s.StkTop==-1) return 1; // Stack rỗng return 0; // Stack không rỗng }
  14. Ngăn xếp – Sử dụng mảng • Thao tác “Kiểm tra Stack đầy” int IsFull(const STACK &s) { if (s.StkTop==s.StkMax-1) return 1; // Stack đầy return 0; // Stack chưa đầy }
  15. Ngăn xếp – Sử dụng mảng • Thao tác “Push”: thêm một phần tử vào đỉnh Stack int Push (STACK& s, int newitem) { if (IsFull(s)) return 0; // stack đầy, không thể thêm s.StkTop++; s.StkArray[s.StkTop] = newitem; return 1; // thêm thành công }
  16. Ngăn xếp – Sử dụng mảng • Thao tác “Pop”: lấy ra 1 phần tử từ đỉnh Stack int Pop(STACK& s, int& outitem) { if (IsEmpty(s)) return 0; // Stack rỗng, không lấy ra được outitem = s.StkArray[s.StkTop]; s.StkTop--; return 1; // lấy ra thành công }
  17. Ngăn xếp – Sử dụng mảng • Thao tác “StackTop”: kiểm tra 1 phần tử ở đỉnh Stack, không làm thay đổi Stack int StackTop(const STACK s, int& outitem) { if (IsEmpty(s)) return 0; // Stack rỗng, không lấy ra được outitem = s.StkArray[s.StkTop]; return 1; // lấy ra thành công }
  18. Ngăn xếp – Ví dụ ứng dụng • Kiểm tra sự tương ứng của các cặp ngoặc đơn trong một biểu thức ? ? •((A+B)/C ( A + B ) / C) • Đảo ngược một chuỗi ký tự • Cá Ăn Kiến nếiK nĂ áC 
  19. Ngăn xếp – Sử dụng DSLK StkCnt StkTop N 7 7 Data Link 9 9  Data Link  4 4 Data Link
  20. Ngăn xếp – Sử dụng DSLK • Cấu tạo đầu stack StkCnt StkTop stack StkCnt N StkTop end stack • Cấu tạo một phần tử trong stack node Data Link end node Data Link
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2