[Tutorial] Thư viện STL trong lập trình C++: Stack

Giới thiệu về stack:

Stack hay còn gọi là ngăn xếp, là một loại container, được thiết kế để hoạt động theo kiểu LIFO (Last in first – out) (vào sau ra trước), tức là một kiểu danh sách (list) mà việc bổ sung và loại bỏ một phần tử được thực hiển ở cuối danh sách.

Cơ chế “vào sau ra trước” của stack tương tự như ngăp xếp. Hãy tưởng tượng, khi bạn xếp quần áo thành chồng lên nhau, sau đó, muốn lấy quần áo nào, ta phải lấy cái trên cùng (tức là cái được cho hàng ngăn xếp cuối cùng).

Vị trí cuối cùng của stack gọi là đỉnh (top) của ngăn xếp.

stack-introduce

Khai báo stack:

Để sử dụng stack, ta cần khai báo thư viện stack:

Các phương thức thành viên:

Capacity:
size() Trả về số lượng phần tử của stack
empty() Trả về true(1) nếu stack rỗng, ngược lại là false (0)
Element access:
top() Truy xuất phần tử ở đỉnh stack (phần tử cuối cùng được thêm vào)
Modifier:
push (const x) Thêm phần tử có giá trị x vào stack. Kích thước stack tăng thêm 1.
pop () Loại bỏ phần tử ở đỉnh stack. Kích thước stack giảm đi 1.

Capacity:

size()

Trả về số lượng phần tử của stack.

Ví dụ: Tạo một stack  có 5 phần tử bất kì và in ra số lượng phần tử của stack này.

Lưu ý:

Ta không thể khai báo stack<int> myStack (5) để khai báo 5 phần tử rỗng tương tự như vector hay list vì stack không cho phép ta khai báo phần tử rỗng.

Tương tự, ta không thể khai báo stack<int> myStack (5,100) để khai báo 5 phần tử của stack có giá trị 100.

empty()

Trả về true(1) nếu stack rỗng, ngược lại là false (0)

Ví dụ: Kiểm tra stack có rỗng không và  in ra thông báo tương ứng.

Element access:

Do tính chất của stack là chỉ có thể thêm vào lấy ra phần tử ở đỉnh stack, do đó, ta chỉ có thể truy cập phần tử ở đỉnh stack bằng phương thức top(). Về cơ bản, phương thức top() tương tự như phương thức back() trong list.

top()

Truy xuất phần tử ở đỉnh stack, tức lá truy xuất phần tử được thêm vào sau cùng. Truy xuất ở đây bao gồm in hoặc chỉnh sửa giá trị.

Ví dụ: Tạo stack có 5 phần tử có giá trị lần lượt là  A,B,C,D,E. Thay đổi phẩn tử ở đình stack thành ‘e’. In ra phần tử ở đỉnh stack sau khi thay đổi.

Modifier:

push (const x)

Thêm phần tử có giá trị x vào cuối stack. Kích thước stack tăng thêm 1.

Phương thức push của stack tương tự như phương thức push_back của list.

stack-push

Ví dụ:

Viết chương trình cho người dùng nhập vào kích thước stack và nhập vào giá trị các phần tử. In các phần tử trong stack.

Nhận xét:

Thứ tự in các phần tử của stack sẽ ngược lại so với thứ tự mà ta nhập vào.
Không thể sử dụng vòng lặp với biến iterator như đối list để in tất cả các phần tử vì stack chỉ cho phép truy xuất duy nhất phần tử ở đỉnh stack,  ví dụ mã lệnh  truy xuất stack như bên dưới là sai:

pop ()

Loại bỏ phần tử ở đình stack (phần tử cuối cùng được thêm vào stack) . Kích thước stack giảm đi 1.

 

stack-pop

Ví dụ: Viết chương trình cho người dùng nhập vào kích thước stack và nhập vào giá trị các phần tử. Sau đó, loại bỏ đi một nửa các phần tử ở đỉnh stack.

Không phải hàm thành viên:

swap(stack s1, stack s2) :

Hoán đổi  các phần tử của 2 stack với nhau.

Lưu ý: khác với vector và list, swap không phải là hàm thành viên của đối tượng, do đó, hàm swap cần truyền vào 2 tham số.

Ví dụ: Tạo stack thứ nhất có 3 phần tử 1,3,5 và stack thứ 2 có 2 phần tử 2,4. Hoán đổi các phần tử của hai stack. In ra kích thước của hai stack sau khi hoán đổi.

 

 

Share
Share