HÀNG ĐỢI QUEUE
CÁC CHỦ ĐỀ
BÀI MỚI NHẤT
MỚI CẬP NHẬT

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.

test php

banquyen png
Bài viết này được đăng tại freetuts.net, không được copy dưới mọi hình thức.

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.

Bài viết này được đăng tại [free tuts .net]

/* 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é!!!

Cùng chuyên mục:

Tìm các số chẵn lẻ bằng Queue và Stack

Tìm các số chẵn lẻ bằng Queue và Stack

Để làm được bài này các bạn cần có kiến thức về cấu trúc Queue…

Cài đặt hàng đợi Queue bằng danh sách liên kết

Cài đặt hàng đợi Queue bằng danh sách liên kết

Chúng ta sẽ cùng nhau tìm hiểu về cách khởi tạo cấu trúc dữ liệu…

Hàng đợi Queue là gì? Cấu trúc dữ liệu và các cách cài đặt Queue

Hàng đợi Queue là gì? Cấu trúc dữ liệu và các cách cài đặt Queue

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc lưu trữ…

Bài tập kiểm tra số nguyên tố bằng Stack

Bài tập kiểm tra số nguyên tố bằng Stack

Chúng ta sẽ cùng nhau tạo một cấu trúc Stack với danh sách liên kết…

Bài tập chuyển đổi cơ số bằng Stack

Bài tập chuyển đổi cơ số bằng Stack

Trong hướng dẫn này mình sẽ thực hiện giải một bài toán chuyển đổi cơ…

Cài đặt Stack bằng mảng một chiều

Cài đặt Stack bằng mảng một chiều

Chúng ta sẽ lần lượt thực hiện tạo các hàm cơ bản cho Stack như:…

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

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

Chúng ta sẽ thực hiện lần lượt các thao tác trong Stack sử dụng danh…

Ngăn xếp Stack là gì? Cấu trúc và cơ chế hoạt động ra sao?

Ngăn xếp Stack là gì? Cấu trúc và cơ chế hoạt động ra sao?

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc lưu trữ…

Xóa Node khỏi cây đỏ đen

Xóa Node khỏi cây đỏ đen

Chúng ta sẽ cùng nhau tìm hiểu về cách xóa một Node khỏi cây đỏ…

Thêm Node mới vào cây đỏ đen

Thêm Node mới vào cây đỏ đen

Cây đỏ đen là gì? Cấu trúc của Red-Black Tree

Cây đỏ đen là gì? Cấu trúc của Red-Black Tree

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc dữ liệu…

Xóa Node khỏi cây nhị phân tìm kiếm

Xóa Node khỏi cây nhị phân tìm kiếm

Chúng ta sẽ cùng nhau thực hiện xóa Node có 1 con, Node có 2…

Tìm Node MAX và MIN trong cây nhị phân tìm kiếm

Tìm Node MAX và MIN trong cây nhị phân tìm kiếm

Chúng ta sẽ thực hiện một vài cách tìm ra giá trị MAX và MIN…

Xuất Node con và lá trong cây nhị phân tìm kiếm

Xuất Node con và lá trong cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn cách xuất các Node con…

Tìm kiếm Node trên cây nhị phân tìm kiếm

Tìm kiếm Node trên cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn cách tìm kiếm một Node…

Duyệt cây nhị phân tìm kiếm

Duyệt cây nhị phân tìm kiếm

Chúng ta sẽ tìm hiểu lần lượt 6 cách duyệt cây nhị phân tìm kiếm:

Thêm Node vào cây nhị phân tìm kiếm

Thêm Node vào cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn về cấu trúc dữ liệu…

Cấu trúc cây nhị phân là gì? Hoạt động ra sao?

Cấu trúc cây nhị phân là gì? Hoạt động ra sao?

Trong bài này mình sẽ giới thiệu các bạn một trong các cấu trúc dữ…

Gộp hai danh sách liên kết đôi

Gộp hai danh sách liên kết đôi

Chúng ta sẽ cùng nhau tìm hiểu về cách nối hai danh sách liên kết…

Tìm kiếm phần tử k trong danh sách liên kết đôi

Tìm kiếm phần tử k trong danh sách liên kết đôi

Chúng ta sẽ cùng nhau tìm hiểu cách tìm kiếm một phần tử k trong…

Top