数据结构篇——栈和队列

• 2022 年 11 月 17 日
• 筆記
• 算法学习

数据结构篇——栈和队列

本次我们介绍基础算法中的栈和队列，我们会从下面几个角度来介绍：

• 栈和队列简述
• 模拟栈
• 模拟队列

栈和队列简述

首先我们要简单了解一下栈和队列：

• 栈：数据元素先进后出
• 队列：数据元素先进先出

我们分别给出展示图：

模拟栈

我们下面给出用数组模拟栈的写法：

public class Stack {
    
    // 固定长度
    final int N = 1000010;
    
    // 栈(栈元素从下标1开始)
    int[] stk = new int[N];
    
    // 栈指针（永远指在栈顶）
    int t = 0;
    
    public static void main(String[] args) {
        // 测试代码
    }

    /**
     * 推入操作
     * @param x
     */
    public void push(int x){
        stk[++t] = x;
    }

    /**
     * 弹出操作
     */
    public void pop(){
        t--;
    }

    /**
     * 判断是否为空
     */
    public boolean isEmpty(){
        if (t > 0){
            return false;
        }else {
            return true;
        }
    }

    /**
     * 返回栈顶元素
     * @return
     */
    public int stkTop(){
        return stk[t];
    }
    
}

模拟队列

我们下面给出用数组模拟队列的写法：

public class Queue {
    
    // 定义一个队列大小
    final int N = 100010;
    
    // 定义队列
    int[] queue = new int[N];
    
    // 定义队头和队尾
    int head = 1;
    int tail = 0;
    
    public static void main(String[] args) {
        // 测试代码
    }

    /**
     * 添加操作
     * @param x
     */
    public void add(int x){
        queue[++tail] = x;
    }

    /**
     * 弹出操作
     */
    public void pop(){
        if (head <= tail){
            // 说明有值，可以删除
            head++;
        }else {
            // 说明无值，无法删除
            System.out.println("无法删除");
        }
    }

    /**
     * 得到队头元素
     * @return
     */
    public int getHead(){
        return queue[head];
    }

    /**
     * 得到队尾元素
     */
    public int getTail(){
        return queue[tail];
    }

    /**
     * 是否为空
     */
    public boolean isEmpty(){
        if (head <= tail){
            return false;
        }else {
            return true;
        }
    }

    /**
     * 队列长度
     */
    public int getLong(){
        return tail-head+1;
    }
}

结束语

好的，关于数据结构篇的栈和队列就介绍到这里，希望能为你带来帮助~

附加

《表达式求值》问题由于涉及数，哈希等内容在后续会在该文章补充~