知识补充

1. 栈
   • 先进后出==》有底的圆筒
2. 队列
   • 先进先出==》没有底的圆筒

题目描述

题目：就是用数组模拟栈，主要操作就是添加栈顶元素，删除栈顶元素，查询栈顶元素，判断栈是否为空。

输入样例

10
push 5
query
push 6
pop
query
pop
empty
push 4
query
empty

输出样例

5
5
YES
4
NO

算法1

(数组模拟栈) $O(n)$

思路：
1. 用数组存储栈的值
2. 用一个变量(tt)来代表指向栈顶的指针
- 添加元素==》stk[++tt] = x;–说明从1开始存储的
- 查询栈顶==》stk[tt];
- 删除栈顶==》–tt;
- 判空==》tt == 0

时间复杂度：$O(n)$

参考文献：y总

Java 代码

import java.util.Scanner;

public class Main {
    static int[] stk = new int[100010];
    static int tt;

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int m  = scan.nextInt();

        while (m-- > 0){
            String op = scan.next();
            if ("push".equals(op)){
                int x = scan.nextInt();
                stk[++tt] = x;// 在栈顶添加元素 从1开始
            }else if ("pop".equals(op)){
                --tt;// 栈顶指针下移
            }else if ("empty".equals(op)){
                System.out.println(tt == 0 ? "YES" : "NO");// 判断是否为空
            }else if ("query".equals(op)){
                System.out.println(stk[tt]);// 查询栈顶元素
            }
        }

    }
}

注意

1. 可能编译器的输出格式有点问题，但是可以ac的