Cách cài đặt stack có sử dụng template
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
template<class T> class Stack { private: int Size; int Top; T *Data; public: Stack(int = 10); ~Stack(); bool Push(const T&); bool Pop(T&); bool isEmpty() const; bool isFull() const; }; |
Ở 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
|
1 2 3 4 5 6 7 8 9 |
template<class T> Stack<T> ::Stack(int n) { if (n > 0 && n < 1000) Size = n; else Size = 10; Top = -1; Data = new T[Size]; } |
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
|
1 2 3 4 |
template<class T> Stack<T> ::~Stack() { delete[] Data; } |
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()
|
1 2 3 4 5 6 |
template<class T> bool Stack<T>::isEmpty() const{ if (Top == -1) return true; return false; } |
Cài đặt hoạt động isFull()
|
1 2 3 4 5 6 |
template<class T> bool Stack<T>::isFull() const { if (Top == Size) return true; return false; } |
Cài đặt hoạt động Push()
|
1 2 3 4 5 6 7 8 9 10 |
template<class T> bool Stack<T> ::Push(const T& Item) { if (!isFull()) { Top++ ; Data[Top] = Item; /*Đã thêm được vào Stack*/ return true; } return false; } |
Đầ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()
|
1 2 3 4 5 6 7 8 9 |
template<class T> bool Stack<T> ::Pop(T& Item) { if (!isEmpty()) { Item = Data[Top]; Top--; return true; } return false; } |
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
#include <iostream> using namespace std; template<class T> class Stack { private: int Size; int Top; T *Data; public: Stack(int = 10); ~Stack(); bool Push(const T&); bool Pop(T&); bool isEmpty() const; bool isFull() const; }; template<class T> Stack<T> ::Stack(int n) { if (n > 0 && n < 1000) Size = n; else Size = 10; Top = -1; Data = new T[Size]; } template<class T> Stack<T> ::~Stack() { delete[] Data; } template<class T> bool Stack<T> ::Push(const T& Item) { if (!isFull()) { Top++ ; Data[Top] = Item; /*Đã thêm được vào Stack*/ return true; } return false; } template<class T> bool Stack<T> ::Pop(T& Item) { if (!isEmpty()) { Item = Data[Top]; Top--; return true; } return false; } template<class T> bool Stack<T>::isEmpty() const{ if (Top == -1) return true; return false; } template<class T> bool Stack<T>::isFull() const { if (Top == Size) return true; return false; } int main() { /*Khai báo Stack có 100 phần tử*/ Stack<int> a(100); /*Push 7 phần tử vào Stack*/ a.Push(1); a.Push(2); a.Push(3); a.Push(4); a.Push(5); a.Push(6); a.Push(7); int data; /*In tất cả các phần tử trong Stack ra màn hình*/ while (a.Pop(data) ) { cout << data<<endl; } } |
|
1 2 3 4 5 6 7 |
7 6 5 4 3 2 1 |
Bài viết mình đến đây là kết thúc. Cám ơn các bạn đã theo dõi !
![Sinh số ngẫu nhiên trong C/C++, Sinh số random trong đoạn [a,b]](https://blog.luyencode.net/wp-content/uploads/2018/10/sinh-so-ngau-nhien-trong-cpp-768x427.jpg)
