Thảo luận:Ngăn xếp

Nội dung trang không được hỗ trợ ở ngôn ngữ khác.
Bách khoa toàn thư mở Wikipedia

Nội dung để merge:


Ngăn xếp - Stack[sửa mã nguồn]

Trong stack, các đối tượng có thể được thêm vào stack bất kỳ lúc nào nhưng chỉ có đối tượng thêm vào sau cùng mới được phép lấy ra khỏi stack.

Thao tác thêm 1 đối tượng vào stack thường được gọi là "Push". Thao tác lấy 1 đối tượng ra khỏi stack gọi là "Pop".

Trong tin học, cấu trúc dữ liệu stack có nhiều ứng dụng: khử đệ qui, tổ chức lưu vết các quá trình tìm kiếm theo chiều sâu và quay lui, vét cạn, ứng dụng trong các bài toán tính toán biểu thức.

Ta có thể định nghĩa cấu trúc dữ liệu stack như sau: stack là một cấu trúc dữ liệu trừu tượng (ADT) tuyến tính hỗ trợ 2 thao tác chính:

• Push(o): Thêm đối tượng o vào đầu stack

• Pop(): Lấy đối tượng ở đầu stack ra khỏi stack và trả về giá trị của nó. Nếu stack rỗng thì lỗi sẽ xảy ra.

Ngoài ra, stack cũng hỗ trợ một số thao tác khác:

• isEmpty(): Kiểm tra xem stack có rỗng không.

• Top(): Trả về giá trị của phần tử nằm ở đầu stack mà không hủy nó khỏi stack. Nếu stack rỗng thì lỗi sẽ xảy ra.

Các thao tác thêm, trích và huỷ một phần tử chỉ được thực hiện ở cùng một phía của Stack do đó hoạt động của Stack được thực hiện theo nguyên tắc LIFO (Last In First Out - vào sau ra trước). Ðể biểu diễn Stack, ta có thể dùng mảng 1 chiều hoặc dùng danh sách liên kết.

Biểu diễn stack dùng mảng[sửa mã nguồn]

//day la demo viet bang c++// //Ban co the lien he: //sadbluesky@gmail.com neu co van de nao chua hieu//

  1. include<iostream>
  2. define max 1000

class Stack {

    private: 
         int top, node[max];//phan tu dau va mang//
    public:
         Stack()
         {
            top=-1;//khoi tao stack
         }
         bool empty()//kiem tra stack co rong hay khong
         {
           if(top==-1)
              return true;
            return false;
         }
         void push(int data)//dua phan tu vao stack
         {
            if(top==max-1)
              cout<<"Stack da day roi";
            else
               node[++top]=data;//dua du lieu vao stack
         }
         int pop()
         {
             if(empty())//stack bi rong
                cout<<"Stack Da Rong";
             return node[top--];
         }

}; int main(int agrc, char* agrv[]) {

  Stack s;int i;
  for(i=0;i<1000;i++)
  s.push(i);
  for(i=0;i<1000;i++)
  {
     int kq=s.pop();
     cout<<" "<<kq<<"  ";
  }

}

Biểu diễn stack dùng danh sách liên kết[sửa mã nguồn]

Ứng dụng của Stack[sửa mã nguồn]

Cấu trúc Stack thích hợp lưu trữ các loại dữ liệu mà trình tự truy xuất ngược với trình tự lưu trữ, do vậy một số ứng dụng sau thường cần đến stack :

• Trong trình biên dịch (thông dịch), khi thực hiện các thủ tục, Stack được sử dụng để lưu môi trường của các thủ tục.

• Trong một số bài toán của lý thuyết đồ thị (như tìm đường đi), Stack cũng thường được sử dụng để lưu dữ liệu khi giải các bài toán này.

Ngoài ra, Stack cũng còn được sử dụng trong trường hợp khử đệ qui đuôi.