Stack kiểu nguyên (sử dụng mảng)

Đề bài:

Hãy tạo một Stack các số nguyên (sử dụng mảng).



Hướng dẫn:

Stack là gì?
Bạn hãy liên tưởng Stack giống như một cái ống chứa các hộp:

├──── size ────┤
┌─┬─┬─┬─┬─┬..┬─┬─
│█│█│█│ │ │  │ │  <= đẩy vào
└─┴─┴─┴─┴─┴..┴─┴─
     ↑
    top

Cái ống này có kích thước là size, nghĩa là nó có thể chứa tối đa là size cái hộp. Cái ống này cũng có một mảng các hộp(elements) mà nó đã chứa và chỉ số (hay là vị trí) của hộp ngoài cùng gọi là top (chỉ số của hộp trong cùng là 0).

Cái ống này chỉ có hai chức năng là đẩy một cái hộp từ bên ngoài vào và đẩy một cái hộp từ trong ra. Như vậy, cái hộp nào được đẩy vào sau nhưng lại được lấy ra trước.

Stack kiểu nguyên:

Ta tiến hành cài đặt một Stack kiểu số nguyên.

Các biến thành phần của Stack:
- size: kích thước của Stack
- *elements : con trỏ mảng các số nguyên
- top: chỉ số của phần tử ngoài cùng

Các hàm thành phần của Stack:
- Stack(int n): hàm khởi tạo Stack có kích thước size = n
- ~Stack(): hàm hủy Stack
- void Push(int x): đầy một số nguyên x vào Stack. Thực chất của Push là thêm x vào mảng elements và tăng biến top đi 1.
- int Pop(): đẩy phần tử top từ Stack ra (giá trị của hàm là giá trị của phần tử top). Thực chất của Pop là lấy giá trị của elements[top] và giảm biến top đi 1.

Ngoài ra ta thêm các hàm khác để tiện cho việc xử lý sau này:
- int Top(): Lấy giá trị của phần tử top (không đẩy phần tử top ra)
- bool Full(): Kiểm tra xem Stack đầy hay chưa
- bool Emty(): Kiểm tra xem Stack rỗng hay không

View Code:

#include<iostream.h>
#include<conio.h>

class Stack
{
   private: int size; //Kích thước Stack
   private: int *elements; //Mảng các phần tử kiểu nguyên
   private: int top; //Chỉ số của phần tử ngoài cùng

   public: Stack(int n) //Hàm khởi tạo
   {
      size = n;
      elements = new int[size];
      top = -1;
   }
   public: ~Stack() //Hàm hủy
   {
      delete elements;
   }
   public: void Push(int x) //Đẩy một phần từ x vào Stack
   {
      if(top == size - 1)cout << "\nStack da day";
      else elements[++top] = x;
   }
   public: int Pop() ////Đẩy phần tử top của Stack ra ngoài
   {
      if(top == -1)cout << "\nStack rong";
      else return elements[top--];
   }
   public: int Top() //Lấy giá trị của phần tử top
   {
      if(top == -1)cout << "\nStack rong";
      else return elements[top];
   }
   public: bool Full() //Kiểm tra Stack đầy
   {
      return top == size - 1;
   }
   public: bool Emty() //Kiểm tra Stack rỗng
   {
      return top == -1;
   }
};

main()
{
   Stack S(100); //Khởi tạo Stack có kích thước 100 phần tử
    S.Push(1); //Thêm 1 vào Stack
    S.Push(5); //Thêm 5 vào Stack
    S.Push(7); //Thêm 7 vào Stack
    S.Push(8); //Thêm 8 vào Stack

    while(!S.Emty()) cout << S.Pop() << endl;
   getch();
}

Ghi chú:
Bạn có thể thay Stack kiểu nguyên thành kiểu khác bằng cách thay kiểu dữ liệu cho mảng elements[].