栈(Stack)

概述

  • 栈就是一种 只允许在表尾进行插入和删除操作 的 线性表
  • 栈的特点
    • 先进后出 ,在表尾进行插入和删除操作




数组实现栈

  • crown
    • crown:使用crown来确定栈顶所在数组的下标,默认为 -1
  • 空栈
    • 当空栈时 ,crown = -1
  • 栈是否为空
    • 当 crown = -1 时 ,栈为空 ,不能 遍历 ,出栈 , 获取栈顶元素
  • 栈是否已满
    • 当 crown = 数组.length - 1 时 ,栈已满 , 不能 入栈
  • 入栈
    • 栈未满,才能入栈
      • 先将 crown上移 ,再给数组下标为crown的元素赋值
    • 栈满 ,不能入栈
  • 出栈
    • 栈不为空 ,才能出栈
      • 将 crown往下移即可
    • 栈为空 ,不能出栈
  • 获取栈顶元素
    • 栈不为空 ,才能获取栈顶元素
      • 获得数组下标为crown的元素
    • 栈为空 ,不能出栈
  • 重置栈
    • 让crown = -1 即可
  • 打印栈
    • 遍历数组下标范围为 [ 0 , crown ] ,即可
public class ArrayStack {
    private int[] satck;
    private int size;
    private int crown = -1; // 栈顶
    public ArrayStack(int size){
        this.size = size;
        satck = new int[size];
    }
    //入栈操作
    public void push(int value){
        if (!isFull()){
            satck[++crown] = value;
        }
    }
    //出栈
    public void pop(){
        if (!isEmpty()){
            crown--;
        }
    }
    //判断是否为空
    public boolean isEmpty(){
        return crown == -1;
    }
    //判断栈是否已满
    public boolean isFull(){
       return crown == size-1;
    }
    //获取栈顶元素
    public int getTop(){
        if (!isEmpty()){
            return satck[crown];
        }
        return -1;
    }
    //重置栈
    public void  reset(){
        crown = -1;
    }
    //打印栈 , 从栈顶开始打印
    public void print(){
        int j = 0;
        for (int i = crown; i >= 0; i--) {
            System.out.println("第"+(++j)+"个元素为:" + satck[i]);
        }
    }
}

/**
 * @author 发着呆看星
 * @create 2023/4/18
 **/
public class ArrayStackTest {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        ArrayStack arrayStack = new ArrayStack(5);
        boolean p = true;
        while (p){
            System.out.println("==================栈的功能检测===================");
            System.out.println("1) 入栈");
            System.out.println("2) 出栈");
            System.out.println("3) 重置栈");
            System.out.println("4) 打印栈");
            System.out.println("5) 取出栈顶元素");
            System.out.println("6) 退出程序");
            System.out.print("请选择你需要的功能(1~~6):");
            int i = scanner.nextInt();
            int j;
            switch (i){
                case 1:
                    System.out.print("请选择你要入栈的数字:");
                    j = scanner.nextInt();
                    arrayStack.push(j);
                    break;
                case 2:
                    arrayStack.pop();
                    break;
                case 3:
                    arrayStack.reset();
                    break;
                case 4:
                    arrayStack.print();
                    break;
                case 5:
                    int top = arrayStack.getTop();
                    System.out.println("栈顶元素为:"+top);
                    break;
                case 6:
                    p = false;
                    break;
            }
        }
    }
}

链表实现栈

  • 实现思路
    • 入栈:将每一个入栈的元素添加为链表的首节点
    • 出栈:出栈则将链表的首节点进行删除
    • 由于链表可以无限长,所以不用担心栈满的问题
  • crown:代表栈顶元素的上一个元素 ,val属性默认为 -1 ,next 属性即为 栈顶元素
    • 当 next == null 时 ,代表空栈
  • 判断栈是否为空
    • 当crown.next == null 时 ,栈为空
  • 重置栈
    • 即将 crown的next属性置为null
  • 获取栈顶元素
    • 即获取链表首节点(获取crown的next属性所代表的节点)
  • 打印栈
    • 即遍历链表




/**
 * @author 发着呆看星
 * @create 2023/4/18
 **/
public class LinkedListStack {
    private ListNode crown = new ListNode(-1,null);
    // 判断是否为空
    public boolean isEmpty(){
        return crown.next == null;
    }
    // 入栈操作
    public void push(int value){
        ListNode temp = crown.next;
        crown.next = new ListNode(value, temp);
    }
    // 出栈操作
    public void pop(){
        if (!isEmpty()){
            crown.next = crown.next.next;
        }
    }
    // 取出栈顶元素
    public ListNode getTop(){
        return crown.next;
    }
    // 重置栈
    public void reset(){
        crown.next = null;
    }
    // 打印栈 ,从栈顶开始
    public void print(){
        ListNode temp = crown;
        int i = 0;
        while (temp.next != null){
            System.out.println("第"+(++i)+"个元素为:"+temp.next.val);
            temp = temp.next;
        }
    }
}
/**
 * @author 发着呆看星
 * @create 2023/4/18
 **/
public class LinkedListStackTest {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        LinkedListStack stack = new LinkedListStack();
        boolean p = true;
        while (p){
            System.out.println("==================栈的功能检测===================");
            System.out.println("1) 入栈");
            System.out.println("2) 出栈");
            System.out.println("3) 重置栈");
            System.out.println("4) 打印栈");
            System.out.println("5) 取出栈顶元素");
            System.out.println("6) 退出程序");
            System.out.print("请选择你需要的功能(1~~6):");
            int i = scanner.nextInt();
            int j;
            switch (i){
                case 1:
                    System.out.print("请选择你要入栈的数字:");
                    j = scanner.nextInt();
                    stack.push(j);
                    break;
                case 2:
                    stack.pop();
                    break;
                case 3:
                    stack.reset();
                    break;
                case 4:
                    stack.print();
                    break;
                case 5:
                    ListNode top = stack.getTop();
                    System.out.println("栈顶元素为:"+top);
                    break;
                case 6:
                    p = false;
                    break;
            }
        }
    }
}

热门相关:地球第一剑   薄先生,情不由己   天启预报   豪门闪婚:帝少的神秘冷妻   霸皇纪