Chào ace, bài này chúng ta sẽ tìm hiểu về Queue và cài đặt Queue bằng mảng một chiều trong series tự học về cấu trúc dữ liệu(CTDL) và giải thuật, sau đây cafedev sẽ giới thiệu và chia sẻ chi tiết(khái niệm, độ phức tạp, ứng dụng của nó, code ví dụ…) về nó thông qua các phần sau.
Giống với Stack (ngăn xếp), thì Queue (hàng đợi) cũng là một cấu trúc dữ liệu tuyến tính tuân theo một thứ tự cụ thể mà trong đó các phép thao tác được thực hiện. Thứ tự trong Queue là First In First Out – Vào trước Ra trước. Một ví dụ điển hình về Queue là một hàng người đang đợi ở trước quầy thanh toán trong siêu thị, khi đó ai là người đến trước, đứng trước ở trong hàng, sẽ được thanh toán xong trước.
Sự khác biệt giữa Stack và Queue được thể hiện khi thực hiện thao tác xóa phần tử. Trong một Stack, chúng ta sẽ xóa phần tử mới được chèn thêm vào gần đây nhất. Còn trong một Queue, chúng ta sẽ xóa phần tử mà đã được chèn thêm vào Queue lâu nhất rồi.
Nội dung chính
1. Các thao tác có thể thực hiện trên Queue
Dưới đây là các phép thao tác dữ liệu cơ bản có thể thực hiện được trên Queue:
1. Enqueue
Chèn thêm một phần tử vào Queue. Nếu Queue đã đầy, lúc này đã đạt đến điều kiện tràn cận trên của Queue, không thể chèn thêm phần tử mới vào nữa.
2. Dequeue:
Xóa một phần tử khỏi Queue. Các phần tử khi được xóa sẽ được đưa ra khỏi Queue theo cùng một thứ tự như khi chúng được đẩy vào trong Queue. Nếu Queue rỗng mà ta vẫn cố tình thực hiện xóa phần tử thì lúc này điều kiện tràn cận dưới của Queue sẽ được kích hoạt.
3. Front:
Lấy ra phần tử nằm ở đầu Queue
4. Rear:
Lấy ra phần tử nằm ở cuối Queue
2. Ứng dụng của Queue
Queue được sử dụng khi mọi thứ không cần phải được xử lý ngay lập tức, mà phải được xử lý theo thử tứ First In First Out – Vào Trước Ra Trước giống như thuật toán BFS – Breadth First Search (tìm kiếm theo chiều rộng). Thuộc tính này của Queue làm cho nó vô cùng hữu dụng trong các loại tình huống sau:
1. Khi một tài nguyên được chia sẻ giữa nhiều đối tượng có nhu cầu. Ví dụ: Quá trình lập lịch CPU, quá trình lập lịch đĩa.
2. Khi dữ liệu được truyền một cách bất đồng bộ (dữ liệu không nhất thiết phải được nhận ở cùng tỷ lệ như khi được gửi) giữa hai tiến trình (process). Ví dụ: các IO Buffers, pipes, file IO, v.v…
3. Cài đặt Queue bằng mảng một chiều
Để cài đặt Queue, chúng ta cần theo dõi hai chỉ số, đó là front và rear. Chúng ta sẽ enqueue – chèn thêm một phần tử vào rear và dequeue – xóa đi một phần tử khỏi front. Nếu chúng ta chỉ tăng các chỉ số front và rear, thì có thể một vấn đề sẽ xảy ra, đó là chỉ số front có thể đạt đến mức cuối mảng. Giải pháp cho vấn đề này là tăng front và rear theo cách xoay vòng.
Dưới đây là các đoạn code ví dụ mô tả cách cài đặt một queue, và các thao tác xử lý dữ liệu trên queue:
CÁC ĐOẠN CODE VÍ DỤ ĐƯỢC VIẾT BẰNG C++ C JAVA PYTHON3 C#
C++
// CPP program for array
// implementation of queue
#include <bits/stdc++.h>
using namespace std;
// A structure to represent a queue
class Queue {
public:
int front, rear, size;
unsigned capacity;
int* array;
};
// function to create a queue
// of given capacity.
// It initializes size of queue as 0
Queue* createQueue(unsigned capacity)
{
Queue* queue = new Queue();
queue->capacity = capacity;
queue->front = queue->size = 0;
// This is important, see the enqueue
queue->rear = capacity - 1;
queue->array = new int[(
queue->capacity * sizeof(int))];
return queue;
}
// Queue is full when size
// becomes equal to the capacity
int isFull(Queue* queue)
{
return (queue->size == queue->capacity);
}
// Queue is empty when size is 0
int isEmpty(Queue* queue)
{
return (queue->size == 0);
}
// Function to add an item to the queue.
// It changes rear and size
void enqueue(Queue* queue, int item)
{
if (isFull(queue))
return;
queue->rear = (queue->rear + 1)
% queue->capacity;
queue->array[queue->rear] = item;
queue->size = queue->size + 1;
cout << item << " enqueued to queue\n";
}
// Function to remove an item from queue.
// It changes front and size
int dequeue(Queue* queue)
{
if (isEmpty(queue))
return INT_MIN;
int item = queue->array[queue->front];
queue->front = (queue->front + 1)
% queue->capacity;
queue->size = queue->size - 1;
return item;
}
// Function to get front of queue
int front(Queue* queue)
{
if (isEmpty(queue))
return INT_MIN;
return queue->array[queue->front];
}
// Function to get rear of queue
int rear(Queue* queue)
{
if (isEmpty(queue))
return INT_MIN;
return queue->array[queue->rear];
}
// Driver code
int main()
{
Queue* queue = createQueue(1000);
enqueue(queue, 10);
enqueue(queue, 20);
enqueue(queue, 30);
enqueue(queue, 40);
cout << dequeue(queue)
<< " dequeued from queue\n";
cout << "Front item is "
<< front(queue) << endl;
cout << "Rear item is "
<< rear(queue) << endl;
return 0;
} C
// C program for array implementation of queue
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
// A structure to represent a queue
struct Queue {
int front, rear, size;
unsigned capacity;
int* array;
};
// function to create a queue
// of given capacity.
// It initializes size of queue as 0
struct Queue* createQueue(unsigned capacity)
{
struct Queue* queue = (struct Queue*)malloc(
sizeof(struct Queue));
queue->capacity = capacity;
queue->front = queue->size = 0;
// This is important, see the enqueue
queue->rear = capacity - 1;
queue->array = (int*)malloc(
queue->capacity * sizeof(int));
return queue;
}
// Queue is full when size becomes
// equal to the capacity
int isFull(struct Queue* queue)
{
return (queue->size == queue->capacity);
}
// Queue is empty when size is 0
int isEmpty(struct Queue* queue)
{
return (queue->size == 0);
}
// Function to add an item to the queue.
// It changes rear and size
void enqueue(struct Queue* queue, int item)
{
if (isFull(queue))
return;
queue->rear = (queue->rear + 1)
% queue->capacity;
queue->array[queue->rear] = item;
queue->size = queue->size + 1;
printf("%d enqueued to queue\n", item);
}
// Function to remove an item from queue.
// It changes front and size
int dequeue(struct Queue* queue)
{
if (isEmpty(queue))
return INT_MIN;
int item = queue->array[queue->front];
queue->front = (queue->front + 1)
% queue->capacity;
queue->size = queue->size - 1;
return item;
}
// Function to get front of queue
int front(struct Queue* queue)
{
if (isEmpty(queue))
return INT_MIN;
return queue->array[queue->front];
}
// Function to get rear of queue
int rear(struct Queue* queue)
{
if (isEmpty(queue))
return INT_MIN;
return queue->array[queue->rear];
}
// Driver program to test above functions./
int main()
{
struct Queue* queue = createQueue(1000);
enqueue(queue, 10);
enqueue(queue, 20);
enqueue(queue, 30);
enqueue(queue, 40);
printf("%d dequeued from queue\n\n",
dequeue(queue));
printf("Front item is %d\n", front(queue));
printf("Rear item is %d\n", rear(queue));
return 0;
}
JAVA
// Java program for array
// implementation of queue
// A class to represent a queue
class Queue {
int front, rear, size;
int capacity;
int array[];
public Queue(int capacity)
{
this.capacity = capacity;
front = this.size = 0;
rear = capacity - 1;
array = new int[this.capacity];
}
// Queue is full when size becomes
// equal to the capacity
boolean isFull(Queue queue)
{
return (queue.size == queue.capacity);
}
// Queue is empty when size is 0
boolean isEmpty(Queue queue)
{
return (queue.size == 0);
}
// Method to add an item to the queue.
// It changes rear and size
void enqueue(int item)
{
if (isFull(this))
return;
this.rear = (this.rear + 1)
% this.capacity;
this.array[this.rear] = item;
this.size = this.size + 1;
System.out.println(item
+ " enqueued to queue");
}
// Method to remove an item from queue.
// It changes front and size
int dequeue()
{
if (isEmpty(this))
return Integer.MIN_VALUE;
int item = this.array[this.front];
this.front = (this.front + 1)
% this.capacity;
this.size = this.size - 1;
return item;
}
// Method to get front of queue
int front()
{
if (isEmpty(this))
return Integer.MIN_VALUE;
return this.array[this.front];
}
// Method to get rear of queue
int rear()
{
if (isEmpty(this))
return Integer.MIN_VALUE;
return this.array[this.rear];
}
}
// Driver class
public class Test {
public static void main(String[] args)
{
Queue queue = new Queue(1000);
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
queue.enqueue(40);
System.out.println(queue.dequeue()
+ " dequeued from queue\n");
System.out.println("Front item is "
+ queue.front());
System.out.println("Rear item is "
+ queue.rear());
}
}
PYTHON3
# Python3 program for array implementation of queue
# Class Queue to represent a queue
class Queue:
# __init__ function
def __init__(self, capacity):
self.front = self.size = 0
self.rear = capacity -1
self.Q = [None]*capacity
self.capacity = capacity
# Queue is full when size becomes
# equal to the capacity
def isFull(self):
return self.size == self.capacity
# Queue is empty when size is 0
def isEmpty(self):
return self.size == 0
# Function to add an item to the queue.
# It changes rear and size
def EnQueue(self, item):
if self.isFull():
print("Full")
return
self.rear = (self.rear + 1) % (self.capacity)
self.Q[self.rear] = item
self.size = self.size + 1
print("% s enqueued to queue" % str(item))
# Function to remove an item from queue.
# It changes front and size
def DeQueue(self):
if self.isEmpty():
print("Empty")
return
print("% s dequeued from queue" % str(self.Q[self.front]))
self.front = (self.front + 1) % (self.capacity)
self.size = self.size -1
# Function to get front of queue
def que_front(self):
if self.isEmpty():
print("Queue is empty")
print("Front item is", self.Q[self.front])
# Function to get rear of queue
def que_rear(self):
if self.isEmpty():
print("Queue is empty")
print("Rear item is", self.Q[self.rear])
# Driver Code
if __name__ == '__main__':
queue = Queue(30)
queue.EnQueue(10)
queue.EnQueue(20)
queue.EnQueue(30)
queue.EnQueue(40)
queue.DeQueue()
queue.que_front()
queue.que_rear()
C#
// C# program for array implementation of queue
using System;
namespace GeeksForGeeks {
// A class to represent a linearqueue
class Queue {
private int[] ele;
private int front;
private int rear;
private int max;
public Queue(int size)
{
ele = new int[size];
front = 0;
rear = -1;
max = size;
}
// Function to add an item to the queue.
// It changes rear and size
public void enqueue(int item)
{
if (rear == max - 1) {
Console.WriteLine("Queue Overflow");
return;
}
else {
ele[++rear] = item;
}
}
// Function to remove an item from queue.
// It changes front and size
public int dequeue()
{
if (front == rear + 1) {
Console.WriteLine("Queue is Empty");
return -1;
}
else {
Console.WriteLine(ele[front] + " dequeued from queue");
int p = ele[front++];
Console.WriteLine();
Console.WriteLine("Front item is {0}", ele[front]);
Console.WriteLine("Rear item is {0} ", ele[rear]);
return p;
}
}
// Function to print queue.
public void printQueue()
{
if (front == rear + 1) {
Console.WriteLine("Queue is Empty");
return;
}
else {
for (int i = front; i <= rear; i++) {
Console.WriteLine(ele[i] + " enqueued to queue");
}
}
}
}
// Driver code
class Program {
static void Main()
{
Queue Q = new Queue(5);
Q.enqueue(10);
Q.enqueue(20);
Q.enqueue(30);
Q.enqueue(40);
Q.printQueue();
Q.dequeue();
}
}
}
Kết quả in ra là:
10 enqueued to queue
20 enqueued to queue
30 enqueued to queue
40 enqueued to queue
10 dequeued from queue
Front item is 20
Rear item is 404. Phân tích độ phức tạp
1. Độ phức tạp về thời gian
Thao tác trên Queue Độ phức tạp về thời gian
Enque(Chèn thêm phần tử) O(1)
Deque(Xóa phần tử) O(1)
Front(Lấy ra phần tử đầu tiên của Queue) O(1)
Rear(Lấy ra phần tử cuối cùng của Queue) O(1)
2. Độ phức tạp về không gian: O(N)
N là kích thước của mảng để lưu trữ các phần tử.
* Ưu điểm của việc cài đặt Queue bằng mảng một chiều
– Dễ cài đặt
* Hạn chế của việc cài đặt Queue bằng mảng một chiều
– Mảng một chiều là kiểu cấu trúc dữ liệu tĩnh, có kích thước cố định không thể thay đổi.
– Nếu thực hiện một số lượng lớn các thao tác enqueue (chèn thêm phần tử mới) và dequeue (xóa phần tử) trên một Queue, tại một thời điểm nào đó chúng ta có thể sẽ không thể chèn thêm được các phần tử mới vào Queue, ngay cả khi Queue đang trống (có thể tránh được vấn đề này bằng cách sử dụng Circular Queue – Hàng đợi vòng tròn).
Nguồn và Tài liệu tiếng anh tham khảo:
Tài liệu từ cafedev:
- Full series tự học Cấu trúc dữ liệu và giải thuật từ cơ bản tới nâng cao tại đây nha.
- Ebook về Cấu trúc dữ liệu và giải thuật tại đây.
- Các series tự học lập trình khác
Nếu bạn thấy hay và hữu ích, bạn có thể tham gia các kênh sau của cafedev để nhận được nhiều hơn nữa:
Chào thân ái và quyết thắng!
 và giải thuật,){kind=link}