【Java数据结构】——栈与队列深度剖析

文章目录

一、栈的基本概念

栈的定义：

栈是仅限定在表尾进行插入和删除操作的线性表。

允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom），不含任何数据的的栈称为空栈。

此外，栈又称为后进先出的线性表。

栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

如何理解栈的定义：

1. 首先它是一个线性表，也就是说，栈元素具有线性关系，即前驱后继关系。区别在于栈是一种特殊的线性表。
2. 定义中说的线性表的表尾进行插入和删除操作，这里的表尾指的是栈顶，而不是栈尾。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据在栈顶。

二、栈的实现

1. 利用顺序表实现，即使用尾插 + 尾删的方式实现
2. 利用链表实现，则头尾皆可

相对来说，顺序表的实现上要更为简单一些，所以我们优先用顺序表实现栈。

importjava.util.Arrays;publicclassMyStack{publicint[] elem;publicint usedSize;publicMyStack(){this.elem =newint[5];}//进栈publicvoidpush(int val){if(isFull()){//扩容Arrays.copyOf(this.elem,2*this.elem.length);}this.elem[this.usedSize]= val;this.usedSize++;}publicbooleanisFull(){returnthis.usedSize ==this.elem.length;}//出栈publicintpop(){if(isEmpty()){thrownewRuntimeException("栈为空");}int oldVal =this.elem[usedSize -1];this.usedSize--;return oldVal;}//获取栈顶元素publicintpeek(){if(isEmpty()){thrownewRuntimeException("栈为空");}returnthis.elem[usedSize-1];}//是否为空publicbooleanisEmpty(){returnthis.usedSize ==0;}}

测试代码：

importjava.util.Stack;publicclassTestDemo{publicstaticvoidmain(String[] args){MyStack stack =newMyStack();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);System.out.println(stack.pop());//弹出栈顶元素，并且删除4System.out.println(stack.peek());//获取栈顶元素，但不删除3System.out.println(stack.isEmpty());//false}}

上面实现的栈，底层是一个数组，那么请问：我们能不能用单链表实现栈？

答案是可以的，我们用单链表实现栈满足以下条件：

1. 先进后出
2. 入栈和出栈的时间复杂度得都是O(1)

再来，链表可以头插法和尾插法，那么我们入栈使用的是头插还是尾插？

假如我们用的是尾插法，我们可以发现，我们出栈的时候每次都需要找尾巴，那么时间复杂度就是O（n)。

假如我们用的是头插法，时间复杂度则为O（1），因为出栈的时候，我们只需要删除头节点就可以了。

三、栈的注意事项

了解完栈的基本概念与实现，我们来看一下下面的这几个问题。

1. 什么是栈？
2. 什么是Java虚拟机栈？
3. 什么是栈帧？

第一，什么是栈？ 栈其实就是一种数据结构。特点是先进先出。这里就是上面栈的基本概念。

第二，什么是Java虚拟机栈？
JVM内存结构分为五部分，如下图，而Java虚拟机栈是JVM中的一块内存。

第三，什么是栈帧？栈帧（Stack Frame）是用于支持虚拟机进行方法调用和方法执行的数据结构。它是虚拟机运行时数据区中的java虚拟机栈的栈元素。

栈帧存储了方法的局部变量表、操作数栈、动态连接和方法返回地址等信息。

每一个方法从调用开始至执行完成的过程，都对应着一个栈帧在虚拟机里面从入栈到出栈的过程。

四、队列的基本概念

定义：

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表
队列具有先进先出FIFO(First In First Out)
入队列：进行插入操作的一端称为队尾（Tail/Rear）
出队列：进行删除操作的一端称为队头（Head/Front）

五、队列的实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

classNode{publicint val;publicNode next;publicNode(int val){this.val = val;}}publicclassMyQueue{publicNode head;publicNode last;/**
     * 尾插法
     * @param val
     */publicvoidoffer(int val){Node node =newNode(val);if(head ==null){
            head = node;
            last = node;}else{
            last.next = node;
            last = last.next;}}/**
     * 出队
     * @return
     */publicintpoll(){if(isEmpty()){thrownewRuntimeException("队列为空");}int oldVal = head.val;this.head = head.next;return oldVal;}publicbooleanisEmpty(){returnthis.head ==null;}publicintpeek(){if(isEmpty()){thrownewRuntimeException("队列为空");}return head.val;}}

测试代码：

publicclassTestDemo{publicstaticvoidmain(String[] args){MyQueue queue =newMyQueue();
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);System.out.println(queue.peek());//1System.out.println(queue.poll());//2System.out.println(queue.poll());//3System.out.println(queue.poll());//}}

结果：

六、循环队列

定义：

队列头尾相接的顺序存储结构称为循环队列

如果理解这个定义呢？这里需要我们一步一步来。

下面内容很重要，请大家认真看。

6.1队列顺序存储的不足与解决方法

我们假设一个队列有n个元素，则顺序存储的队列需建立一个大于n的数组，并把队列的所有元素存储在数组的前n个单元,数组下标为0的一端即是队头。所谓的入队列操作，其实就是在队尾追加一个元素,不需要移动任何元素，因此时间复杂度为O(1).

但问题是队列元素的出列是在队头，即下标为0的位置，那也就意味着，队列中的所有元素都得向前移动，就像我们平时排队一样，以保证队列的队头，也就是下标为0的位置不为空，此时时间复杂度为0(n)。

来到这里我们思考一下，我们在出队的时候，能不能不移动队列？也就说，我们能不能不把队头一定限定在下标为0的位置？

这里我们引入两个指针，一个是front指针，一个rear指针。
front指针指向队头元素，rear 指针指向队尾元素的下一个位置，这样当front等于rear时,就变成空队列了。

假设是长度为6的数组，初始状态，空队列如下左图所示，front与rear指针均指向下标为0的位置。然后入队 a1、a2、a3、a4、a5,front 指针依然指向下标为0位置，而rear指针指向下标为4的位置，如下的右图所示。

假如我们将a1出队列，则front往下移，如下图。
假如我们将元素a6、a7入队，我们会发现rear指针指向了数组之外，也就是溢出了。但事实上我们溢出了没有？很明显，前面还有空位，这个我们称为假溢出。

那如何解决假溢出的问题呢？
——————————————————采用循环队列

后面满了，就再从头开始，也就是头尾相接的循环。

我们把队列的这种头尾相接的顺序存储结构称为循环队列。

如果刚刚的例子中，我们的rear又重新指向了队头，这问题就可以解决了。


此时问题又出来了，我们刚才说，空队列时，front 等于rear，现在当队列满时，也是 front等于rear，那么如何判断此时的队列究竟是空还是满呢?

在这里，我们有两个办法解决这个问题。
方法一：

设置一个标志变量flag,当front == rear，且 flag=0时为队列空,当front == rear，且 flag =1时为队列满。

方法二：

办法二是当队列空时，条件就是 front = rear，当队列满时，我们修改其条件，保留一个元素空间。也就是说，队列满时，数组中还有一个空闲单元。例如下图所示，我们就认为此队列已经满了。

在实际的操作中，我们一般使用第二种比较多，所以我们这里重点介绍第二种。

由于rear可能比 front大，也可能比 front小，所以管它们只相差一个位置时就是满的情况，但也可能是相差整整一圈。所以若队列的最大尺寸为 QueueSize，那么队列满的条件是：

(rear+1)%QueueSize == front(取模“%”的目的就是为了整合rear 与 front大小为一个问题)。

如下图，QueueSize = 6，front=2，而rear=1,(1+1)%6 = 2，所以此时队列满。

再如下图，front= 2而rear = 5。(5 +1) %6 ≠ 2 ，所以此时队列也是满的。

另外，当rear > front时，如下图，此时队列的长度为rear-front。

但当rear < front时，，队列长度分为两段，一段是 QueueSize-front,另一段是0 +rear,加在一起，队列长度为rear一front +QueueSize。

因此通用的计算队列长度公式为:
(rear- front + QueueSize)%QueueSize = length

其中：
    length为当前队列的长度
    rear为队列尾指针
    front为队列头指针
    QueueSize为队列可容纳的元素总数（即队列大小）

七、循环队列代码实现

publicclassMyCircleQueue{publicint[] elem;publicint front;//队头下标publicint rear;//队尾下标publicMyCircleQueue(int k){this.elem =newint[k];}/**
     * 入队
     * @param value
     * @return
     */publicbooleanenQueue(int value){if(isFull())returnfalse;this.elem[rear]= value;//rear++;
        rear =(rear+1)% elem.length;returntrue;}publicbooleandeQueue(){if(isEmpty())returnfalse;
        front =(front+1)% elem.length;returntrue;}/**
     * 得到队头元素
     * @return
     */publicintFront(){if(isEmpty()){return-1;}return elem[front];}publicintRear(){if(isEmpty()){return-1;}int index =-1;if(rear ==0){
            index = elem.length-1;}else{
            index = rear-1;}return elem[index];}//判断队列是否为空publicbooleanisEmpty(){return front == rear;}//判断队列是否已满publicbooleanisFull(){//rear的下一个是frontif((this.rear+1)% elem.length == front){returntrue;}returnfalse;}}

八、双端队列

定义：

双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。
那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。

总结

好久没更博客了，确实颓废了。整理了一下栈和队列的知识点，以为很快，没想到了弄了一天了。希望各位看客老爷能一键三连。感谢，感谢！