分析：用数组实现大小固定的栈和队列

1、实现栈结构：栈结构是先进后出，只需要一个数组和一个记录位置的变量size，当进来一个元素，size++，当出去一个元素则size--。

2、实现队列结构：队列先进先出，需要一个数组和三个变量，size记录已经进来了多少个元素，in记录刚进来的元素放置在哪个位置，out表示用户要求弹出元素所在的位置。其中size还是in与out的操作的关键信息。

实现：

栈的实现：

package stack1;

public class Stack1 {

       public static class MyStack{

           private int size;//指针位置，也表示栈已经压了多少

            private int[]arr;

           MyStack(int iniSize){//构造方法初始化数组

                arr = new int[iniSize];

             size = 0;

          }

           public void push(int num){

                if(size == arr.length){

                   throw new RuntimeException("栈下标越界！");

              }

               arr[size++] = num;

          }

           public int pop(){

               if(size == 0){

                   throw new RuntimeException("栈中已经没有元素可以弹出！");

               }

               return arr[--size];

           }

           public int peek(){

              if(size == 0){

                   throw new RuntimeException("栈中已经没有元素可以弹出！");

               }

               return arr[size];

         }

       }

       public static void main(String[] args) {

          int len = 13;

            MyStack myStack = new MyStack(len);

           for (int i = 0; i < len; i++) {

             myStack.push(i);

            }

           for (int i = 0; i < len; i++) {

             System.out.println(myStack.pop());

          }

       }

    }

 

队列的实现：

package stack1;

public class Queue1 {

       public static class MyQueue{

           private int out;//新进来的数 放这

         private int in;//用户要求弹出的数

          private int size;//已经进队列的个数

           

            private int arr[];

          public MyQueue(int iniSize){

                arr = new int[iniSize];

             size = 0;

              in = 0;

                out = 0;

           }

           public void push(int num){

                if(size==arr.length){

                 throw new RuntimeException("the queue is full!");

              }

               size++;//大小扩展一个

               arr[in] = num;//赋值

                in = in==arr.length-1 ? 0 : in+1;//如果已经到达数组末尾就重新等于0

            }

           public int pull(){

              if(size==0){

                 throw new RuntimeException("the queue is empty!");

             }

               size--;

             int t = out;//记录

                out = out==arr.length-1 ? 0 : out+1;//如果已经到达数组末尾就重新等于0

             return arr[t];

            }

           public int peek(){

              if(size==0){

                 throw new RuntimeException("the queue is empty!");

             }

               return arr[out];

          }

       }

       public static void main(String[] args) {

          int iniSize = 3;

         MyQueue myQueue = new MyQueue(iniSize);

           myQueue.push(12);

          myQueue.push(13);

          myQueue.push(15);

          System.out.println(myQueue.pull());

         System.out.println(myQueue.pull());

         System.out.println(myQueue.pull());

         myQueue.push(23);

          myQueue.push(24);

          System.out.println(myQueue.pull());

         System.out.println(myQueue.peek());

     }

    }

栈是用来存储逻辑关系为 "一对一" 数据的线性存储结构
后进去先出来。
栈的存储结构中关键的在于：存与取。
栈只能从表的一端存取数据，另一端是封闭的
在栈中，无论是存数据还是取数据，都必须遵循"先进后出(LIFO)"的原则，即最先进栈的元素最后出栈。上图 的栈来说，从图中数据的存储状态可判断出，元素 1 是最先进的栈。因此，当需要从栈中取出元素 1 时，根据"先进后出"的原则，需提前将元素 3 和元素 2 从栈中取出，然后才能成功取出元素 1。
把上图的栈立起来就是这样子的(这样或许更好理解)。
 实现一个栈的数据结构，使其具有以下方法：压栈、弹栈、取栈顶元素、判断栈是否为空以及获取栈中元素个数。下面是一个栈的入栈和出栈整个过程
栈的实现有两种方法，分别为采用数组来实现和采用链表来实现。下面分别详细介绍这两种方法。
数组实现
分析
在采用数组来实现栈的时候，栈空间是一段连续的空间。实现思路如下图所示
从上图中可以看出，可以把数组的首元素当作栈底，同时记录栈中元素的个数size，假设数组首地址为arr，压栈的操作其实是把待压栈的元素放到数组arr[size]中，然后执行size++操作；同理，弹栈操作其实是取数组arr[size-1]元素，然后执行size--操作。根据这个原理可以非常容易实现栈。
代码实现
/*** 数组使用栈** @author tian* @date 2020/4/26*/public class MyStackDemo {   public static void main(String[] args) {       ArrayStack stackDemo = new ArrayStack();       //入栈两个元素       stackDemo.push(1);       stackDemo.push(2);       System.out.println("栈顶元素：" + stackDemo.top());       System.out.println("栈大小：" + stackDemo.size());       stackDemo.pop();       System.out.println("栈第一次弹出元素");       stackDemo.pop();       System.out.println("栈第二次弹出元素");       stackDemo.pop();  }}class ArrayStack {   private ArrayList arrayList;   private int stackSize;   public ArrayStack() {       this.stackSize = 0;       this.arrayList = new ArrayList<>();  }   int size() {       return stackSize;  }   boolean isEmpty() {       return this.stackSize == 0;  }   //返回栈顶元素   T top() {       if (isEmpty()) {           return null;      }       return arrayList.get(stackSize - 1);  }   //元素出栈   T pop() {       if (stackSize > 0) {           return arrayList.get(--stackSize);      } else {           System.out.println("栈中无元素了");           return null;      }  }   //元素入栈   void push(T item) {       arrayList.add(item);       stackSize++;  }}
运行输出
链表实现
分析
在创建链表的时候经常采用一种从头结点插入新结点的方法，可以采用这种方法来实现栈，最好使用带头结点的链表，这样可以保证对每个结点的操作都是相同的，实现思路如下图所示。
在上图中，在进行压栈操作时，首先需要创建新的结点，把待压栈的元素放到新结点的数据域中，然后只需要(1)和(2)两步就实现了压栈操作(把新结点加到了链表首部)。同理，在弹栈的时候，只需要进行步骤(3)的操作就可以删除链表的第一个元素，从而实现弹栈操作。
代码实现
/*** 数组实现栈** @author tian* @date 2020/4/26*/public class NodeStackDemo {   private MyNode head;   public NodeStackDemo() {       this.head = new MyNode<>();       head.data = null;       head.next = null;  }   //判断栈是否为空   boolean isEmpty() {       return head == null;  }   //栈的大小   int size() {       int size = 0;       MyNode p = head.next;       while (p != null) {           p = p.next;           size++;      }       return size;  }   void push(T e) {       MyNode temp = new MyNode<>();       temp.data = e;       temp.next = head.next;       head.next = temp;  }   //出栈，同时返回栈顶元素   T pop() {       MyNode temp = head.next;       if (temp != null) {           head.next = temp.next;           return temp.data;      }       System.out.println("占中已经不存元素了");       return null;  }   //获取栈顶元素   T top() {       if (head.next != null) {           return head.next.data;      }       System.out.println("栈中不存在元素");       return null;  }   public static void main(String[] args) {       NodeStackDemo stackDemo = new NodeStackDemo();       stackDemo.push(1);       stackDemo.push(3);       stackDemo.push(5);       System.out.println("栈顶元素：" + stackDemo.top());       System.out.println("栈大小：" + stackDemo.size());       stackDemo.pop();       System.out.println("栈第一次弹出元素");       stackDemo.pop();       System.out.println("栈第二次弹出元素");       stackDemo.pop();       System.out.println("栈第二次弹出元素");       stackDemo.pop();  }}class MyNode {   T data;   MyNode next;}
运行结果
两种方法的对比
采用数组实现栈的优点：一个元素值占用一个存储空间；它的缺点：如果初始化申请的存储空间太大，会造成空间的浪费，如果申请的存储空间太小，后期会经常需要扩充存储空间，扩充存储空间是个费时的操作，这样会造成性能的下降。采用链表实现栈的优点：使用灵活方便，只有在需要的时候才会申请空间。它的缺点：除了要存储元素外，还需要额外的存储空间存储指针信息。
算法性能分析：这两种方法压栈与弹栈的时间复杂度都为O(1)。

队列概述
队列是一种先进先出的线性表（first in first out，简称FIFO）。它只允许在队列的一段插入数据，另一端取出数据。允许插入数据的一端叫做队尾（rear），允许删除的一段则称为队头（front）。



队列无论在实际生活中还是在开发中都是非常常见的。比如我们去银行办理业务的排号系统就是队列。消息中间件也是队列的思想。
队列ADT
下面给出队列的抽象定义，在后文中我们将以此ADT开发队列的实现。
/**
 * @author jaune
 * @since 1.0.0
 */
public interface Queue<E> {

    /**
     * 查看队列中的第一个元素，仅仅查看元素，不从队列中取出。
     * @return 队列中的第一个元素
     * @throws NoSuchElementException 队列为空时抛出
     */
    E peek();

    /**
     * 向队列中添加元素，元素添加到队尾。
     */
    void push(E e);

    /**
     * 从队列中取出第一个元素。
     * @return 队列中的第一个元素。
     * @throws NoSuchElementException 队列为空时抛出
     */
    E pop();

    /**
     * 清空队列并
     */
    void clear();

    /**
     * 队列中元素的数量，如果队列为空，则返回0
     *
     * @return 队列中元素的数量
     */
    int size();

    /**
     * 判断队列是否为空
     * @return true-空，false-非空
     */
    boolean isEmpty();

    /**
     * 判断队列是已满
     * @return true-已满，false-未满
     */
    boolean isFull();
}

使用数组实现的基本思想
定义两个指针，一个指向队头（front），一个指向队尾(rear)。



当从队列中取出元素时，front指针后移；当向队列中添加元素时rear指针后移。



当队头和队尾在同一个位置时，队列为空。



采用数组的方式实现队列的最大问题就是，当front和rear指针全部指向队列的尾部时，队列失效了。无法添加新的元素至队列中。当添加元素时因为指针指向队尾，所以出现队列已满的情况。在后面我将介绍如何处理这种情况。在本文中对这种情况不做处理。


代码实现
package com.codestd.study.queue;

import java.util.NoSuchElementException;

/**
 * 数组队列的实现
 *
 * @author jaune
 * @since 1.0.0
 */
public class ArrayQueue<T> implements Queue<T> {

    final int maxSize;
    final T[] queueArray;
    private int front = -1;
    private int rear = -1;

    public ArrayQueue(int maxSize) {
        this.maxSize = maxSize;
        this.queueArray = (T[]) new Object[maxSize];
    }

    @Override
    public T peek() {
        if (this.isEmpty()) {
            throw new NoSuchElementException("队列为空");
        }
        return this.queueArray[this.front + 1];
    }

    @Override
    public void push(T t) {
        if (this.isFull()) {
            throw new RuntimeException("队列已满，无法添加新的元素。");
        }
        this.queueArray[++this.rear] = t;
    }

    @Override
    public T pop() {
        if (this.isEmpty()) {
            throw new NoSuchElementException("队列为空");
        }
        T element = this.queueArray[++this.front];
        this.queueArray[this.front] = null;
        return element;
    }

    @Override
    public int size() {
        return this.rear - this.front;
    }

    /**
     * 清空队列，并重置队头和队尾指针。
     */
    @Override
    public void clear() {
        for (int i = (this.front + 1); i <= this.rear; i++) {
            this.queueArray[i] = null;
        }
        this.front = -1;
        this.rear = -1;
    }

    @Override
    public boolean isEmpty() {
        return this.rear == this.front;
    }

    @Override
    public boolean isFull() {
        return this.rear + 1 == this.maxSize;
    }
}

测试代码
package com.codestd.study.queue;

import org.junit.Test;

import static org.assertj.core.api.Assertions.*;

/**
 * Test for {@link ArrayQueue}
 */
public class ArrayQueueTest {

    @Test
    public void test() {
        Queue<Integer> queue = new ArrayQueue<>(3);
        assertThat(queue.isEmpty()).isTrue();
        assertThat(queue.isFull()).isFalse();

        queue.push(1);
        assertThat(queue.isEmpty()).isFalse();
        assertThat(queue.peek()).isEqualTo(1);
        assertThat(queue.size()).isEqualTo(1);

        int el = queue.pop();
        assertThat(queue.isEmpty()).isTrue();
        assertThat(el).isEqualTo(1);

        queue.push(2);
        queue.push(3);
        assertThat(queue.isEmpty()).isFalse();
        assertThat(queue.isFull()).isTrue();
        assertThat(queue.size()).isEqualTo(2);

        el = queue.pop();
        assertThat(el).isEqualTo(2);

        el = queue.pop();
        assertThat(el).isEqualTo(3);

        assertThat(queue.isFull()).isTrue();
        assertThat(queue.isEmpty()).isTrue();

        queue.clear();
        assertThat(queue.isEmpty()).isTrue();
        assertThat(queue.isFull()).isFalse();

        queue.push(1);
        queue.clear();
        assertThat(queue.isEmpty()).isTrue();
        assertThat(queue.isFull()).isFalse();
    }
}

总结
前文中已经提到这种方式存在严重的问题，这是一个一次性的队列。在队列满了之后，就无法再往队列中插入数据了，哪怕数组中有空位置。要解决这个问题就需要用到环形数组。这部分的实现原理在下一篇文章中将。

 导读

            在开始讲之前，我们都必须明白的一点就是栈和队列数据进出的方式：栈是先进后出的，队列是先进先出的。在数据结构中，这两个算法模式都是很常见或者说最基础和最重要的一部分，数据如何存储的，都基本离不开栈和队列。但是js中的栈和队列和一般的语言有一些区别，实际上就好像把队列看成栈一样，实际上还是有差别的并且遵循的原理也依然没有变。

 一、js中的数组栈和队列

 

发现问题：

	var stack=[];
	
	stack.push("a");
	stack.push("b");
	stack.push("c");
	
	console.log(stack.pop());
	console.log(stack.pop());
				
		
	var queue = [];
	
	queue.unshift("a");
	queue.unshift("b");
	queue.unshift("c");
	
	console.log(queue.shift());
	console.log(queue.shift());

              结果输出：                 

                                                            

 

               上面是出现疑问的代码，首先对于栈而言，就是输出cb没有任何疑问。但是为什么队列也是输出cb呢?接下来看我们的解释。

 

1.栈

    首先，栈是先进后出的，例如现在给出一组一维数组为[a,b,c],

 

                               

                       压栈顺序应该是abc

                                     

                          出栈顺序为：cba。 

总结：
                 栈，在js中的栈中存入值是从头部插入数据的，在尾部输出或者拿走数据，此时a的左边就像被堵住了，必须要在右边拿数据，这是因为是栈的特性必须遵循先进后出的原理。这个相信很多人都懂，也很多人能够理解，先进后出嘛，就是最先进入的数据就最后才出来的意思，在图和逻辑上基本是和平常人思维一致的，但是到js的数组队列中就发现一个问题了。

2.队列

             同样进入三个值abc，假设和栈的数组一样，从左往右阅读。

            队列从尾部插入数据

                                                 

            出去的顺序为：cba。从头部出来数据。

                                            

   总结： 

             此时很多人都会觉得真的是这样的吗？其实在内存阅读程序过程中，受到队列和栈的算法影响，阅读顺序有所差别。队列是从尾部插入数据，从头部输出数据会更加好理解。

  二、深入js数组栈和堆理解

             首先，js中的队列我们不能用一种惯性思维去理解，当然队列算法的原理完全没有问题的，所以也不存在算法逻辑上的错误。实际上，在js中的栈中存入值是从头部插入数据的，最先进入栈里的值会顶到最后面出来的拿一个位置。                      

                    如图所示：



                                    

所以a最先进入被顶入最左边，最左边封顶，a是最后一个值，此时如果输出值就会拿出cba值。

                                                            

  

                               

 

和栈的区别就是队列中，a的最左边不封顶，被数值顶入队列中，也就是在a左边还有可能还有更多的数值，a不是最后一个值。因为现在内存阅读从右边开始拿数据，那么输出也是和栈一致是cba。

自我感想：

            队列和栈在js中都有不同的表现，这些表现也许我们还是相当疑惑的。我们都知道队列和栈的算法原理，但是实际上我们在操作过程中会存在很多疑问，解决这些疑问，就是我们提高我们的硬实力的绝佳路径。

 

 

 

谢谢大家~❤