Hỏi Đáp

      Hàng đợi (queue) là gì? Cách xây dựng hàng đợi – Góc Học IT

      Posted on by
      16
      Th4

      Queue là gì

      1. Hàng đợi (queue) là gì?

      Hàng đợi (queue) là một cấu trúc dữ liệu hoạt động theo cơ chế FIFO (First In First Out), tạm dịch là “vào trước ra trước”. Có nghĩa là phần tử nào được thêm hàng đợi trước thì sẽ được lấy ra trước.

      Có thể hình dung hàng đợi như một đoàn người xếp hàng mua vé. Người nào xếp hàng trước sẽ được mua vé trước và ra khỏi hàng để nhường vị trí cho người xếp hàng ngay phía sau.

      Có thể xem hàng đợi (queue) là một kiểu danh sách có 2 phép toán đặc trưng là:

        • Bổ sung một phần tử vào cuối danh sách (rear)
        • Loại bỏ một phần tử ở đầu danh sách (front)

      Một số thao tác thông dụng trên queue như:

      • enqueue(): thêm một phần tử vào queue.
      • dequeue(): loại bỏ một phần tử ra khỏi queue.
      • isFull(): kiểm tra queue có đầy chưa. Số lượng phần tử trong queue do người dùng quy định. Tùy trường hợp chúng ta mới cần sử dụng hàm isFull().
      • isEmpty(): kiểm tra queue có rỗng hay không.

      Trong lập trình, có 2 cách thường dùng để xây dựng queue là sử dụng mảng (array) và danh sách liên kết (linked list).

      2. Xây dựng hàng đợi bằng mảng

      Khi xây dựng queue bằng mảng thì chúng ta lưu ý một số vấn đề sau:

        • Cần có hai chỉ số front và rear để lưu chỉ số phần tử đầu và chỉ số phần tử cuối trong queue. Khởi tạo queue rỗng thì front = 0 và rear = -1.
        • Để thêm một phần tử vào queue, ta tăng rear lên 1 và đưa giá trị đó vào phần tử thứ rear trong mảng.
        • Để loại bỏ một phần tử khỏi queue, ta tăng front lên 1.
        • Chỉ những phần tử của mảng từ vị trí front tới rear mới được xem là các phần tử trong queue.
        • Khi front > rear thì queue đang rỗng.
        • Khi rear tăng lên hết khoảng chỉ số của mảng thì mảng đã đầy, không thể thêm phần tử vào nữa.

      #include <iostream> using namespace std; #define max 10000 int Queue[max]; int front, rear; void QueueInit(){ front = 0; rear = -1; } void enqueue(int V){ if(rear >= max-1){ cout<<“Queue is full”; }else{ rear++; Queue[rear] = V; } } int dequeue(){ if(front > rear){ cout<<“Queue is empty”; return -1; }else{ int res = Queue[front]; front++; return res; } } //print Queue void printQueue(){ if(front > rear){ cout<<“Queue is empty”; }else{ cout<<“Elements in Queue:”; for(int i=front;i<=rear;i++){ cout<<Queue[i]<<” “; } } } int main(){ //init Queue QueueInit(); //enqueue to Queue enqueue(5); enqueue(21); enqueue(10); enqueue(99); enqueue(101); //print Queue printQueue(); //dequeue from Queue cout<<endl<<“Dequeue fromt Queue:”; cout<<dequeue()<<” “; cout<<dequeue()<<endl; //print Queue after dequeue cout<<“Print Queue after dequeue”<<endl; printQueue(); system(“pause”); }

      Kết quả

      Elements in Queue:5 21 10 99 101 Dequeue fromt Queue:5 21 Print Queue after dequeue Elements in Queue:10 99 101

      Nhận xét:

      Khi sử dụng mảng để cài đặt queue, chỉ số rear và front chỉ tăng lên chứ không giảm đi, kể cả khi lấy các phần tử ra khỏi hàng đợi. Chỉ có các phần tử từ vị trí front tới rear là thuộc queue. Các phần tử từ vị trí 0 tới front-1 bị lãng phí.

      Hơn nữa, nếu chỉ số rear tăng lên vượt quá số lượng phần tử cho phép trong mảng thì queue cũng bị tràn, không thể thêm phần tử vào queue nữa.

      Chúng ta có thể sử dụng danh sách liên kết để cài đặt queue nhằm khắc phục các khuyết điểm trên.

      3. Xây dựng hàng đợi bằng danh sách liên kết

      Khi sử dụng danh sách liên kết đơn để xây dựng queue, nếu muốn thêm một phần tử vào queue thì ta thêm vào cuối danh sách. Nếu muốn lấy một phần tử ra khỏi queue thì ta hủy phần tử đầu danh sách.

      #include <iostream> using namespace std; struct node{ int data; node *next; }; node * front; node *rear; void QueueInit(){ front = NULL; rear = NULL; } void enqueue(int V){ node *p; p = new node; p->data = V; p->next = NULL; if (front!=NULL){ rear->next = p; }else{ front = p; } rear = p; } int dequeue(){ if (front == NULL){ cout<<“Queue is empty”; return -1; }else{ int res = front->data; node *p = front->next; delete front; front = p; if(front == NULL){ rear = NULL; } return res; } } //print Queue void printQueue(){ node *p; p = front; cout<<“Elements in Queue:”; while (p!= NULL){ cout<<p->data<<” “; p = p->next; } } int main(){ //init Queue QueueInit(); //enqueue to Queue enqueue(5); enqueue(21); enqueue(10); enqueue(99); enqueue(101); //print Queue printQueue(); //dequeue from Queue cout<<endl<<“Dequeue fromt Queue:”; cout<<dequeue()<<” “; cout<<dequeue()<<endl; //print Queue after dequeue cout<<“Print Queue after dequeue”<<endl; printQueue(); system(“pause”); }

      Kết quả

      Elements in Queue:5 21 10 99 101 Dequeue fromt Queue:5 21 Print Queue after dequeue Elements in Queue:10 99 101 Bài trước và bài sau trong môn học<< Ngăn xếp (stack) là gì? Cách xây dựng ngăn xếpCấu trúc dữ liệu dạng cây là gì? Đặc điểm của cây nhị phân (Binary Tree) >>