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

Ngăn xếp là một 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à ngăn xếp vì nó hoạt động giống như một ngăn xếp trong thế giới thực, chẳng hạn - một bộ 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. Ví dụ, chúng ta chỉ có thể đặt hoặc lấy thẻ hoặc đĩa ở trên cùng của ngăn xếp. Tương tự như vậy, 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 ta chỉ có thể truy cập phần tử trên cùng của ngăn xếp.

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

Biểu 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. Ngăn xếp có thể có kích thước cố định hoặc có thể có cảm giác thay đổi kích thước động. Ở đây, chúng ta sẽ triển khai ngăn xếp bằng cách sử dụng các mảng, làm cho nó trở thành một triển khai ngăn xếp có 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ử khởi tạo nó. Ngoài những nội dung cơ bản này, ngăn xếp được sử dụng cho hai hoạt động chính sau:

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

Khi dữ liệu được PUSHed vào ngăn xếp.

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

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

Tại mọi thời điểm, chúng tôi duy trì một con trỏ đến 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 phần trên cùng của ngăn xếp, do đó có têntop. Cáctop con trỏ cung cấp giá trị cao nhất 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 hàm 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 -

Example

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

isfull ()

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.

Example

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 triển khai hàm isempty () trong ngôn ngữ lập trình C hơi khác. 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 dưới 0 hay -1 để xác định xem ngăn xếp có trống hay không. Đây là mã -

Example

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 vào ngăn xếp được gọi là Hoạt động Đẩy. Hoạt động đẩy bao gồm một loạt các bước -

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

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 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 Đẩy có thể được suy ra như sau:

begin procedure push: stack, data

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

end procedure

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

Example

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 Pop

Truy cập nội dung trong khi xóa nội dung đó khỏi ngăn xếp, được gọi là Thao tác bật. Trong triển khai mảng của thao tác pop (), phần tử dữ liệu không thực sự bị xóa, thay vào đótopđượ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 triển khai danh sách liên kết, pop () thực sự loại bỏ phần tử dữ liệu và phân bổ không gian bộ nhớ.

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

Step 1 - Kiểm tra xem ngăn xếp có trống không.
Step 2 - Nếu ngăn xếp trống, tạo ra lỗi và thoát.
Step 3 - Nếu ngăn xếp không trống, hãy truy cập vào phần tử dữ liệu tại đó top đang trỏ.
Step 4 - Giảm giá trị của top 1.
Step 5 - Trả lại 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 suy ra 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 triển khai thuật toán này trong C, như sau:

Example

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ó một chương trình ngăn xếp hoàn chỉnh bằng ngôn ngữ lập trình C, vui lòng nhấp vào đây .