队列循环数组循环

Question

假设我有一个大小为[10]的数组，当该数组被填满时，我想实现一个FIFO结构，而不是它只是填满了，因此无法向数组中添加新的东西，并抛出旧的东西。

例如，如果我有一个包含汽车制造商的字符串数组，当我的数组中有10个制造商时，我希望删除最旧的条目，添加最新的条目，但要考虑kepping FIFO。我如何在这样的方法中实现它：

public void insert(String name)
{
    int a;
    a = (rear + 1) % names.length;

    if(a == front)
    {
        System.out.println("Full Queue!");
    }
    else
    {
        rear = a;
        names[rear] = name;

        if(front == -1)
        {
            front = 0;
        }

    }
}

Answer 1

我试着像你一样用后部和前部建立一个队列。稍微修改了一下你的插页。我写了一个带有一些测试的主方法。

此外，我还必须添加一个“空”标志，以检查freer==front是因为是空的还是因为是满的。

public class DummyQueue {
    int rear, front;
    String[] names;
    boolean empty = true;

    public DummyQueue(int size) {
        names = new String[size];
    }

    public void insert(String name)
    {
        if(!empty && rear == front )
        {
            System.out.println("Full Queue!");
        }
        else
        {
            names[rear] = name;
            rear = (rear+1) % names.length;
        }
        empty = false;
    }

    public String deque()
    {
        if (empty) {
            System.out.println("Empty Queue!");
            return null; // demo 
        } else { 
             String response = names[front % names.length];
             front = (front + 1) % names.length;
             if (front == rear) empty = true;
             return response;
        }
    }

    public static void main(String[] args) {
        DummyQueue d = new DummyQueue(10);
        System.out.println(d.deque());
        d.insert("Element");
        System.out.println(d.deque());
        System.out.println(d.deque());
        for (int i = 0; i < 12; i++) {
            System.out.println("Adding: "+i);
            d.insert("Element "+ i);
        }
        for (int i = 0; i < 12; i++) {
            System.out.println(d.deque());
        }
    }
}

Answer 2

我建议使用LinkedList的实现

public class LinkedList {
  Node head;
  Node tail;
  final int MAX_SIZE;
  int currentSize; 

  public LinkedList(int MAX_SIZE) {
    this.head = null;
    this.tail = null;
    this.MAX_SIZE = MAX_SIZE;
    this.currentSize = 0;
  }

  public void append(String val) {
    Node n = new Node(val);

    if (currentSize < MAX_SIZE) {   
      if (head == null) {
        head = n;
        tail = n;
        return;
      }

      Node current = head;
      while (current.next != null) {
        current = current.next;
      }

      current.next = n;
      currentSize++;
    }
    else {
      head = head.next;
      currentSize--;
      append(val);
    }
  }

public class Node {
  String val;
  Node next;

  public Node(String val) {
    this.val = val;
    this.next = null;
  }
}

基本上，您持有max_size和currentsize。当currentSize达到最大值时，删除LinkedList的头部，并将该值追加到结尾。