Hàng đợi là một cấu trúc dữ liệu tuyến tính, trong đó thứ tự hoạt động là FIFO (nhập trước xuất trước).
Mảng là một cấu trúc dữ liệu chứa các phần tử của cùng một kiểu dữ liệu, được lưu trữ ở vị trí bộ nhớ liên tục.
Trong hàng đợi, các thao tác chèn và xóa như được thực hiện ở hai đầu đối diện của hàng đợi. Việc triển khai phức tạp hơn một chút so với ngăn xếp.
Trong triển khai mảng hàng đợi, chúng ta tạo một hàng đợi mảng có kích thước n với hai biến đầu và cuối.
Bây giờ, ban đầu, mảng trống, tức là cả phần trên và phần cuối đều ở 0 chỉ mục của mảng. Và khi các phần tử được thêm vào hàng đợi (chèn) giá trị của biến cuối được tăng lên. Giá trị của phần cuối có thể tăng lên đến n tức là độ dài tối đa của một mảng.
Khi nào các phần tử sẽ bị xóa khỏi hàng đợi (xóa) , giá trị của biến hàng đầu được tăng lên. Giá trị của phần đầu có thể lên đến giá trị của phần cuối.
Thực hiện hoạt động hàng đợi
Yêu cầu - Là thao tác thêm các phần tử vào hàng đợi. Trước khi thêm các phần tử vào hàng đợi, chúng ta sẽ kiểm tra xem hàng đợi đã đầy hay chưa. Điều kiện để kiểm tra nó kết thúc, nếu nó nhỏ hơn n thì chúng ta có thể lưu trữ các phần tử ở queue [end]. Và tăng kết thúc bằng 1.
Điều kiện tràn là khi mảng đầy tức là end ==n.
Dequeue - Là thao tác xóa các phần tử của hàng đợi. Trước khi xóa các phần tử của hàng đợi, chúng ta sẽ kiểm tra xem hàng đợi có trống hay không. Điều kiện để kiểm tra xem hàng đợi có trống hay không, giá trị của đầu và cuối được kiểm tra. Nếu đầu ==cuối mảng trống.
Nếu có phần tử thì chúng ta sẽ dequeue mảng. Bằng cách dịch chuyển tất cả các phần tử ở bên trái của mảng.
Mặt trước - trích xuất phần tử đầu tiên của hàng đợi, tức là mảng [top]. Thao tác này chỉ có thể được thực hiện khi mảng không trống.
Hiển thị - Thao tác này hiển thị tất cả các phần tử của hàng đợi. Tức là lướt qua hàng đợi.
Thuật toán
ENQUEUE : Step 1 : if (end == n), print : “OVERFLOW”. Exit Step 2 : queue[end] = data and end++ DEQUEUE : Step 1 : If (top == 0), print : “empty Queue”. Exit Step 2 : shift all elements one position left. End-- ;
Ví dụ
#include <bits/stdc++.h>
using namespace std;
struct Queue {
int top, end, n;
int* queue;
Queue(int c){
top = end = 0;
n = c;
queue = new int;
}
~Queue() { delete[] queue;
}
void Enqueue(int data){
if (n == end) {
printf("\nQueue is full\n");
return;
}
else {
queue[end] = data;
end++;
}
return;
}
void Dequeue(){
if (top == end) {
printf("\nQueue is empty\n");
return;
}
else {
for (int i = 0; i < end - 1; i++) {
queue[i] = queue[i + 1];
}
end--;
}
return;
}
void Display(){
int i;
if (top == end) {
printf("\nQueue is Empty\n");
return;
}
for (i = top; i < end; i++) {
printf(" %d <-- ", queue[i]);
}
return;
}
void Front(){
if (top == end) {
printf("\nQueue is Empty\n");
return;
}
printf("\nFront Element is: %d", queue[top]);
return;
}
};
int main(void){
Queue q(4);
q.Display();
q.Enqueue(12);
q.Enqueue(89);
q.Enqueue(65);
q.Enqueue(34);
q.Display();
q.Enqueue(92);
q.Display();
q.Dequeue();
q.Dequeue();
q.Display();
q.Front();
return 0;
} Đầu ra
Queue is Empty 12 <-- 89 <-- 65 <-- 34 <-- Queue is full 12 <-- 89 <-- 65 <-- 34 <-- 65 <-- 34 <-- Front Element is: 65