Cách cài đặt stack có sử dụng template

0
257

Bài viết hôm nay mình sẽ hướng dẫn các bạn cách cài đặt stack có sử dụng template trong ngôn ngữ c++. Nếu bạn chưa biết template là gì thì có thể xem lại tại đây.

Stack là gì: Stack là một cấu trúc dữ liệu thường dùng phổ biến trong các ngôn ngữ lập trình. Bạn có thể tưởng tượng stack như một đống sách vậy, cứ quyển sau bỏ vào thì sẽ nằm trên quyển trước. Vì vậy mới có một câu nói về stack đó là  “Vào sau ra trước ! “

Các hoạt động cơ bản trên stack

Stack hỗ trợ cho chúng ta các hoạt động sau:

  • Hoạt động Pop(): Xóa dữ liệu từ ngăn xếp
  • Hoạt động Push(): Thêm một phần tử từ ngăn xếp
  • Hoạt động isEmpty(): Kiểm tra xem ngăn xếp có rỗng hay không
  • Hoạt động isFull(): Kiểm tra xem ngăn xếp đã đầy hay chưa

Trong stack ta luôn phải để con trỏ Top trỏ tới phần tử cuối cùng được Push() vào. Sở dĩ con trỏ có tên là Top vì nó luôn trỏ đến phần tử cuối cùng của mảng.

Cách cài đặt stack sử dụng template

Chúng ta sẽ lần lượt cài đặt các hoạt động của stack như sau

Khai báo một lớp stack

Ở trên có các thuộc tính Size chính là số lượng phần tử của stack, Top chính là vị trí của con trỏ chỉ tới phần tử cuối cùng. Data chính là con trỏ dùng để lưu trữ dữ liệu.

Cài đặt construction cho stack

Nếu không truyền vào giá trị cho tham số n, thì mặc định con stack sẽ có 10 phần tử. Ta khởi tạo vị trí Top bằng -1 vì hiện tại stack đang trống.

Cài đặt destruction cho stack

Destruction chỉ có nhiệm vụ là xóa dữ liệu của con trỏ mà thôi.

Cài đặt hoạt động isEmpty()

Cài đặt hoạt động isFull()

Cài đặt hoạt động Push()

Đầu tiên ta kiểm tra xem ngăn xếp đã đầy chưa, nếu vẫn chưa đầy thì ta tiến hành tăng giá trị Top và thêm phần tử vào cuối stack. Hoạt động Push() sẽ trả về giá trị true nếu đã thêm được phần tử thành công.

Cài đặt hoạt động Pop()

Ta tiến hành kiểm tra xem ngăn xếp có rỗng hay không, nếu không rỗng thì sẽ lấy ra giá trị cuối cùng và giảm giá trị của Top. Hoạt động Pop() sẽ trả về giá trị true nếu phần tử đã được lấy ra từ stack thành công và ngược lại.

Chạy thử chương trình cài đặt stack

Bài viết mình đến đây là kết thúc. Cám ơn các bạn đã theo dõi !

avatar
  Subscribe  
Notify of