Helpex - Trao đổi & giúp đỡ Đăng nhập

Hàng đợi là gì?

Hôm nay, tôi sẽ trình bày về hàng đợi, là một cấu trúc dữ liệu tuyến tính. Hoạt động của hàng đợi rất trực quan và dễ hiểu, vì nó hoạt động giống như một hàng đợi thông thường (tức là trong cửa hàng tạp hóa).

Không giống như các ngăn xếp tuân theo nguyên tắc LIFO (Vào trước, Xuất trước), một hàng đợi tuân theo nguyên tắc FIFO (Vào trước, Ra trước). Nói cách khác, " Trong cấu trúc dữ liệu hàng đợi, chúng tôi loại bỏ mục ít được chèn gần đây nhất."

Nếu bạn nhầm lẫn, chỉ cần so sánh cấu trúc dữ liệu với một dòng tại cửa hàng tạp hóa. Ai đã chờ đợi lâu nhất nên được giải quyết trước.

Có bốn hoạt động cơ bản mà hàng đợi nên hỗ trợ:

  •  enqueue(): Phương thức enqueue thêm một mục vào hàng đợi.
  •  dequeue(): Phương thức dequeue loại bỏ mục ít được chèn gần đây nhất khỏi hàng đợi.
  •  front(): Phương thức phía trước trả về mục ở phía trước hàng đợi (mục tiếp theo sẽ bị xóa khi gọi phương thức dequeue)
  •  rear(): Phương thức phía sau trả về mục ở cuối hàng đợi, mục được chèn gần đây nhất.

Ngoài bốn thao tác cơ bản này, chắc chắn chúng ta cũng sẽ được hưởng lợi từ một số phương pháp trợ giúp:

  •  size(): Trả lại số lượng mục trong hàng đợi.
  •  isFull(): Đúng nếu hàng đợi đã đầy.
  •  isEmpty(): Đúng nếu hàng đợi trống.

Chúng tôi cũng sẽ cần một số biến riêng, cả để theo dõi các vị trí trong hàng đợi và một mảng bên trong cho hàng đợi thực tế:

  •  front: Vị trí hiện tại của phần tử phía trước.
  •  rear: Vị trí hiện tại của phần tử phía sau.
  •  size: Kích thước hiện tại của hàng đợi (số lượng mục).
  •  array: Một mảng bên trong, chứa các mục thực tế trong hàng đợi.

Chúng tôi cũng sẽ làm cho lớp của chúng tôi chung chung, tránh các ví dụ chung mà bạn chỉ có thể chèn các “đối tượng” int gốc vào Hàng đợi.

Một khung mã cho hàng đợi của chúng tôi được trình bày bên dưới. Bộ xương được bình luận nhiều.

package queue;

/**
 * Implementation of a Queue.
 * The inner array acts as a Ring Buffer, which makes this a circular queue.
 */
public class Queue<T> {

    /**
     * Position of the front element
     */
    private int front;
    /**
     * Position of the rear element
     */
    private int rear;
    /**
     * Size, number of elements in the queue
     */
    private int size;
    /**
     * Inner array, the actual queue.
     */
    private T[] arr;

    /**
     * Constructor, init. array and positions
     *
     * @param size The size of the queue.
     */
    public Queue(int size) {
    }

    /**
     * Placing item x in the queue.
     *
     * @throws IllegalStateException Queue is full
     */
    public void enqueue(T x) {

    }

    /**
     * Removing the front element from the queue.
     *
     * @return The front element of the queue
     * @throws java.util.NoSuchElementException Queue is empty
     */
    public T dequeue() {

    }

    /**
     * @return The front element of the queue.
     * @throws java.util.NoSuchElementException Queue is empty
     */
    public T front() {

    }

    /**
     * @return The rear element of the queue
     * @throws java.util.NoSuchElementException Queue is empty.
     */
    public T rear() {

    }

    /**
     * @return True if queue is empty (size = 0), false otherwise.
     */
    public boolean isEmpty() {

    }

    /**
     * @return True if queue is full (size = arr.length), false otherwise.
     */
    public boolean isFull() {

    }

    /**
     * @return Size (number of elements).
     */
    public int size() {

    }
}


Nếu bạn đọc các bình luận của lớp, bạn có thể nhận thấy rằng hai thuật ngữ mới đã được giới thiệu: Ring BufferCircular Queue.

Chúng tôi muốn mảng bên trong của chúng tôi hoạt động như một bộ đệm vòng, có nghĩa là nếu phía trước hoặc phía sau đạt đến vị trí cuối cùng của mảng, chúng tôi sẽ kết nối lại nó trở lại đầu mảng.

Để giải thích lý do tại sao chúng ta nên tạo một hàng đợi tròn, trước tiên chúng ta sẽ giải thích vấn đề chúng ta sẽ gặp phải nếu chúng ta chỉ tạo một hàng đợi tuyến tính.

Giả sử bạn có một hàng đợi có thể chứa tổng cộng năm phần tử, các thao tác sau được thực hiện trên hàng đợi:

  • enqueue (1). Phía trước = 0, phía sau = 0.
  • enqueue (2). Phía trước = 0, phía sau = 1.
  • enqueue (3). Phía trước = 0, phía sau = 2.
  • dequeue (). Phía trước = 1, phía sau = 2.
  • dequeue (). Phía trước = 2, phía sau = 2.
  • enqueue (4). Phía trước = 2, phía sau = 3.
  • enqueue (5). Phía trước = 2, phía sau = 4.

Sau khi các thao tác đó được thực thi, hàng đợi sẽ trông như thế này:

Như bạn thấy, có 2 vị trí có sẵn trong hàng đợi, chỉ số 0 và 1.
Nhưng, nếu hàng đợi không phải là hình tròn, điều gì sẽ xảy ra nếu chúng ta cố gắng xếp số 6 vào hàng đợi

Nếu bạn đoán rằng hàng đợi sẽ báo lại là đã đầy, bạn đã đúng!
Để giải quyết vấn đề này, chúng ta cần tạo hàng đợi theo vòng tròn. Chúng tôi muốn cả phía trước và phía sau đặt lại về vị trí 0 nếu đã đến cuối hàng (giả sử hàng đợi chưa đầy).

Bây giờ, hãy hoàn thành khung mã của chúng ta và viết một hàng đợi vòng tròn. Hãy tham khảo các ý kiến ​​để làm rõ hơn.

package queue;

import java.util.NoSuchElementException;

/**
 * Implementation of a Queue.
 * The inner array acts as a Ring Buffer, which makes this a circular queue.
 *
 * @author Anders Engen Olsen
 */
public class Queue<T> {

    /**
     * Position of the front element
     */
    private int front;
    /**
     * Position of the rear element
     */
    private int rear;
    /**
     * Size, number of elements in the queue
     */
    private int size;
    /**
     * Inner array, the actual queue.
     */
    private T[] arr;

    /**
     * Constructor, init. array and positions
     *
     * @param size The size of the queue.
     */
    public Queue(int size) {
        front = rear = -1;
        this.size = 0;
        arr = (T[]) new Object[size];
    }

    /**
     * Placing item x in the queue.
     *
     * @throws IllegalStateException Queue is full
     */
    public void enqueue(T x) {
        if (isFull())
            throw new IllegalStateException("Queue is full");

        if (isEmpty()) {
            front = rear = 0;
            arr[0] = x;
        } else {
            rear++;
            if (rear > arr.length - 1)
                rear = 0;
            arr[rear] = x;
        }

        size++;
    }

    /**
     * Removing the front element from the queue.
     *
     * @return The front element of the queue
     * @throws java.util.NoSuchElementException Queue is empty
     */
    public T dequeue() {
        if (isEmpty())
            throw new NoSuchElementException("Queue is empty");

        // Storing current front object.
        if (front > arr.length - 1)
            front = 0;
        T val = arr[front];

        // Updating the front position.
        front++;

        // Decrease size
        size--;

        return val;
    }

    /**
     * @return The front element of the queue.
     * @throws java.util.NoSuchElementException Queue is empty
     */
    public T front() {
        if (isEmpty())
            throw new NoSuchElementException("Queue is empty");

        return arr[front];
    }

    /**
     * @return The rear element of the queue
     * @throws java.util.NoSuchElementException Queue is empty.
     */
    public T rear() {
        if (isEmpty())
            throw new NoSuchElementException("Queue is empty");

        return arr[rear];
    }

    /**
     * @return True if queue is empty (size = 0), false otherwise.
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * @return True if queue is full (size = arr.length), false otherwise.
     */
    public boolean isFull() {
        return size == arr.length;
    }

    /**
     * @return Size (number of elements).
     */
    public int size() {
        return size;
    }
}


Tôi cũng đã viết một bài kiểm tra đơn vị đơn giản trong JUnit.

import org.junit.Before;
import org.junit.Test;

import static org.junit.Assert.*;

import queue.Queue;

import java.util.NoSuchElementException;

public class QueueTest {

    private Queue<Integer> queue;

    @Before
    public void setUp() {
        queue = new Queue<>(5);
    }

    @Test
    public void testEmptyQueueReturnsTrue() {
        assertTrue(queue.isEmpty());
    }

    @Test
    public void testEmptyQueueHasSizeZero() {
        assertEquals(0, queue.size());
    }

    @Test(expected = NoSuchElementException.class)
    public void testDequeueEmptyQueueThrowsException() {
        queue.dequeue();
    }

    @Test(expected = NoSuchElementException.class)
    public void testGetFrontEmptyQueueThrowsException() {
        queue.front();
    }

    @Test(expected = NoSuchElementException.class)
    public void testGetRearEmptyQueueThrowsException() {
        queue.rear();
    }

    @Test(expected = IllegalStateException.class)
    public void testExceptionThrownWhenFull() {
        for (int i = 0; i < 10; i++) {
            queue.enqueue(i);
        }
    }

    @Test
    public void testQueueWrappingAround() {
        for (int i = 1; i <= 3; i++) {
            queue.enqueue(i);
        }

        assertEquals(1, (int) queue.dequeue());
        assertEquals(2, (int) queue.dequeue());

        for (int i = 4; i <= 6; i++) {
            queue.enqueue(i);
        }

        assertEquals(3, (int) queue.front());
        assertEquals(6, (int) queue.rear());

        for (int i = 3; i <= 6; i++) {
            assertEquals(i, (int) queue.dequeue());
        }

        assertTrue(queue.isEmpty());
    }


    @Test
    public void testInsertTwoElementsAndDequeue() {
        queue.enqueue(1);
        queue.enqueue(2);

        assertEquals(1, (int) queue.dequeue());
        assertEquals(2, (int) queue.dequeue());
    }

}


Chúc bạn viết mã vui vẻ!



Nếu bạn thích bài viết này và muốn tìm hiểu thêm về Bộ sưu tập Java, hãy xem bộ sưu tập hướng dẫn và bài viết này  về tất cả mọi thứ về Bộ sưu tập Java.

13 hữu ích 0 bình luận 12k xem chia sẻ

Có thể bạn quan tâm

loading