Home > Giải thuật > Hàng đợi Queue > Cài đặt hàng đợi Queue bằng mảng một chiều
giam gia tino jpg
Kênh Youtube chính thức của freetuts, các bạn hãy sub ủng hộ mình với nhé, từ giờ mình đang làm sạch lại nội dung học tập trên kênh này. Xem kênh

Cài đặt hàng đợi Queue bằng mảng một chiều

Trong hướng dẫn này mình sẽ giới thiệu các bạn cách cài đằ hàng đợi bằng mảng một chiều. Đây là một trong những cách cơ bản để cài đặt hàng đợi Queue, được áp dụng vào các bài toán đơn giản.

Chúng ta sẽ cùng nhau tìm hiểu về cách cài đặt hàng đợi Queue bằng mảng một chiều như thế nào, sau đó mình sẽ thực hiện một chương trình nhập xuất các giá trị trong Queue.

1. Các hàm cơ bản trong hàng đợi

Trong phần này mình sẽ hướng dẫn viết một số hàm cơ bản trong Queue. Về cơ bản thì khi cài đặt Queue bằng mảng một chiều nó cũng tương tự như cài đăt Queue bằng danh sách liên kết. Chúng ta cũng sẽ cần tạo một số hàm cơ bản như Push, pop và hàm hiển thị các phần tử trong Queue. Ngoài ra còn một số hàm khác tùy thuộc vào bài toán để chúng ta tạo nó, vì như vậy sẽ tối ưu hóa được thời gian viết.

Hàm Push

Trước khi viết hàm push() để thêm phần tử vào Queue thì ta cần khai báo một mảng queue[] và cấp độ dài cho nó là 100, tùy thuộc vào bài toán chúng ta sẽ khởi tạo độ dài cho phù hợp. Cùng với đó ta cần hai biến khác đó là front và rear, đây là hai biến được khỏi tạo ban đầu là -1. Front là vị trí ban đầu của mảng, rear là vị trí hiện tại mà chúng ta xét đến trong Queue.

/* khởi tạo mảng và các biến cần thiết trong Queue */
int queue[100], n = 100, front = - 1, rear = - 1;

Sau khi đã tạo mảng và khởi tạo độ dài cho nó, ta bắt đầu vào viết hàm push().

Đầu tiên ta sẽ tạo một biến val, đây là phần tử ta sẽ thêm nó vào trong Queue. Ta sẽ bắt đầu kiểm tra xem trong phần tử đã đầy hay chưa, nếu Queue đã đầy thì ta không thể thêm phần tử vào được.

Ngược lại nếu trong Queue vẫn còn chỗ trống thì ta sẽ bắt đầu chèn phần tử vào hàng đợi, bằng cách lấy dữ liệu từ bàn phím và gán nó vào rear (vị trị hiện tại trong Queue).

/* hàm thêm phần tử vào trong Queue */
void push() {
// khởi tạo biến val và đưa nó vào trong hàng đợi
   int val;
//xét điều kiện hàng đợi đầy, nếu đầy thì không thể thêm phần tử vào được
   if (rear == n - 1)
   cout<<"Tràn hàng đợi"<<endl;
//Ngược lại nếu trong hàng đợi vẫn còn chỗ trống thì ta thực hiện thêm phần tử
   else {
      if (front == - 1)
      front = 0;
      cout<<"Chèn phần tử vào hàng đợi : "<<endl;
      //yêu cầu nhập dữ liệu từ bàn phím
      cin>>val;
      //tăng vị trí hiện tại lên một
      rear++;
      //thêm phần tử đó vào vị trí hiện tại rear
      queue[rear] = val;
   }
}

Hàm Pop

Trong phần này ta sẽ viết hàm pop() để thực hiện lấy phần tử đầu đồng thời xóa nó khỏi hàng đợi Queue, đây là một thao tác khá quan trọng vì khi thực hiện một số bài toán sẽ yêu cầu xóa phần tử trong Queue.

Cũng như các thao tác khác, ta sẽ kiểm tra xem trong Queue có tồn tại phần tử hay không, nếu Queue rỗng thì ta return và kết thúc hàm. Ngược lại nếu trong Queue tồn tại phần tử ta sẽ thực hiện lấy phần tử đó ra và xóa luôn khỏi Queue.

/* hàm xóa phần tử khỏi Queue */
void pop() {
//nếu trong hàng đợi rỗng thì không thể xóa phần tử, ta thực hiện return và kết thúc hàm
   if (front == - 1 || front > rear) {
      cout<<"Không thể xóa phần tử trong hàng đợi ";
      return ;
   } 
//Ngược lại ta sẽ thực hiện lấy phần tử đó ra và xóa luôn khỏi hàng đợi
   else {
      cout<<"Phần tử đã xóa khỏi hàng đợi là: "<< queue[front] <<endl;
      front++;;
   }
}

Hàm Print

Để có thể kiểm tra và xem được các phần tử trong Queue thì ta cần tạo một hàm đế làm việc đó, cũng tương tự như hàm pop(), ta cần kiểm tra Queue có rỗng hay không, nếu rỗng thì ta return và kết thúc hàm. Ngược lại nếu tồn tại phần tử thì ta sẽ sử dụng vòng lặp for để hiển thị lần lượt các phần tử trong Queue.

/* hàm in các phần tử trong Queue ra màn hình */
void print() {
//nếu hàng đợi rỗng ta sẽ thông báo 
   if (front == - 1)
   cout<<"Hàng đợi rỗng!!"<<endl;
//Ngược lại nếu hàng đợi có phần tử thì ta sẽ xuất lần lượt các phần tử đó ra màn hình
   else {
      cout<<"Các phần tử trong hàng đợi là: ";
      //sử dụng vòng lặp for để xuất lần lượt các phần tử
      for (int i = front; i <= rear; i++)
      cout<<queue[i]<<" ";
         cout<<endl;
   }
}

2. Ví dụ xây dựng một cấu trúc Queue

Trong phần này mình sẽ sẽ dụng một số hàm đã viết ở trên để thực hiện thêm, xóa, hiển thị phần tử trong Queue, các bạn có thể tham khảo code mình đã viết sẵn dưới đây nhé.

Full code:

#include <iostream>
using namespace std;
/* khởi tạo mảng và các biến cần thiết trong Queue */
int queue[100], n = 100, front = - 1, rear = - 1;
/* hàm thêm phần tử vào trong Queue */
void push() {
// khởi tạo biến val và đưa nó vào trong hàng đợi
   int val;
//xét điều kiện hàng đợi đầy, nếu đầy thì không thể thêm phần tử vào được
   if (rear == n - 1)
   cout<<"Tràn hàng đợi"<<endl;
//Ngược lại nếu trong hàng đợi vẫn còn chỗ trống thì ta thực hiện thêm phần tử
   else {
      if (front == - 1)
      front = 0;
      cout<<"Chèn phần tử vào hàng đợi : "<<endl;
      //yêu cầu nhập dữ liệu từ bàn phím
      cin>>val;
      //tăng vị trí hiện tại lên một
      rear++;
      //thêm phần tử đó vào vị trí hiện tại rear
      queue[rear] = val;
   }
}
/* hàm xóa phần tử khỏi Queue */
void pop() {
//nếu trong hàng đợi rỗng thì không thể xóa phần tử, ta thực hiện return và kết thúc hàm
   if (front == - 1 || front > rear) {
      cout<<"Không thể xóa phần tử trong hàng đợi ";
      return ;
   } 
//Ngược lại ta sẽ thực hiện lấy phần tử đó ra và xóa luôn khỏi hàng đợi
   else {
      cout<<"Phần tử đã xóa khỏi hàng đợi là: "<< queue[front] <<endl;
      front++;;
   }
}
/* hàm in các phần tử trong Queue ra màn hình */
void print() {
//nếu hàng đợi rỗng ta sẽ thông báo 
   if (front == - 1)
   cout<<"Hàng đợi rỗng!!"<<endl;
//Ngược lại nếu hàng đợi có phần tử thì ta sẽ xuất lần lượt các phần tử đó ra màn hình
   else {
      cout<<"Các phần tử trong hàng đợi là: ";
      //sử dụng vòng lặp for để xuất lần lượt các phần tử
      for (int i = front; i <= rear; i++)
      cout<<queue[i]<<" ";
         cout<<endl;
   }
}
/* hàm main để tạo menu và gọi các hàm đã tạo ở trên */
int main() {
   int ch;
   cout<<"1) Thêm phần tử vào Queue"<<endl;
   cout<<"2) Xóa phần tử khỏi Queue"<<endl;
   cout<<"3) Hiện thị tất cả các phần tử trong Queue"<<endl;
   cout<<"4) Thoát"<<endl;
   do {
      cout<<"Nhập lựa chọn của bạn: "<<endl;
      cin>>ch;
      switch (ch) {
         case 1: push();
         break;
         case 2: pop();
         break;
         case 3: print();
         break;
         case 4: cout<<"Kết thúc"<<endl;
         break;
         default: cout<<"Lựa chọn của bạn không đúng"<<endl;
      }
   } while(ch!=4);
   
   cout<<"\n--------------------------\n";
   cout<<"Chương trình này được đăng tại Freetuts.net";
}

Kết quả:

queue mang PNG

3. Kết luận

Như vậy là chúng ta đã tìm hiểu xong cách cài đặt Queue bằng mảng một chiều, cũng như ở bài trước ta cũng đã tìm hiểu cách cài đặt Queue bằng danh sách liên kết. Đây là hai cách cài đặt quan trọng và cơ bản nhất, tuy nhiên khi lập trình ta ưu tiên sử dụng danh sách liên kết để cài đặt, vì các thao tác push và pop sẽ được thực hiện nhanh hơn. Ở bài tiếp theo mình sẽ thực hiện một vài ví dụ sử dụng cả Queue và Stack, hãy chú ý theo dõi nhé!!!

BÀI VIẾT

notice png LIST home png HOME hot gif BÁO
LỖI
top png TOP