Các thông tin cần thiết để biểu diễn hàng đợi bằng mảng một chiều là gì?

Để biểu diễn hàng đợi bằng mảng một chiều, cần các thông tin cần thiết sau:

1. Mảng để lưu trữ các phần tử của hàng đợi: Đây là nơi các phần tử của hàng đợi sẽ được lưu trữ.

2. Chỉ số đầu (front): Chỉ số của phần tử đầu tiên trong hàng đợi. Khi hàng đợi trống, chỉ số này thường được đặt là -1 hoặc một giá trị đặc biệt để biểu thị hàng đợi trống.

3. Chỉ số cuối (rear): Chỉ số của phần tử cuối cùng trong hàng đợi. Khi hàng đợi trống, chỉ số này cũng thường được đặt là -1 hoặc một giá trị đặc biệt tương tự.

4. Kích thước hiện tại (size): Số lượng phần tử hiện tại trong hàng đợi. Kích thước này giúp kiểm tra nhanh liệu hàng đợi có trống hay đầy hay không.

5. Kích thước tối đa (capacity): Số lượng phần tử tối đa mà hàng đợi có thể chứa. Kích thước này xác định độ lớn của mảng ban đầu.

Dưới đây là một ví dụ minh họa về cách biểu diễn hàng đợi bằng mảng một chiều trong mã giả:

class Queue:

    def __init__(self, capacity):

       self.capacity = capacity

       self.array = [None] * capacity

       self.front = -1

       self.rear = -1

       self.size = 0

    def is_empty(self):

        return self.size == 0

    def is_full(self):

        return self.size == self.capacity

    def enqueue(self, item):

        if self.is_full():

           print("Queue is full")

           return

        if self.front == -1:

           self.front = 0

       self.rear = (self.rear + 1) % self.capacity

       self.array[self.rear] = item

       self.size += 1

    def dequeue(self):

        if self.is_empty():

           print("Queue is empty")

           return None

        item = self.array[self.front]

       self.front = (self.front + 1) % self.capacity

       self.size -= 1

        if self.size == 0:

           self.front = -1

           self.rear = -1

        return item