栈与队列（超详细）

目录

一、栈（Stack）

1、什么是栈？

栈其实就是一种数据结构 - 先进后出（先入栈的数据后出来，最先入栈的数据会被压入栈底）

什么是java虚拟机栈？
java虚拟机栈只是JVM当中的一块内存，该内存一般用来存放 例如：局部变量
当调用函数时，我们会为函数开辟一块内存，叫做 栈帧，在 java虚拟机栈中开辟，具体如下。

常见考点：不可能的出栈顺序

这道题该怎么分析呢？
首先我们知道，出栈时拿到的第一个元素为4，那么4必须入栈，因为入栈的顺序是 1 2 3 4 5 6，所以4要入栈，1 2 3 得先入栈。（通过后面分析得知，该出栈序列正确）

2、栈的常见方法

方法作用E push(E item)放入元素E pop()获取栈顶元素并弹出E peek()获取栈顶元素boolean isEmpty()判断栈是否为空（父类Vector的方法）

3、自己实现一个栈（底层用一个数组实现）

publicclassMyStack{publicint[] elem;publicint usedSize;publicMyStack(){this.elem =newint[4];}// 放入元素publicvoidpush(int val){if(isFull()){// 如果放满了，二倍扩容this.elem =Arrays.copyOf(elem,2* elem.length);}this.elem[this.usedSize++]= val;}// 获取栈顶元素并弹出publicintpop(){if(isEmpty()){thrownewRuntimeException("栈为空！");}
        usedSize--;return elem[usedSize];}// 获取栈顶元素publicintpeek(){if(isEmpty()){thrownewRuntimeException("栈为空！");}return elem[usedSize-1];}// 是否为空publicbooleanisEmpty(){return usedSize ==0;}// 是否满了publicbooleanisFull(){return elem.length == usedSize;}}

二、队列（Queue）

1、什么是队列？

只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有 - 先进先出。
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头

2、队列的常见方法

// 普通队列Queue<Integer> queue =newLinkedList<>();
queue.offer(1);// 队尾入int top = queue.peek();// 获取队头元素
queue.poll();// 弹出队尾元素并返回// 双端队列Deque<Integer> deque =newLinkedList<>();
deque.offer(1);// 默认队尾入
deque.offerFirst(2);// 队头入
deque.offerLast(3);// 队尾入

deque.peekFirst();// 获取队头元素
deque.peekLast();// 获取队尾元素

deque.pollFirst();// 弹出队头元素并返回
deque.pollLast();// 弹出队尾元素并返回

3、队列的实现（单链表实现）

/**
 * 每个节点
 */classNode{publicint val;publicNode next;publicNode(int val){this.val = val;}}publicclassMyQueue{publicNode head;publicNode tail;/**
     * 插入元素 -- 尾插法
     * @param val
     */publicvoidoffer(int val){Node node =newNode(val);if(head ==null){
            head = node;
            tail = node;}else{
            tail.next = node;
            tail = tail.next;}}/**
     * 出队列
     */publicintpoll(){if(isEmpty()){thrownewRuntimeException("队列为空！");}int val = head.val;
        head = head.next;return val;}/**
     * 获取队头元素
     */publicintpeek(){if(isEmpty()){thrownewRuntimeException("队列为空！");}return head.val;}// 队列是否为空publicbooleanisEmpty(){return head ==null;}}

4、循环队列

当考虑用数组来实现一个队列， 很容易想到以下结构：

当我们连续从该队头中弹出元素时，就可以发现问题了

可以看到此时数组并没有满，但是当我们再次插入元素时，队尾却插入不了了，这时候我们可以想到将该数组看成是循环的数组，结构如下。

可以看出，当 front 和 rear 相遇时，队列可能的情况有两种，要么为空，要么是满的状态。那么队列什么时候为空，什么时候是满的呢？
我们有两种方法：
1、设置usedSize 当usedSize和数组长度相等时为满，等于0 则为空。
2、设置标志位 设 flag = false，每放一个元素，将 flag 置为 true，每有一个元素出队列，则将 flag 置为 false。当 front 和 rear 相遇时，flag为 true 则是满的，反之则是空的。

publicclassMyCircularQueue{publicint[] elem;publicint front;// 队头下标publicint rear;// 队尾下标boolean flag =true;// 是否为空publicMyCircularQueue(int k){
        elem =newint[k];}// 向循环队列插入一个元素。如果成功插入则返回真。publicbooleanenQueue(int value){if(isFull()){returnfalse;//            throw new RuntimeException("队列已满!");}
        elem[rear]= value;
        rear =(rear +1)% elem.length;
        flag =false;returntrue;}// 从循环队列中删除一个元素。如果成功删除则返回真。publicbooleandeQueue(){if(isEmpty()){returnfalse;//            throw new RuntimeException("队列为空!");}
        front =(front +1)% elem.length;
        flag =true;returntrue;}// 从队首获取元素。如果队列为空，返回 -1 。publicintFront(){if(isEmpty()){return-1;//            throw new RuntimeException("队列为空!");}return elem[front];}// 获取队尾元素。如果队列为空，返回 -1 。publicintRear(){if(isEmpty()){return-1;//            throw new RuntimeException("队列为空!");}// 如果是0下标，拿最后一个元素if(rear ==0){return elem[elem.length-1];}else{return elem[rear -1];}}// 检查循环队列是否为空。publicbooleanisEmpty(){if(rear == front && flag){returntrue;}returnfalse;}// 检查循环队列是否已满。publicbooleanisFull(){if(rear == front &&!flag){returntrue;}returnfalse;}}