Cài đặt Stack bằng danh sách liên kết đơn trong C++


| Cài đặt Stack bằng danh sách liên kết đơn trong C++



Khai báo struct NODE và LIST


typedef struct node
{
      int data;
      node* next;
}NODE;

typedef struct list
{
      NODE* head;
      NODE* tail;
}LIST;

Prototype

void init(LIST&);
int IsEmpty(LIST);
NODE* creatNode(int);
void Push(LIST&, NODE*);
int Pop(LIST&, int&);
int Peek(LIST&);
void Nhap(LIST&);
void Xuat(LIST);
void Menu();
void XulyMenu(LIST&);

Khởi tạo danh sách liên kết

void init(LIST& s)
{
      s.head = s.tail = NULL;
}

Tạo node mới trong danh sách liên kết đơn

NODE* creatNode(int x)
{
      NODE* p = new NODE;
      if (p == NULL)
            return NULL;
      p->data = x;
      p->next = NULL;
      return p;
}

Kiểm tra Stack có rỗng không

int IsEmpty(LIST s)
{
      return (s.head == NULL);
}
Lưu ý: cài Stack từ Danh sách liên kết đơn không cần Hàm kiểm tra Stack có đầy không (IsFull)

Push: Thêm đối tượng vào Stack

void Push(LIST& s, NODE* p)
{
      if (IsEmpty(s))
      {
            s.head = s.tail = p;
      }
      else
      {
            p->next = s.head;
            s.head = p;
      }
}

Pop: Xoá và lấy đối tượng từ Stack

int Pop(LIST& s, int& trave)
{
      NODE* p;
      if (!IsEmpty(s))
      {
            if (s.head != NULL)
            {
                  p = s.head;
                  trave = p->data;
                  s.head = s.head->next;
                  if (s.head == NULL)
                        s.tail = NULL;
                  return 1;
                  delete p;
            }
      }
      return 0;
}

Peek: Lấy đối tượng từ Stack nhưng không xoá

int Peek(LIST& s)
{
      return s.head->data;
}


Hàm nhập

void Nhap(LIST& s)
{
      int n;
      cout << "Nhap so phan tu cua Stack: ";
      cin >> n;
      for (int i = 0; i < n; i++)
      {
            int x;
            cout << "Nhap phan tu thu " << i << ": ";
            cin >> x;
            NODE* p = creatNode(x);
            Push(s, p);
      }
}

Hàm xuất

void Xuat(LIST s)
{
      if (IsEmpty(s))
            cout << "Stack rong.\n";
      else
      {
            cout << "Xuat Stack: ";
            for (NODE* p = s.head; p != NULL; p = p->next)
            {
                  cout << p->data << " ";
            }
            cout << endl;
      }
}

Xuất danh sách Menu

void Menu()
{
      cout << "\n1. Kiem tra Stack rong hay khong?";
      cout << "\n2. Push phan tu vao Stack.";
      cout << "\n3. Pop phan tu tu Stack.";
      cout << "\n4. Xem phan tu o dau Stack.";
      cout << "\n5. Xuat Stack.";
      cout << "\n6. Thoat.";
cout << endl;
}

Xử lý Menu với lựa chọn tương ứng

void XulyMenu(LIST& s)
{
      int luachon;
      do
      {
            cout << "\nNhap lua chon: ";
            cin >> luachon;
            switch (luachon)
            {
            case 1:
            {
                  if (IsEmpty(s))
                        cout << "Stack rong.\n";
                  else cout << "Stack khong rong.\n";
                  break;
            }
            case 2:
            {
                  int x;
                  cout << "Nhap gia tri phan tu can push: ";
                  cin >> x;
                  NODE* p = creatNode(x);
                  Push(s, p);
                  cout << "Push thanh cong.\n";
                  Xuat(s);
                  break;
            }
            case 3:
            {
                  int trave;
                  Pop(s, trave);
                  cout << "Phan tu da pop: " << trave << endl;
                  Xuat(s);
                  break;
            }
            case 4:
            {
                  cout << "Phan tu o dau Stack: " << Peek(s) << endl;
                  break;
            }
            case 5:
            {
                  Xuat(s);
                  break;
            }
            case 6:
                  exit(1);
                  break;
            }
      } while (luachon < 1 || luachon > 6);
}

Main.cpp

#include <iostream>
using namespace std;
int main()
{
      LIST s;
      init(s);
      Nhap(s);
      Xuat(s);
      Menu();
      while (true)
      {
            XulyMenu(s);
      }
      system("pause");
      return 0;
}

Nhận xét

Đăng nhận xét