当前位置:   article > 正文

数据结构:栈和队列

数据结构:栈和队列

栈和队列

1、栈(Stack)

1.1概念

是一种特殊的线性表,只允许在固定的一段端进行数据的插入和删除。进行数据插入和删除的一端称为栈的栈顶,另一端称为栈底。栈中的数据遵循先进后出的原则。

image-20221025231650035

1.2栈的使用

image-20221025231803876

public static void main(String[] args) {
        Stack<Integer>stack=new Stack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        System.out.println("栈中元素个数"+stack.size());
        System.out.println("栈顶元素"+stack.peek());
        System.out.println(stack.pop());//出栈
        if (stack.isEmpty()){
            System.out.println("栈为空");
        }else {
            System.out.println(stack.size());
        }
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

1.3栈的模拟实现

image-20221025234049926

集合框架中,Stack继承了Vector,Vector和ArrayList类似,都是动态顺序表。

public class MyStack {
    // 用一个数组去组织数据
    private int[] elementData;
    // 有效元素的个数
    private int size;
    // 定义一个数组默认的大小
    private final int DEFAULT_CAPACITY = 5;

    public MyStack() {
        this.elementData = new int[DEFAULT_CAPACITY];
    }

    public MyStack(int capacity) {
        if (capacity < 0) {
            throw new RuntimeException("数组容量不能小于0.");
        } else if (capacity > 0) {
            this.elementData = new int[capacity];
        } else {
            this.elementData = new int[DEFAULT_CAPACITY];
        }
    }

    public void push(int data) {
        // 数组是否需要扩容
        ensureCapacity();
        // 在size位置加入元素
        elementData[size++] = data;
        // size++
    }
    //取出栈顶元素
    public int pop(){
        int e = peek();
        size--;
        return e;
    }
    //获得栈顶元素
    public int peek(){
        if(empty()){
            throw new RuntimeException("栈为空,无法获取栈顶元素");
        }
        return elementData[size-1];
    }
    public int size(){
        return size;
    }
    //扩容
    private void ensureCapacity() {
        if (size == elementData.length) {
            this.elementData = Arrays.copyOf(elementData, elementData.length * 2);
        }
    }
    public boolean empty(){
        return 0 == size;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55

1.4相关OJ

  1. 括号匹配
  2. 逆波兰表达式
  3. 最小栈
  4. 出栈入栈次序匹配

1.5注意

栈、虚拟机栈、栈帧有什么区别呢?

简单的理解:

栈是一种数据结构。

虚拟机栈:具有特殊作用的一块内存空间。jvm为了对数据进行更好的管理,将内存按照不同的需求划分出来的一种结构

栈帧:一种结构,这种结构与函数调用相关的,内部:局部变量表、操作数栈…

每个方法在运行时,jvm都会创建一个栈帧,然后将栈帧压入到虚拟机栈中

当方法调用结束时,该方法对应的栈帧会从虚拟机栈中出栈

2、队列(Queue)

2.1概念

与栈的概念相似。而队列是在一端进行插入数据,另一端进行删除数据操作的特殊线性表,队列遵循先进先出原则。

image-20221026000404498

2.2队列的使用

在Java中,Queue是个接口,底层是通过链表实现的

image-20221026000522894

image-20221026000541280

public static void main(String[] args) {
        //Queue是个接口,在实例化时必须实例化LinkedList的对象,因为LinkedList实现了Queue接口
        Queue<Integer>queue=new LinkedList<>();
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        queue.offer(4);
        queue.offer(5);
        System.out.println(queue.size());
        System.out.println("队头元素"+queue.peek());
        System.out.println("出队"+queue.poll());
        if (queue.isEmpty()){
            System.out.println("队空");
        }else {
            System.out.println(queue.size());
        }
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

2.3队列的实现(链表实现)

public class MyQueue {
    //1、定义一个静态双向链表节点的类
    public static class ListNode{
        int val;
        ListNode prev;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
    //头节点
    public ListNode head;
    //尾节点
    public ListNode tail;
    //对列
    public int size;

    /**
     * 入队  从对尾入
     * @param e
     */
    public void offer(int e){
        ListNode node=new ListNode(e);

        if (head==null){
            //空链表
            head=node;
        }else{
            tail.next=node;
            node.prev=tail;
        }
        tail=node;
        size++;
    }

    /**
     * 出栈 ,从队头出
     */
    public int poll(){
        if (isEmpty()){
            throw new RuntimeException("队列为空.");
        }
        //获取对头元素
        int headVal= head.val;
        head=head.next;
        if (head==null){
            tail=null;
        }else {
            //处理前驱节点
            head.prev.next=null;

            head.prev=null;
        }
        size--;
        return headVal;
    }

    /**
     * 获取队头元素
     * @return
     */
    public int peek(){
        if (isEmpty()){
            throw new RuntimeException("队列为空.");
        }
        return head.val;
    }
    public boolean isEmpty(){
        return size==0;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72

2.4循环队列

在使用中我们还会用到一种队列叫循环队列。

循环队列通常使用数组实现。

image-20221026003353512

相关OJ

设计循环队列

循环队列实现

2.5 OJ

  1. 用栈实现队列
  2. 用队列实现栈

参考代码

队列实现栈

栈实现队列

声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:【wpsshop博客】
推荐阅读
相关标签
  

闽ICP备14008679号