Document

Hàng đợi(Queue)

  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ế FIFO (First – In – First – Out ) - Khá giống với Stack khác nhau ở cơ chế Vào ra Dữ liệu
    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ỏ Input biểu diễn lối vào của Hàng đợi
    2. 1 con trỏ Output biểu diên lối ra của hàng đợi
    3. 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 Queue{
            int inp;
            int out;
            int s[100];
        }
  3. Các thao tác
    1. Kiểm tra tính Rỗng của stack:inp=out=-1 là rỗng và ngược lại
              bool isEmpty(){
            if(inp==out==-1)
                return true;
            return false;
        }
    2. Kiểm tra tính đầy của stack: do mình đặt size=100 nên khi inp==99 sẽ là đầy queue 
              bool isFull(){
            if(inp==99)
                return true;
            return false;
        }
    3. Thêm 1 phần tử vào queue 
              void push(int value){
            if(!isFull())
                s[++inp]=value;
            else
                cout<<"Queue Full"<< endl;
        }
    4. Lấy 1 phần tử ra khỏi stack 
              int pop(){
            if(!isEmpty()){
                int x=s[++out];
                return x;
            }
            else
            cout<<"Queue 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();// Queue rỗng trả về true và ngược lại
      2. void push(value);// thêm 1 phần tử vào cuối Queue
      3. void pop();//xóa phần tử ở đầu Queue
      4. reference front();//trả về giá trị tại đầu Queue
      5. reference back();//trả về giá trị tại cuối Queue
      6. int size();//trả về kích thước của Queue
      7. duyệt các phần tử trong Queue: :từ đầu tới cuối
                void show(queue q){
            while(!q.empty()){
                cout << q.front() << " ";
                q.pop();
            }
            cout << endl;
        }
  5. Code các bạn có thể tham khảo ở đây và ở đây