Queue

Queue

Overview

First-in-first-out (FIFO—first in first out), only allows delete operations at the front of the table (front), and inserts at the back of the table (rear)

Tail

The end of the insert operation becomes the end of the line

Right

The end that performs the delete operation becomes the counterparty

Join the team

Inserting a queue element in the queue is called enqueue

Leave the team

And removing a queue element from the queue is called dequeue

One-way queue (Queue)

You can only insert data at one end and delete data at the other end.

public ArrayQueue(int c) {
        capacity = c;
        queue = (Item[]) new Object[capacity];
        front =0;
        rear = -1;
        size = 0;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isFull() {
        return size==capacity;
    }

    @Override
    public boolean isEmpty() {
        return size==0;
    }

    @Override
    public void enqueue(Item i) {
        if (isFull()){
            throw new IllegalArgumentException("queue is full");
        }
        queue[size++]=i;
    }

    @Override
    public Item dequeue() {
        if (isEmpty()){
            throw new IllegalArgumentException("queue is empty");
        }
        Item front = queue[0];
        for(int i =0;i<size-1;i++){
            queue[i]=queue[i+1];
        }
        size--;
        return front;
    }

    @Override
    public Item getFront() {
        if (isEmpty()){
            throw new IllegalArgumentException("queue is empty");
        }
        return queue[0];
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("queue:[");
        for(int i=0;i<size;i++){
            sb.append(queue[i]);
            if (i!=size-1){
                sb.append(", ");
            }
        }
        sb.append("]");
        return sb.toString();
    }

Circular queue

public class ArrayQueue<Item> implements Queue<Item>{
    private int capacity;//capacity
    private Item[] queue;
    private int front;//front end
    private int rear;//back end
    private int size;//The total amount of actual elements in the queue

    public ArrayQueue(int c) {
        capacity = c;
        queue = (Item[]) new Object[capacity];
        front = 0;
        rear = -1;
        size = 0;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isFull() {
        return size==capacity;
    }

    @Override
    public boolean isEmpty() {
        return size==0;
    }

    @Override
    public void enqueue(Item i) {
        if (isFull()){
            throw new IllegalArgumentException("queue is full");
        }
        if (rear==capacity-1){//reach the end of the queue
            rear = -1;
        }
        queue[++rear]=i;
        size++;
    }

    @Override
    public Item dequeue() {
        if (isEmpty()){
            throw new IllegalArgumentException("queue is empty");
        }
        Item i = queue[front];
        queue[front] = null;
        front++;
        if (front == capacity){
            front=0;
        }
        size--;
        return i;
    }

    @Override
    public Item peekFront() {
        if (isEmpty()){
            throw new IllegalArgumentException("queue is empty");
        }
        return queue[front];
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("queue:[");
        if (front<=rear){
            for(int i=front;i<=rear;i++){
                sb.append(queue[i]);
                if (i!=rear){
                    sb.append(", ");
                }
            }
        }else{
            for(int i=front;i<=capacity-1;i++){
                sb.append(queue[i]);
                sb.append(", ");
            }
            for(int i=0;i<=rear;i++){
                sb.append(queue[i]);
                if (i!=rear){
                    sb.append(", ");
                }
            }
        }
        sb.append("]");
        return sb.toString();
    }
}

Deque

Each end can insert data and delete data operations.

Reference: https://cloud.tencent.com/developer/article/1437147 Queue-Cloud + Community-Tencent Cloud