栈与队列(超详细)

发布时间:2024-04-17 17:01

目录

  • 一、栈(Stack)
      • 1、什么是栈?
      • 2、栈的常见方法
      • 3、自己实现一个栈(底层用一个数组实现)
  • 二、队列(Queue)
      • 1、什么是队列?
      • 2、队列的常见方法
      • 3、队列的实现(单链表实现)
      • 4、循环队列

一、栈(Stack)

1、什么是栈?

栈其实就是一种数据结构 - 先进后出(先入栈的数据后出来,最先入栈的数据会被压入栈底)
\"栈与队列(超详细)_第1张图片\"
什么是java虚拟机栈?
java虚拟机栈只是JVM当中的一块内存,该内存一般用来存放 例如:局部变量
当调用函数时,我们会为函数开辟一块内存,叫做 栈帧,在 java虚拟机栈中开辟,具体如下。
\"栈与队列(超详细)_第2张图片\"
常见考点:不可能的出栈顺序
\"栈与队列(超详细)_第3张图片\"
这道题该怎么分析呢?
首先我们知道,出栈时拿到的第一个元素为4,那么4必须入栈,因为入栈的顺序是 1 2 3 4 5 6,所以4要入栈,1 2 3 得先入栈。(通过后面分析得知,该出栈序列正确)
\"栈与队列(超详细)_第4张图片\"

2、栈的常见方法

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

3、自己实现一个栈(底层用一个数组实现)

public class MyStack {
    public int[] elem;
    public int usedSize;

    public MyStack() {
        this.elem = new int[4];
    }

    // 放入元素
    public void push(int val) {
        if(isFull()) {
            // 如果放满了,二倍扩容
            this.elem = Arrays.copyOf(elem,2 * elem.length);
        }
        this.elem[this.usedSize++] = val;
    }
    // 获取栈顶元素并弹出
    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException(\"栈为空!\");
        }
        usedSize--;
        return elem[usedSize];
    }
    // 获取栈顶元素
    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException(\"栈为空!\");
        }
        return elem[usedSize-1];
    }
    // 是否为空
    public boolean isEmpty() {
        return usedSize == 0;
    }
    // 是否满了
    public boolean isFull() {
        return elem.length == usedSize;
    }
}

二、队列(Queue)

1、什么是队列?

只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有 - 先进先出。
入队列:进行插入操作的一端称为队尾
出队列:进行删除操作的一端称为队头
\"栈与队列(超详细)_第5张图片\"
\"栈与队列(超详细)_第6张图片\"

2、队列的常见方法

\"栈与队列(超详细)_第7张图片\"
\"栈与队列(超详细)_第8张图片\"

// 普通队列
Queue<Integer> queue = new LinkedList<>();
queue.offer(1);// 队尾入
int top = queue.peek();// 获取队头元素
queue.poll();// 弹出队尾元素并返回

// 双端队列
Deque<Integer> deque = new LinkedList<>();
deque.offer(1);// 默认队尾入
deque.offerFirst(2);// 队头入
deque.offerLast(3);// 队尾入

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

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

3、队列的实现(单链表实现)

\"栈与队列(超详细)_第9张图片\"

/**
 * 每个节点
 */
class Node{
    public int val;
    public Node next;

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

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

    /**
     * 出队列
     */
    public int poll() {
        if(isEmpty()) {
            throw new RuntimeException(\"队列为空!\");
        }
        int val = head.val;
        head = head.next;
        return val;
    }

    /**
     * 获取队头元素
     */
    public int peek() {
        if(isEmpty()) {
            throw new RuntimeException(\"队列为空!\");
        }
        return head.val;
    }
    
    // 队列是否为空
    public boolean isEmpty() {
        return head == null;
    }
}

4、循环队列

当考虑用数组来实现一个队列, 很容易想到以下结构:
\"栈与队列(超详细)_第10张图片\"
当我们连续从该队头中弹出元素时,就可以发现问题了
\"栈与队列(超详细)_第11张图片\"
可以看到此时数组并没有满,但是当我们再次插入元素时,队尾却插入不了了,这时候我们可以想到将该数组看成是循环的数组,结构如下。
\"栈与队列(超详细)_第12张图片\"
可以看出,当 front 和 rear 相遇时,队列可能的情况有两种,要么为空,要么是满的状态。那么队列什么时候为空,什么时候是满的呢?
我们有两种方法:
1、设置usedSize 当usedSize和数组长度相等时为满,等于0 则为空。
2、设置标志位 设 flag = true,每放一个元素,将 flag 置为 false,每有一个元素出队列,则将 flag 置为 true。当 front 和 rear 相遇时,flag为 true 则是空的,反之则是满的。

public class MyCircularQueue {
    public int[] elem;
    public int front;// 队头下标
    public int rear;// 队尾下标
    boolean flag = true;// 是否为空

    public MyCircularQueue(int k) {
        elem = new int[k];
    }

    // 向循环队列插入一个元素。如果成功插入则返回真。
    public boolean enQueue(int value) {
        if (isFull()) {
            return false;
//            throw new RuntimeException(\"队列已满!\");
        }
        elem[rear] = value;
        rear = (rear + 1) % elem.length;
        flag = false;
        return true;
    }

    // 从循环队列中删除一个元素。如果成功删除则返回真。
    public boolean deQueue() {
        if (isEmpty()) {
            return false;
//            throw new RuntimeException(\"队列为空!\");
        }
        front = (front + 1) % elem.length;
        flag = true;
        return true;
    }

    // 从队首获取元素。如果队列为空,返回 -1 。
    public int Front() {
        if (isEmpty()) {
            return -1;
//            throw new RuntimeException(\"队列为空!\");
        }
        return elem[front];
    }
    // 获取队尾元素。如果队列为空,返回 -1 。
    public int Rear() {
        if (isEmpty()) {
            return -1;
//            throw new RuntimeException(\"队列为空!\");
        }
        // 如果是0下标,拿最后一个元素
        if (rear == 0) {
            return elem[elem.length-1];
        }else {
            return elem[rear - 1];
        }
    }

    // 检查循环队列是否为空。
    public boolean isEmpty() {
        if (rear == front && flag){
            return true;
        }
        return false;
    }
    // 检查循环队列是否已满。
    public boolean isFull() {
        if (rear == front && !flag){
            return true;
        }
        return false;
    }
}

ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网,如有侵权请联系:561261067@qq.com

桂ICP备16001015号