数组

链表

栈

队列

1、数组实现，简易版，队尾入，队首出，没有加边界限制条件。

时间复杂度比较高，入队是O(1)，出队都O(n)

  1. public class MyQueue {
  2.     private int size;   //元素个数
  3.     private int[] data;  //存储元素的数组
  5.     public MyQueue(int cap){
  6.         this.size = 0;
  7.         this.data = new int[cap];
  8.     }
  10.     //入队
  11.     public void push(int n){
  12.         if(size == data.length){
  13.             resize();
  14.         }
  15.         data[size] = n;
  16.         size++;
  17.     }
  19.     //扩容，每次扩大2倍
  20.     private void resize() {
  21.         int[] temp = new int[data.length * 2];
  22.         for (int i = 0; i < data.length; i++) {
  23.             temp[i] = data[i];
  24.         }
  25.         this.data = temp;
  26.     }
  27.     //出队,从对首出，这样每出一次都需要移动一次数组
  28.     public int pop(){
  29.         if(size == 0){
  30.             return -1;
  31.         }
  32.         int re = data[0];
  33.         for (int i = 0; i < size - 1; i++) {
  34.             data[i] = data[i + 1];
  35.         }
  36.         size--;
  37.         return re;
  38.     }
  40.     //测试
  41.     public static void main(String[] args) {
  42.         MyQueue myQueue = new MyQueue(10);
  43.         System.out.println(myQueue.size);
  44.         myQueue.push(12);
  45.         myQueue.push(45);
  46.         myQueue.push(25);
  47.         myQueue.push(66);
  48.         myQueue.push(36);
  49.         for (int i = 0; i <5; i++) {
  50.             System.out.println(myQueue.pop());
  51.             System.out.println("size:"+ myQueue.size);
  52.         }
  53.         System.out.println(myQueue.size);
  54.     }
  57. }

2、数组实现，升级版，引入头指针，提升时间复杂度

上一种实现里，有一个size表示元素个数，可以表示队列的尾结点，这里引入一个表示头结点的指针，每次入队出队直接操作头尾指针位置的元素，时间复杂度都是O(1)，当尾结点移动到数组尾部时需要进行移动数据，时间复杂度为O(n)，也就是说，假使初始化大小为100，那么前面100次push的时间复杂度都是O(1)，再次进行push的时候进行移动元素或者扩容，时间复杂度为O(n)，等于是100次O(1)+1次O(n)。整体来说有不少提升

  1. public class MyQueuePlus {
  2.     private int[] data;
  3.     private int head;  //头指针，用于出队
  4.     private int tail;  //尾指针，用于入队
  6.     public MyQueuePlus(int cap){
  7.         this.data = new int[cap];
  8.         this.head = 0;
  9.         this.tail = 0;
  10.     }
  12.     //入队
  13.     public void push(int n){
  14.         //判断扩容
  15.         if(tail == data.length){
  16.             resize();
  17.         }
  18.         data[tail] = n;
  19.         tail++;
  20.     }
  22.     //扩容，出站后数组前面的位置就空出来了，如果元素个数不多，不需要扩容，只需重新整理一下队列中的元素位置即可
  23.     private void resize() {
  24.         int n = tail - head;
  25.         int resize = Math.max(n * 2,data.length);
  26.         int[] temp = new int[resize];
  27.         for (int i = 0; i < tail-head; i++){
  28.             temp[i] = data[head+i];
  29.         }
  30.         head = 0;
  31.         tail = n;
  32.         this.data = temp;
  33.     }
  35.     //出队
  36.     public int pop(){
  37.         return data[head++];
  38.     }
  40.     public static void main(String[] args) {
  41.         MyQueuePlus queue = new MyQueuePlus(5);
  42.         queue.push(2);
  43.         queue.push(5);
  44.         queue.push(3);
  45.         queue.push(4);
  46.         queue.pop();
  47.         queue.pop();
  48.         queue.push(8);  //尾指针已到达数组最后
  49.         queue.push(15);  //触发一次整理（扩容）
  50.         System.out.println(queue.data.length);
  51.         System.out.println(queue.head);
  52.         System.out.println(queue.tail);
  53.     }
  54. }

3、用链表实现

用链表实现比较简单，而且时间复杂度也只有O(1)，还不涉及到扩容问题，但是正因为这样，链表具有天然的扩展性，使用的时候更需要注意内存问题，只要你不限制，理论上可以占完整个内存。所以可以加在初始化的时候给一个大小，在入队列的时候进行判断一下。这里没有实现。

  1. public class MyQueueWithLinked {
  2.     private int size;  //记录节点数量
  3.     private Node head;  //头结点，用于出队
  4.     private Node tail;  //尾结点，用户入队
  6.     //初始化
  7.     public MyQueueWithLinked(){
  8.         this.size = 0;
  9.         this.head = null;
  10.         this.tail = null;
  11.     }
  13.     //入队
  14.     public void push(int n){
  15.         Node node = new Node(n);
  16.         if(size == 0){  //队列为空时
  17.             head = node;
  18.             tail = node;
  19.         }else {  //队列为空时,直接插入到队尾
  20.             tail.next = node;
  21.             tail = node;
  22.         }
  23.         size++;
  24.     }
  26.     //出队列
  27.     public int pop(){
  28.         int re;
  29.         if(size == 0){  //队列为空
  30.             re = -1;
  31.         }else {
  32.             re = head.value; //从头节点出队，
  33.             head= head.next; //将头结点指向下一个节点
  34.             size--;
  35.         }
  36.         return re;
  37.     }
  38.     //测试
  39.     public static void main(String[] args) {
  40.         MyQueueWithLinked queue = new MyQueueWithLinked();
  41.         queue.push(23);
  42.         queue.push(5);
  43.         queue.push(66);
  44.         queue.pop();
  45.         queue.push(17);
  46.         queue.push(99);
  47.         queue.push(33);
  48.         for (int i = 0; i < 5; i++) {
  49.             System.out.println(queue.pop());
  50.         }
  51.     }
  52. }
  53. //用来表示链表的节点，其实本质上来说，一个链表就是一个节点，因为永远可以通过next来找到下一个节点，直到找到所有节点。
  54. class Node{
  55.     int value;
  56.     Node next;
  58.     public Node(int value){
  59.         this.value = value;
  60.         this.next = null;
  61.     }
  62. }