Cộng đồng chia sẻ tri thức Lib24.vn

Cấu trúc dữ liệu và thuật toán - Ngăn xếp

Gửi bởi: Võ Thị Hường 13 tháng 2 2020 lúc 10:41:47


Mục lục
* * * * *

Một ngăn xếp là Kiểu dữ liệu trừu tượng (ADT), thường được sử dụng trong hầu hết các ngôn ngữ lập trình. Nó được đặt tên là stack vì nó hoạt động giống như một ngăn xếp trong thế giới thực, ví dụ - một cỗ bài hoặc một đống đĩa, v.v.

Một ngăn xếp trong thế giới thực chỉ cho phép các hoạt động ở một đầu duy nhất. Ví dụ: chúng ta chỉ có thể đặt hoặc loại bỏ một thẻ hoặc tấm từ đầu ngăn xếp. Tương tự, Stack ADT chỉ cho phép tất cả các hoạt động dữ liệu ở một đầu. Tại bất kỳ thời điểm nào, chúng tôi chỉ có thể truy cập vào phần tử trên cùng của ngăn xếp.

Tính năng này làm cho nó cấu trúc dữ liệu LIFO. LIFO là viết tắt của Lần xuất trước. Ở đây, phần tử được đặt (chèn hoặc thêm) cuối cùng, được truy cập trước. Trong thuật ngữ ngăn xếp, hoạt động chèn được gọi là hoạt động PUSH và hoạt động loại bỏ được gọi là hoạt động POP .

Đại diện ngăn xếp

Sơ đồ sau mô tả một ngăn xếp và các hoạt động của nó -

Một ngăn xếp có thể được thực hiện bằng Mảng, Cấu trúc, Con trỏ và Danh sách Liên kết. Stack có thể là một kích thước cố định hoặc nó có thể có ý nghĩa thay đổi kích thước động. Ở đây, chúng ta sẽ thực hiện ngăn xếp bằng cách sử dụng các mảng, làm cho nó thực hiện ngăn xếp kích thước cố định.

Hoạt động cơ bản

Các hoạt động ngăn xếp có thể liên quan đến việc khởi tạo ngăn xếp, sử dụng nó và sau đó khởi tạo lại nó. Ngoài những thứ cơ bản này, một ngăn xếp được sử dụng cho hai thao tác chính sau -

  1. đẩy () - Đẩy (lưu trữ) một phần tử trên ngăn xếp.
  2. pop () - Loại bỏ (truy cập) một phần tử khỏi ngăn xếp.

Khi dữ liệu được PUSHed lên ngăn xếp.

Để sử dụng stack một cách hiệu quả, chúng ta cũng cần kiểm tra trạng thái của stack. Với cùng mục đích, chức năng sau được thêm vào ngăn xếp -

  1. peek () - lấy phần tử dữ liệu hàng đầu của ngăn xếp mà không xóa nó.
  2. isFull () - kiểm tra xem ngăn xếp đã đầy chưa.
  3. isEmpty () - kiểm tra xem stack có trống không.

Tại mọi thời điểm, chúng tôi duy trì một con trỏ tới dữ liệu PUSHed cuối cùng trên ngăn xếp. Vì con trỏ này luôn đại diện cho đỉnh của ngăn xếp, do đó được đặt tên là đỉnh . Con trỏ trên cùng cung cấp giá trị hàng đầu của ngăn xếp mà không thực sự loại bỏ nó.

Trước tiên chúng ta nên tìm hiểu về các thủ tục để hỗ trợ các chức năng ngăn xếp -

nhìn trộm ()

Thuật toán của hàm peek () -

begin procedure peek
   return stack[top]
end procedure

Thực hiện hàm peek () trong ngôn ngữ lập trình C -

Thí dụ

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

đầy đủ ()

Thuật toán của hàm isfull () -

begin procedure isfull

   if top equals to MAXSIZE
      return true
   else
      return false
   endif
   
end procedure

Thực hiện hàm isfull () trong ngôn ngữ lập trình C -

Thí dụ

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

isempty ()

Thuật toán của hàm isempty () -

begin procedure isempty

   if top less than 1
      return true
   else
      return false
   endif
   
end procedure

Việc thực hiện hàm isempty () trong ngôn ngữ lập trình C hơi khác một chút. Chúng tôi khởi tạo đỉnh ở -1, vì chỉ số trong mảng bắt đầu từ 0. Vì vậy, chúng tôi kiểm tra xem đỉnh có dưới 0 hay -1 để xác định xem ngăn xếp có trống không. Đây là mã -

Thí dụ

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

Hoạt động đẩy

Quá trình đưa một phần tử dữ liệu mới lên ngăn xếp được gọi là Thao tác đẩy. Hoạt động đẩy bao gồm một loạt các bước -

  1. Bước 1 - Kiểm tra xem ngăn xếp đã đầy chưa.
  2. Bước 2 - Nếu ngăn xếp đầy, tạo ra lỗi và thoát.
  3. Bước 3 - Nếu ngăn xếp không đầy, hãy tăng từ trên xuống để chỉ chỗ trống tiếp theo.
  4. Bước 4 - Thêm phần tử dữ liệu vào vị trí ngăn xếp, nơi đỉnh đang trỏ.
  5. Bước 5 - Trả về thành công.

Nếu danh sách được liên kết được sử dụng để thực hiện ngăn xếp, thì trong bước 3, chúng ta cần phân bổ không gian động.

Thuật toán cho hoạt động PUSH

Một thuật toán đơn giản cho hoạt động Push có thể được bắt nguồn như sau -

begin procedure push: stack, data

   if stack is full
      return null
   endif
   
   top ← top + 1
   stack[top] ← data

end procedure

Thực hiện thuật toán này trong C, rất dễ dàng. Xem mã sau -

Thí dụ

void push(int data) {
   if(!isFull()) {
      top = top + 1;   
      stack[top] = data;
   } else {
      printf("Could not insert data, Stack is full.\n");
   }
}

Hoạt động nhạc pop

Truy cập nội dung trong khi xóa nội dung đó khỏi ngăn xếp, được gọi là Hoạt động Pop. Trong một 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 đó phần trên được giảm xuống vị trí thấp hơn trong ngăn xếp để trỏ đến giá trị tiếp theo. Nhưng trong việc thực hiện danh sách liên kết, pop () thực sự loại bỏ thành phần dữ liệu và giải phóng không gian bộ nhớ.

Một hoạt động Pop có thể bao gồm các bước sau -

  1. Bước 1 - Kiểm tra xem ngăn xếp có trống không.
  2. Bước 2 - Nếu ngăn xếp trống, tạo ra lỗi và thoát.
  3. Bước 3 - Nếu ngăn xếp không trống, truy cập vào phần tử dữ liệu mà đỉnh đang trỏ.
  4. Bước 4 - Giảm giá trị của top 1.
  5. Bước 5 - Trả về thành công.

Thuật toán cho hoạt động Pop

Một thuật toán đơn giản cho hoạt động Pop có thể được bắt nguồn như sau -

begin procedure pop: stack

   if stack is empty
      return null
   endif
   
   data ← stack[top]
   top ← top - 1
   return data

end procedure

Việc thực hiện thuật toán này trong C, như sau -

Thí dụ

int pop(int data) {

   if(!isempty()) {
      data = stack[top];
      top = top - 1;   
      return data;
   } else {
      printf("Could not retrieve data, Stack is empty.\n");
   }
}

Được cập nhật: 25 tháng 3 lúc 17:24:23 | Lượt xem: 835

Các bài học liên quan