Các kiểu dữ liệu trong C ( int - float - double - char ...) 
Thuật toán tìm ước chung lớn nhất trong C/C++ 
Cấu trúc lệnh switch case trong C++ (có bài tập thực hành) 
ComboBox - ListBox trong lập trình C# winforms 
Random trong Python: Tạo số random ngẫu nhiên 
Lệnh cin và cout trong C++ 
Cách khai báo biến trong PHP, các loại biến thường gặp 
Download và cài đặt Vertrigo Server 
Thẻ li trong HTML 
Thẻ article trong HTML5 
Cấu trúc HTML5: Cách tạo template HTML5 đầu tiên 
Cách dùng thẻ img trong HTML và các thuộc tính của img 
Thẻ a trong HTML và các thuộc tính của thẻ a thường dùng Cài đặt Stack bằng danh sách liên kết
Trong hướng dẫn này mình sẽ giới thiệu các bạn cách cài đặt cấu trúc Stack trong danh sách liên kết. Đây là một trong hai cách được sử dụng để cài đặt cấu trúc Stack.
Chúng ta sẽ thực hiện lần lượt các thao tác trong Stack sử dụng danh sách liên kết để cài đặt: Push, Pop, Top(), isEmpty().
1. Cấu trúc dữ liệu của Stack
Trong phần này mình sử dụng danh sách liên kết để cài đặt cho Stack vì vậy cấu trúc dữ liệu chính của nó chính là danh sách liên kết. Ta sẽ có cấu trúc của một Node trong Stack.
//khai báo cấu trúc Node
struct Node {
int data;
Node *next;
};
typedef struct Node *stack;Tiếp đến ta sẽ có cấu trúc của Stack, để quản lý Stack ta sử dụng con trỏ đầu để quản lý.
Bài viết này được đăng tại [free tuts .net]
//khai báo cấu trúc stack
struct Stack{
Node *head;
Node *tail;
};Sau khi đã khởi tạo cấu trúc của một Node và cấu trúc của Stack, ta sẽ tạo một Node mới.
//tạo Node
Node *createNode(int data) {
Node *p = new Node();
if (p == NULL) {
return NULL;
}
p->data = data;
p->next = NULL;
return p;
}
Như vậy là ta dã có cấu trúc cần thiết trong Stack cũng như đã khởi tạo cho nó, bây giờ chúng ta đã có thể thực hiện các thao tác trên Stack vừa được tạo.
2. Hàm isEmpty
Việc đầu tiên khi muốn thực hiện một thao tác nào đó trong Stack thì ta phải kiểm tra xem trong Stack có tồn tại phẩn tử hay không, Nếu Stack rỗng thì ta không thể thực hiện các thao tác đó trên Stack được.
//kiểm tra stack rỗng
bool isEmpty(stack s) {
return (s == NULL);
}3. Hàm Push
Khi thêm một phần tử vào Stack, trước tiên ta cần kiểm tra xem danh sách có rỗng hay không, nếu danh sách rỗng thì phần tử đầu tiên thêm vào chính là Node p. Ngược lại nếu danh sách đã tồn tại phần tử thì ta cho con trỏ của Node p trỏ đến Node đầu của danh sách để tạo liên kết.
Sau khi tạo liên kết cho Node p vừa được thêm vào, ta cập nhật là Node đầu cho danh sách.
void push(stack &s, int data) {
// tạo một Node mới
Node *ptr = createNode(data);
// kiểm tra stack rỗng
if (isEmpty(s)) {
s = ptr;
}
//nếu tồn tại phần tử ta trỏ đến phần tử đầu danh sách
else {
ptr->next = s;
s = ptr;
}
}
4. Hàm Pop
Việc xóa một phần tử khỏi Stack được thực hiện khá đơn giản, đầu tiên ta cũng sẽ phải kiểm tra xem danh sách có tồn tại phần tử hay không. Nếu danh sách rỗng thì ta thực hiện return và kết thúc hàm, ngược lại nếu danh sách có tồn tại phần tử thì ta bắt đầu thực hiện các bước sau:
- Gán giá trị của Node đầu Stack vào biến x.
- Cập nhập Node đầu Stack và Node tiếp theo.
- Xóa Node đầu Stack vừa lấy chính là Node x.
int pop(stack &s) {
if (!isEmpty(s)) {
//tạo một biến data
int data = s->data;
//tạo Node x và gán cho bằng s
Node *x = s;
// cho s = s trỏ đến next
s = s->next;
// thực hiện xóa node x
delete(x);
cout<<"Xóa thành công !!";
return data;
}
else {
cout << "Stack rỗng!" << endl;
}
}5. Hàm Top
Hàm Top() có chức năng hiển thị phần tử và không xóa nó khỏi Stack, không giống như Pop sau khi lấy phần tử từ Stack ra nó sẽ thực hiện xóa luôn phần tử đó khỏi Stack.
Đầu tiên ta sẽ kiểm tra xem danh sách có phần tử hay không, nếu có thì ta mới thực hiện lấy giá trị x, nếu danh sách rỗng thì return và kết thúc hàm.
int top(stack s) {
// kiểm tra stack tồn tại phần tử thì thực hiện hiển thị ra màn hình
if (!isEmpty(s)) {
return s->data;
}
else {
cout << "Stack rỗng!" << endl;
}
}6. Ví dụ xây dựng một cấu trúc Stack hoàn chỉnh
Ta đã có lần lượt các hàm cần thiết cho một cấu trúc Stack, các bạn có thể tham khảo một chương trình mình đã viết sẵn dưới đây. Chương trình chỉ đơn giản là thêm phần tử, xóa phần tử và hiển thị phần tử và sử dụng danh sách liên kết để cài đặt cho Stack.
Full code:
#include<iostream>
using namespace std;
//khai báo cấu trúc Node
struct Node {
int data;
Node *next;
};
typedef struct Node *stack;
//khai báo cấu trúc stack
struct Stack{
Node *head;
Node *tail;
};
//kiểm tra stack rỗng
bool isEmpty(stack s) {
return (s == NULL);
}
//tạo Node
Node *createNode(int data) {
Node *p = new Node();
if (p == NULL) {
return NULL;
}
p->data = data;
p->next = NULL;
return p;
}
void push(stack &s, int data) {
// tạo một Node mới
Node *ptr = createNode(data);
// kiểm tra stack rỗng
if (isEmpty(s)) {
s = ptr;
}
//nếu tồn tại phần tử ta trỏ đến phần tử đầu danh sách
else {
ptr->next = s;
s = ptr;
}
}
int top(stack s) {
if (!isEmpty(s)) {
return s->data;
}
else {
cout << "Stack is empty!" << endl;
}
}
int pop(stack &s) {
if (!isEmpty(s)) {
//tạo một biến data
int data = s->data;
//tạo Node x và gán cho bằng s
Node *x = s;
// cho s = s trỏ đến next
s = s->next;
// thực hiện xóa node x
delete(x);
cout<<"Xóa thành công !!";
return data;
}
else {
cout << "Stack rỗng!" << endl;
}
}
int main() {
int lc, k;
stack s;
push(s, 10);
push(s, 11);
push(s, 12);
push(s, 13);
push(s, 14);
push(s, 15);
push(s, 16);
cout<<"danh sách các số bao gồm : 10, 11, 12, 13, 14, 15, 16";
do{
cout << "\n\n\t\t ============== Menu ==============";
cout << "\n\t1. Hiển thị phần tử đầu Stack";
cout << "\n\t2. Xóa phần tử đầu Stack";
cout << "\n\t0. Ket thuc";
cout << "\n\n\t\t ============== End ==============";
cout<<"\nNhập lựa chọn bạn muốn chọn: ";
cin>> lc;
switch(lc){
case 0: break;
case 1:
cout<<"Phần tử đầu tiên trong Stack: "<<top(s);
break;
case 2:
pop(s);
break;
default: cout<<"\nNhập sai, vui lòng nhập lại!";
}
} while(lc);
cout<<"Chương trình này được đang tại Freetuts.net";
}Kết quả: Mình đã thực hiện thêm phần tử sẵn trước đó bao gồm các số: 10, 11, 12, 13 ,14, 15, 16.
7. Kết luận
Như vậy là chúng ta đã tìm hiểu xong về cấu trúc dữ liệu của Stack và các thao tác cơ bản của nó. Trong bài này mình đã sử dụng danh sách liên kết để cài đặt cho Stack, ở bài tiếp theo mình sẽ sử dụng mảng một chiều để cài đặt cho Stack. Các bạn hãy chú ý theo dõi nhé !!!
