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


| Cài đặt Queue 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&);
NODE* CreateNode(int);
bool IsEmpty(LIST);
void EnQueue(LIST&, NODE*);
int DeQueue(LIST&, int&);
void Input(LIST&);
void Output(LIST);

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

void Init(LIST& Q)
{
      Q.head = Q.tail = NULL;
}

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

NODE* CreateNode(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

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

EnQueue: Thêm phần tử vào Queue


void EnQueue(LIST& Q, NODE* p)
{
      if (Q.head == NULL)
            Q.head = Q.tail = p;
      else
      {
            Q.tail->next = p;
            Q.tail = p;
      }
}

DeQueue: Xoá và lấy phần tử từ Queue

int DeQueue(LIST& Q, int& saved)
{
      if (!IsEmpty(Q))
      {
            NODE* p = Q.head;
            saved = p->data;
            Q.head = Q.head->next;
            return 1;
            delete p;
      }
      return 0;
}

Hàm nhập

void Input(LIST& Q)
{
      int n;
      cout << "Nhap so luong phan tu Queue: ";
      cin >> n;
      for (int i = 0; i < n; i++)
      {
            int x;
            cout << "Nhap phan tu thu " << i << ": ";
            cin >> x;
            NODE* p = CreateNode(x);
            EnQueue(Q, p);
      }
}

Hàm xuất

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

Main.cpp

int main()
{
      LIST Q;
      Init(Q);
      Input(Q);
      Output(Q);
      cout << "\n1. Kiem tra Queue co rong khong.";
      cout << "\n2. Push phan tu vao cuoi Queue.";
      cout << "\n3. Pop phan tu dau Queue.";
      cout << "\n4. Xuat Queue.";
      cout << "\n5. Thoat.";
      cout << endl;

      while (true)
      {
            int luachon;
            do
            {
                  cout << "\nNhap lua chon: ";
                  cin >> luachon;
                  switch (luachon)
                  {
                  case 1:
                  {
                        if (IsEmpty(Q))
                              cout << "Queue rong.\n";
                        else cout << "Queue khong rong.\n";
                        break;
                  }
                  case 2:
                  {
                        int x;
                        cout << "Nhap phan tu can push: ";
                        cin >> x;
                        NODE* p = CreateNode(x);
                        EnQueue(Q, p);
                        Output(Q);
                        break;
                  }
                  case 3:
                  {
                        int saved; 
                        if (DeQueue(Q, saved))
                        {
                              cout << "Phan tu da pop: " << saved << endl;
                              Output(Q);
                        }
                        else
                        {
                              cout << "Queue rong.\n";
                        }
                        break;
                  }
                  case 4:
                  {
                        Output(Q);
                        break;
                  }
                  case 5:
                  {
                        exit(1);
                        break;
                  }
                  }

            } while (luachon < 1 || luachon > 5);
      }
      system("pause");
      return 0;
}

Nhận xét

Đăng nhận xét