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

一、栈的基本概念

栈的定义:

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

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

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

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

如何理解栈的定义:

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

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

在这里插入图片描述

二、栈的实现

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

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

import java.util.Arrays;
public class MyStack { 
    public int [] elem;
    public int usedSize;

    public MyStack(){ 
        this.elem = new int[5];
    }
//进栈
    public  void push(int val){ 
        if(isFull()){ 
            //扩容
            Arrays.copyOf(this.elem,2*this.elem.length);
        }
        this.elem[this.usedSize] = val;
        this.usedSize++;
    }
    public boolean isFull(){ 
        return this.usedSize == this.elem.length;
    }
    //出栈
    public int pop(){ 
        if(isEmpty()){ 
            throw new RuntimeException("栈为空");
        }
        int oldVal = this.elem[usedSize - 1];
        this.usedSize--;
        return oldVal;
    }
    //获取栈顶元素
    public int peek(){ 
        if(isEmpty()){ 
            throw new RuntimeException("栈为空");
        }
        return this.elem[usedSize-1];
    }
    //是否为空
    public boolean isEmpty(){ 
        return this.usedSize == 0;
    }
}

测试代码:

import java.util.Stack;
public class TestDemo { 
    public static void main(String[] args) { 
        MyStack stack = new MyStack();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        System.out.println(stack.pop());//弹出栈顶元素,并且删除4
        System.out.println(stack.peek());//获取栈顶元素,但不删除3
        System.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)

在这里插入图片描述


五、队列的实现

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

class Node{ 
    public int val;
    public Node next;
    public Node(int val){ 
        this.val = val;
    }
}
public class MyQueue { 
    public Node head;
    public Node last;

    /** * 尾插法 * @param val */
    public void offer(int val){ 
        Node node =new Node(val);
        if(head == null){ 
            head = node;
            last = node;
        }else { 
            last.next = node;
            last = last.next;
        }
    }

    /** * 出队 * @return */
    public int poll(){ 
        if(isEmpty()){ 
            throw new RuntimeException("队列为空");
        }
        int oldVal = head.val;
        this.head = head.next;
        return oldVal;
    }
    public boolean isEmpty(){ 
        return this.head == null;
    }
    public int peek(){ 
        if(isEmpty()){ 
            throw new RuntimeException("队列为空");
        }
        return head.val;
    }
}

测试代码:

public class TestDemo { 
    public static void main(String[] args) { 
        MyQueue queue = new MyQueue();
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        System.out.println(queue.peek());//1
        System.out.println(queue.poll());//2
        System.out.println(queue.poll());//3
        System.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为队列可容纳的元素总数(即队列大小)


七、循环队列代码实现

public class MyCircleQueue { 
    public int[] elem;
    public int front;//队头下标
    public int rear;//队尾下标
    public MyCircleQueue(int k) { 
        this.elem = new int[k];
    }

    /** * 入队 * @param value * @return */
    public boolean enQueue(int value) { 
        if(isFull()) return false;

        this.elem[rear] = value;
        //rear++;
        rear = (rear+1)% elem.length;
        return true;
    }

    public boolean deQueue() { 
        if(isEmpty()) return false;
        front = (front+1)% elem.length;
        return true;
    }

    /** * 得到队头元素 * @return */
    public int Front() { 
        if(isEmpty()) { 
            return -1;
        }
        return elem[front];
    }

    public int Rear() { 
        if(isEmpty()) { 
            return -1;
        }
        int index = -1;
        if(rear == 0) { 
            index = elem.length-1;
        }else { 
            index = rear-1;
        }
        return elem[index];
    }
//判断队列是否为空
    public boolean isEmpty() { 
        return front == rear;
    }
//判断队列是否已满
    public boolean isFull() { 
        //rear的下一个是front
        if( (this.rear+1) % elem.length == front) { 
            return true;
        }
        return false;
    }
}

八、双端队列

定义:

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


总结

好久没更博客了,确实颓废了。整理了一下栈和队列的知识点,以为很快,没想到了弄了一天了。希望各位看客老爷能一键三连。感谢,感谢!
正文到此结束
评论插件初始化中...
Loading...