Ngăn xếp(Stack)

1. Định nghĩa: Tập hợp các node thông tin được tổ chức liên tục hoặc rời rạc nhau trong bộ nhớ và thực hiện theo cơ chế FILO (First – In – Last – Out )
   
1. Biểu diễn liên tục: Các phần tử được lưu trữ liền kề nhau (Array-Mảng)
2. Biểu diễn rời rạc: Các phần tử được lưu trữ rời rạc (LinkedList-DS liên kết)
2. Khai báo
   Ta cần:
   1. 1 con trỏ Top lưu vị trí của đỉnh Stack
   2. 1 kiểu dữ liệu lưu các giá trị: Array, LinkedList, List, Vector..
   Ở đây mình sẽ dùng kiểu Array để lưu trữ:

           class stack{
               int top;
               int s[100];
           }
           

3. Các thao tác
   
   1. Kiểm tra tính Rỗng của stack:top=-1 là rỗng và ngược lại
      

              bool isEmpty(){
                  if(top==-1) //quy uoc top=-1 la rong va nguoc lai
                      return true;
                  return false;
              }
                      

   2. Kiểm tra tính đầy của stack: do mình đặt size=100 nên khi top==99 sẽ là đầy stack

              bool isFull(){
                  if(top==99)
                      return true;
                  return false;
              }
                          

   3. Thêm 1 phần tử vào stack
      

              void push(int value){
                  if(!isFull())
                      s[++top]=value;
                  else
                      cout<<"Stack Full"<< endl;
              }
                          

   4. Lấy 1 phần tử ra khỏi stack
      

              int pop(){
                  if(!isEmpty()){
                      int x=s[top--];
                      return x;
                  }
                  else
                  cout<<"Stack Empty"<< endl;
              }
                          

4. Trong thư viện STL của C++ cũng có 1 lớp Stack được cài đặt sẵn như List hay Vector ở bài trước:
   Lưu ý cần include lớp Stack: #include< stack >
   1. Khai báo: stack < kieu_du_lieu > ten_bien
      VD: stack < int > a;
   2. Các hàm hay sử dụng:
      
      1. bool empty();// Stack rỗng trả về true và ngược lại
      2. void push(value);// thêm 1 phần tử vào Stack
      3. void pop();//xóa phần tử ở đỉnh Stack
      4. reference top();//trả về giá trị tại đỉnh Stack
      5. int size();//trả về kích thước của Stack
      6. duyệt các phần tử trong Stack: :từ đỉnh xuống
         

             void showstack(stack  s){ 
                 while (!s.empty()){ 
                     cout << s.top() << " "; 
                     s.pop(); 
                 } 
                 cout << endl;
             } 
                                     

5. Code các bạn có thể tham khảo ở đây và ở đây - chịu khó chút quảng cáo ạ