Bài 7: Khái niệm về Stack - Sử dụng thư viện chuẩn STL cho C/C++

Đăng bởi: Admin | Lượt xem: 3715 | Chuyên mục: C/C++

Các tính năng cơ bản :

Stack là một dạng chuyển đổi danh sách chứa, được thiết kế đặc biệt theo dạng LIFO (last-in first-out), các phần tử vào đầu tiên sẽ được lấy ra cuối cùng và ngược lại

Các ngăn xếp được triển khai như các bộ điều hợp vùng chứa, là các lớp sử dụng một đối tượng được đóng gói của một lớp chứa cụ thể làm vùng chứa bên dưới của nó, cung cấp một tập hợp các hàm thành viên cụ thể để truy cập các phần tử của nó. Các phần tử được đẩy từ "phía sau" của danh sách chứa cụ thể, được gọi là đỉnh của ngăn xếp.

Container bên dưới có thể là bất kỳ mẫu lớp container tiêu chuẩn nào hoặc một số lớp container được thiết kế đặc biệt khác. Container sẽ hỗ trợ các hoạt động sau:

empty
size
back
push_back
pop_back

Tại mọi thời điểm, chúng ta duy trì một con trỏ tới phần tử dữ liệu vừa được PUSH cuối cùng vào trên ngăn xếp. Vì con trỏ này luôn biểu diễn vị trí trên cùng của ngăn xếp vì thế được đặt tên là top. Con trỏ top cung cấp cho chúng ta giá trị của phần tử trên cùng của ngăn xếp mà không cần phải thực hiện hoạt động xóa ở trên (hoạt động pop).

Phương thức để hỗ trợ các tính năng của ngăn xếp.

Phương thức peek() :

Cấu trúc như sau :

Bắt đầu hàm peek

   return stack[top]
   
kết thúc hàm

int peek() {
   return stack[top];
}

Phương thức isFull()

Bắt đầu hàm isfull

   if top bằng MAXSIZE
      return true
   else
      return false
   kết thúc if
   
kết thúc hàm

bool isfull() {
   if(top == MAXSIZE)
      return true;
   else
      return false;
}

Phương thức isEmpty() :

Giải thuật của hàm isEmpty():

bắt đầu hàm isempty

   if top nhỏ hơn 1
      return true
   else
      return false
   kết thúc if
   
kết thúc hàm

Sự triển khai của hàm isEmpty() trong ngôn ngữ C khác hơn một chút. Chúng ta khởi tạo top tại -1, giống như chỉ mục của mảng bắt đầu từ 0. Vì thế chúng ta kiểm tra nếu top là dưới 0 hoặc -1 thì ngăn xếp là trống. Dưới đây là phần code:

bool isempty() {
   if(top == -1)
      return true;
   else
      return false;
}

Hoạt động PUSH trong cấu trúc dữ liệu ngăn xếp

Tiến trình đặt (thêm) một phần tử dữ liệu mới vào trên ngăn xếp còn được biết đến với tên Hoạt động PUSH. Hoạt động push bao gồm các bước sau:

kiểm tra xem ngăn xếp đã đầy hay chưa.
nếu ngăn xếp là đầy, tiến trình bị lỗi và thoát ra.
nếu ngăn xếp chưa đầy, tăng top để trỏ tới phần bộ nhớ trống tiếp theo.
thêm phần tử dữ liệu vào vị trí nơi mà top đang trỏ đến trên ngăn xếp.
trả về success.

Nếu Danh sách liên kết được sử dụng để triển khai ngăn xếp, thì ở bước 3 chúng ta cần cấp phát một không gian động.

Cách sử dụng PUSH như sau :

bắt đầu hoạt động push: stack, data

   if stack là đầy
      return null
   kết thúc if
   
   top ← top + 1
   
   stack[top] ← data

kết thúc hàm

void push(int data) {
   if(!isFull()) {
      top = top + 1;   
      stack[top] = data;
   }else {
      printf("Khong the chen them du lieu vi Stack da day.\n");
   }
}

Hoạt động POP của cấu trúc dữ liệu ngăn xếp

Việc truy cập nội dung phần tử trong khi xóa nó từ ngăn xếp còn được gọi là Hoạt động POP. Trong sự triển khai Mảng của hoạt động pop(), phần tử dữ liệu không thực sự bị xóa, thay vào đó top sẽ bị giảm về vị trí thấp hơn trong ngăn xếp để trỏ tới giá trị tiếp theo. Nhưng trong sự triển khai Danh sách liên kết, hoạt động pop() thực sụ xóa phần tử xữ liệu và xóa nó khỏi không gian bộ nhớ.

Hoạt động POP có thể bao gồm các bước sau:

kiểm tra xem ngăn xếp là trống hay không.
nếu ngăn xếp là trống, tiến trình bị lỗi và thoát ra.
nếu ngăn xếp là không trống, truy cập phần tử dữ liệu tại top đang trỏ tới.
giảm giá trị của top đi 1.
trả về success.

Cách sử dụng POP :

bắt đầu hàm pop: stack

   if stack là trống
      return null
   kết thúc if
   
   data ← stack[top]
   
   top ← top - 1
   
   return data

kết thúc hàm

int pop(int data) {

   if(!isempty()) {
      data = stack[top];
      top = top - 1;   
      return data;
   }else {
      printf("Khong the lay du lieu, Stack la trong.\n");
   }
}

Ứng dụng của ngăn xếp :

Xử lý gọi hàm trong C/C++ - Trong máy tính, sử dụng để tính giá trị biểu thức, xử lý ngắt - Trong các chương trình biên dịch - Trong trình duyệt web, trình soạn thảo văn bản - Định giá biểu thức + Biểu thức trung tố: toán tử hai ngôi đứng giưã hai toán hạng, toán tử một ngôi đứng trước toán hạng + Biểu thức hậu tố : toán tử đứng sau toán hạng + Biểu thức tiền tố toán tử đứng trước toán hạng

VD định giá biểu thức A = b + c * d /e – f Trung tố a*(b-c)/d Hậu tố abc-*d/ Tiền tố /*a-bcd

Bài tiếp theo: Các hàm cơ bản và bài tập minh họa về STACK >>

Theo dõi VnCoder trên Facebook, để cập nhật những bài viết, tin tức và khoá học mới nhất!