Mục lục
- Giới thiệu
-
- Nắm vững định nghĩa, đặc điểm và kiểu dữ liệu trừu tượng của ngăn xếp
-
- Định nghĩa
-
- Là cấu trúc chỉ cho phép chèn/xóa tại đầu cuối
- Đặc điểm
-
- Đầu cuối là đỉnh (top)
- Nguyên tắc sau vào trước ra
- Kiểu dữ liệu trừu tượng
-
- Trang 57
-
- Mối quan hệ giữa ngăn xếp và đệ quy
-
- Đệ quy
-
- Định nghĩa đệ quy
-
- Khi một hàm, quá trình hay cấu trúc dữ liệu định nghĩa bên trong có sử dụng lại bản thân mình
- Giai thừa, chia để trị
- Cấu trúc dữ liệu đệ quy
-
- Node danh sách liên kết chứa con trỏ trỏ đến chính kiểu Node đó
- Danh sách liên kết, cây nhị phân
- Giải pháp đệ quy
-
- Bài toán không có cấu trúc đệ quy nhưng giải bằng đệ quy đơn giản hơn
- Tháp Hà Nội, 8 hậu, mê cung
- Quan hệ
-
- Khi hàm gọi chính nó nhiều lần
- Giao tiếp giữa các hàm cần dùng ngăn xếp
- Hệ thống quản lý không gian dữ liệu bằng ngăn xếp, mỗi lần gọi hàm sẽ cấp phát vùng nhớ tại đỉnh ngăn xếp
- Ngăn xếp mảng
- Ngăn xếp danh sách liên kết
- Chuyển đổi cơ số
- Kiểm tra cặp ngoặc
- Nhật ký phát triển
Giới thiệu
- Nắm vững định nghĩa, đặc điểm và kiểu dữ liệu trừu tượng của ngăn xếp
Định nghĩa
Là cấu trúc chỉ cho phép thao tác chèn/xóa tại đầu cuối
Đặc điểm
Đầu cuối là đỉnh (top)
Nguyên tắc sau vào trước ra
Kiểu dữ liệu trừu tượng
Trang 57
- Mối quan hệ giữa ngăn xếp và đệ quy
Đệ quy
Định nghĩa đệ quy
Khi một hàm, quá trình hay cấu trúc dữ liệu định nghĩa bên trong có sử dụng lại bản thân mình
Giai thừa, chia để trị
Cấu trúc dữ liệu đệ quy
Node danh sách liên kết chứa con trỏ trỏ đến chính kiểu Node đó
Danh sách liên kết, cây nhị phân
Giải pháp đệ quy
Bài toán không có cấu trúc đệ quy nhưng giải bằng đệ quy đơn giản hơn
Tháp Hà Nội, 8 hậu, mê cung
Quan hệ
Khi hàm gọi chính nó nhiều lần
Giao tiếp giữa các hàm cần dùng ngăn xếp
Hệ thống quản lý không gian dữ liệu bằng ngăn xếp, mỗi lần gọi hàm sẽ cấp phát vùng nhớ tại đỉnh ngăn xếp
Ngăn xếp mảng
#include <iostream>
#include <cstdio>
using namespace std;
#define MAXSIZE 100
typedef int Status;
typedef int ElementType;
struct ArrayStack {
int capacity;
ElementType* base;
ElementType* top;
};
Status InitStack(ArrayStack& s) {
s.base = new ElementType[MAXSIZE];
if (!s.base) return 0;
s.top = s.base;
s.capacity = MAXSIZE;
return 1;
}
Status Push(ArrayStack& s, ElementType e) {
if (s.top - s.base >= s.capacity) return 0;
*s.top++ = e;
return 1;
}
Status Pop(ArrayStack& s, ElementType& e) {
if (s.top == s.base) return 0;
e = *--s.top;
return 1;
}
ElementType GetTop(ArrayStack& s) {
if (s.top != s.base)
return *(s.top - 1);
return 0;
}
int main() {
ArrayStack s;
InitStack(s);
Push(s, 1);
cout << GetTop(s);
ElementType e;
Pop(s, e);
cout << e;
}
Ngăn xếp danh sách liên kết
#include <iostream>
#include <cstdio>
using namespace std;
struct ListNode {
int data;
ListNode* next;
};
struct LinkedListStack {
ListNode* top;
};
void InitStack(LinkedListStack& s) {
s.top = nullptr;
}
void Push(LinkedListStack& s, int value) {
ListNode* newNode = new ListNode{value, s.top};
s.top = newNode;
}
int Pop(LinkedListStack& s) {
if (!s.top) return -1;
int value = s.top->data;
ListNode* temp = s.top;
s.top = s.top->next;
delete temp;
return value;
}
int GetTop(LinkedListStack& s) {
if (s.top) return s.top->data;
return -1;
}
int main() {
LinkedListStack s;
InitStack(s);
Push(s, 1);
cout << GetTop(s) << endl;
cout << Pop(s) << endl;
}
Chuyển đổi cơ số
#include <iostream>
#include <cstdio>
using namespace std;
#define MAXSIZE 100
typedef int Status;
typedef int ElementType;
struct ArrayStack {
int capacity;
ElementType* base;
ElementType* top;
};
Status InitStack(ArrayStack& s) {
s.base = new ElementType[MAXSIZE];
if (!s.base) return -1;
s.top = s.base;
s.capacity = MAXSIZE;
return 1;
}
Status Push(ArrayStack& s, ElementType e) {
if (s.top - s.base >= s.capacity) return -1;
*s.top++ = e;
return 1;
}
Status Pop(ArrayStack& s, ElementType& e) {
if (s.top == s.base) return -1;
e = *--s.top;
return 1;
}
Status IsEmpty(ArrayStack& s) {
return s.top == s.base;
}
Status ConvertBase(ArrayStack& s, int number, int base) {
InitStack(s);
while (number > 0) {
Push(s, number % base);
number /= base;
}
while (!IsEmpty(s)) {
ElementType remainder;
Pop(s, remainder);
cout << remainder;
}
return 1;
}
int main() {
ArrayStack s;
ConvertBase(s, 10, 2);
}
Kiểm tra cặp ngoặc
#include <iostream>
#include <cstdio>
using namespace std;
#define MAXSIZE 100
typedef int Status;
typedef char ElementType;
struct ArrayStack {
int capacity;
ElementType* base;
ElementType* top;
};
Status InitStack(ArrayStack& s) {
s.base = new ElementType[MAXSIZE];
if (!s.base) return -1;
s.top = s.base;
s.capacity = MAXSIZE;
return 1;
}
Status Push(ArrayStack& s, ElementType e) {
if (s.top - s.base >= s.capacity) return -1;
*s.top++ = e;
return 1;
}
Status Pop(ArrayStack& s, ElementType& e) {
if (s.top == s.base) return -1;
e = *--s.top;
return 1;
}
ElementType GetTop(ArrayStack& s) {
if (s.top != s.base)
return *(s.top - 1);
return '\0';
}
Status IsEmpty(ArrayStack& s) {
return s.top == s.base;
}
Status CheckBrackets(ArrayStack& s) {
InitStack(s);
char input;
int valid = 1;
cin >> input;
while (input != '#' && valid) {
switch (input) {
case '(':
case '[': Push(s, input); break;
case ')':
if (!IsEmpty(s) && GetTop(s) == '(')
Pop(s, input);
else valid = 0;
break;
case ']':
if (!IsEmpty(s) && GetTop(s) == '[')
Pop(s, input);
else valid = 0;
break;
}
cin >> input;
}
return IsEmpty(s) && valid;
}
int main() {
ArrayStack s;
cout << (CheckBrackets(s) ? "1" : "0");
}
Nhật ký phát triển
Việc triển khai ngăn xếp mảng khá thuận lợi Dần hiểu rõ hơn về logic trong sách giáo trình Việc truyền tham chiếu &s và trả về giá trị qua &e cần lưu ý
Sự khác biệt giữa base và top giúp quản lý bộ nhớ hiệu quả Cú pháp *s.top++ = e ban đầu gây khó hiểu nhưng dần quen
Phần chuyển đổi cơ số gặp lỗi khi xuất kết quả Nguyên nhân do giá trị trả về của StackEmpty được xử lý sai Sửa lại hàm kiểm tra trạng thái rỗng giúp khắc phục
Phiên bản ban đầu của hàm ConvertBase thiếu hàm kiểm tra trạng thái ngăn xếp Đã bổ sung hàm IsEmpty() như sau:
Status IsEmpty(ArrayStack& s) {
return s.top == s.base;
}
-
Kiểm tra cặp ngoặc Logic kiểm tra khá trực quan nhưng cần lưu ý: 3.1 Không thể dùng điều kiện '(', '[' như trong video mẫu 3.2 Phải thêm break sau mỗi trường hợp xử lý 3.3 Cần thay đổi kiểu trả về của GetTop từ Status sang ElementType
Mặc dù hiểu rõ nguyên lý, việc triển khai vẫn phức tạp