队列

数组实现

public class Queue<T> {
  // 前后两个指针
  private int front;
  private int rear;
  // 底层存储数组
  private T[] queue;
  public YKDArrayQueue(int size) {
    this.front = 0;
    this.rear = 0;
    // #1. 特别注意此处的数组泛型的写法
    this.queue = (T[]) new Object[size];
  }
  // 队列尾部添加元素
  public void add(T o) {
    this.queue[this.rear] = o;
    // 因此是循环队列，所以处理数组长度取余
    int newRear = (rear + 1) % this.queue.length;
    // 暂不考虑扩容情况
    if (newRear == this.front) {
      // 如果加入元素以后指针碰撞，则抛出越界提示
      throw new IndexOutOfBoundsException("队列已满");
    }
    this.rear = newRear;
  }
  // 删除队列头部元素
  public T remove() {
    if(this.size()==0){
      throw new IndexOutOfBoundsException("队列为空，不允许remove");
    }
    T data = this.queue[this.front];
    if (data!=null){
      this.queue[this.front] = null;
      this.front = (this.front+1)%this.queue.length;
      return data;
    } 
    return null;
  }
  // 获取队列中索引位置元素
  public T get(int i) {
    if(i<0 || i>=this.size()){
      throw new IndexOutOfBoundsException("获取队列元素，越界");
    }
    int index = (i+this.front)%this.queue.length;
    return this.queue[index];
  }
  // 获取队列的长度
  public int size() {
    if (this.rear < this.front) {
      return this.rear + this.queue.length - this.front;
    }
    return this.rear - this.front;
  }
  public String toString() {
    StringBuffer sb = new StringBuffer();
    int i = this.front;
    while (i != this.rear) {
      sb.append(this.queue[i]);
      sb.append(" ");
      i++;
    }
    return sb.toString();
  }
  public static void main(String[] args) {
    Queue<Integer> queue = new Queue<>(20);
    queue.add(10);
    queue.add(5);
    queue.add(11);
    System.out.println(queue.get(0));
    System.out.println(queue.get(2));
    System.out.println(queue.remove());
    System.out.println(queue.remove());
    System.out.println(queue.toString());
    System.out.println(queue.size());
  }
}

链表实现

Node

public class Node<T> {
  private T content;
  private Node<T> next;
  public Node() {
  }
  public Node(T content) {
    this.content = content;
  }
  public Node(T content, Node<T> next) {
    this.content = content;
    this.next = next;
  }
  public T getContent() {
    return content;
  }
  public void setContent(T content) {
    this.content = content;
  }
  public Node<T> getNext() {
    return next;
  }
  public void setNext(Node<T> next) {
    this.next = next;
  }
}

package com.youkeda;
public class LinkedQueue<T> {
  // 前后两个指针
  private Node<T> front;
  private Node<T> rear;
  private int size = 0;
  // 队列尾部添加元素
  public void add(T o) {
    Node<T> node = new Node<>(o);
    if (this.front == null) {
      this.front = node;
    } else {
      this.rear.setNext(node);
    }
    this.size++;
    this.rear = node;
  }
  // 删除队列头部元素
  public T remove() {
    if(this.front == null){
      throw new IndexOutOfBoundsException("队列为空，不能删除");
    }
    Node<T> temp = this.front;
    this.front = temp.getNext();
    temp.setNext(null);
    this.size--;
    return temp.getContent();
  }
  // 获取队列中索引位置元素
  public T get(int i) {
    if (i < 0 || i >= this.size()) {
      throw new IndexOutOfBoundsException("获取队列元素，越界");
    }
    Node<T> node = this.front;
    while(i > 0){
      node = node.getNext();
      i--;
    }
    return node.getContent();
  }
  // 获取队列的长度
  public int size() {
    return this.size;
  }
  public String toString() {
    StringBuffer sb = new StringBuffer();
    Node<T> node = this.front;
    while (node.getNext() != null) {
      sb.append(node.getContent());
      sb.append(" ");
      node = node.getNext();
    }
    return sb.toString();
  }
  public static void main(String[] args) {
    LinkedQueue<Integer> queue = new LinkedQueue<>();
    queue.add(10);
    queue.add(5);
    queue.add(11);
    System.out.println(queue.get(0));
    System.out.println(queue.get(2));
    System.out.println(queue.remove());
    System.out.println(queue.remove());
    System.out.println(queue.toString());
    System.out.println(queue.size());
  }
}

队列常见算法——滑块窗口

获取长度最小的连续子数组