关于java:数据结构之栈初学只需一文

5次阅读

共计 5580 个字符，预计需要花费 14 分钟才能阅读完成。

什么是栈？
栈有什么个性？
栈怎么实现？（动态栈、动静栈）
栈具体利用？

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，绝对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的下面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

1. 栈是容许在同一端进行插入和删除操作的非凡线性表
2. 遵循先进后出 (后进先出) 的准则
3. 栈具备记忆作用，对栈插入与删除操作中，不须要扭转栈底的指针

栈也分为动态栈和动静栈：动态栈个别用数组示意，大小固定。动静栈，个别用链表示意，大小主动扩容。

接下来对两种栈类型都进行代码实操运行：

/**
 * 栈接口类
 * @author gxw
 * @date 2021/11/7 早晨 22：14
 */
public interface Stack {

    // 进栈办法
    void push(Object g);

    // 出栈办法
    Object pop();

    // 获取栈顶数据，但不移除
    Object peek();

    // 获取栈总数
    int getSize();

    // 返回栈是否为空
    boolean isEmpty();

    // 展现栈
    void display();}

/**
 * 动静栈：大小能够主动扩容
 * 动静栈依赖于链表，所以咱们须要用到 Node 结点类
 * @author gxw
 * @date 2021/11/7 早晨 22:32
 */
public class DynamicStack implements Stack {
    // 申明动静栈
    private Node topStack = new Node();

    // 栈总数
    private int size;
    @Override
    public void push(Object g) {if(size == 0)
            topStack.setData(g);
        else {
            // 申明新栈顶
            Node newTop = new Node();
            // 设置新栈顶值
            newTop.setData(g);
            // 设置新栈顶的下一个结点
            newTop.setNext(topStack);
            // 而后新栈顶正式上位栈顶
            topStack = newTop;
        }
        size++;
    }

    @Override
    public Object pop() {
        // 获取栈顶数据
        Object topData = topStack.getData();
        // 而后出栈，将旧栈顶出栈，下一个结点主动成为新栈顶
        Node newTopStack = topStack.getNext();
        topStack = newTopStack;
        size--;
        return topData;
    }

    @Override
    public int getSize() {return size;}

    @Override
    public Object peek() {if(size == 0)
            return null;
        return topStack.getData();}

    @Override
    public boolean isEmpty() {return size == 0;}

    @Override
    public void display() {
        Node topStack2 = topStack;
        System.out.println("展现栈");
        for (int i = 0;i < size;i++){System.out.print(topStack2.getData());
            System.out.print(" ");
            topStack2 = topStack2.getNext();}
        System.out.println("");
    }
}

/**
 * 单链表采纳了结点，所以须要以下定义
 * 次要两个属性，一个是数据域(存放数据内容)，一个是指针域(寄存下一个的结点的地址)
 */
public class Node {
    // 数据域
    private Object data;
    // 指针域
    private Node next;

    public Node(){this.data = new Object();
        this.next = null;
    }

    public Node(Object data, Node next){
        this.data = data;
        this.next = next;
    }

    public Node(Object data){this.data = data;}

    public Object getData() {return data;}

    public void setData(Object data) {this.data = data;}

    public Node getNext() {return next;}

    public void setNext(Node next) {this.next = next;}
}

/**
 * 动态栈：有固定大小的栈（个别以数组实现）* @author gxw
 * @date 2021/11/7 23:25
 */
public class StaticStack implements Stack {
    // 动态栈数组
    private Object[] staticStack;

    // 栈顶角标
    private int topIndex = -1;

    // 栈当初长度
    private int size;

    // 动态栈最大长度
    private int maxSize;

    /*
    构造方法，初始构建动态栈
     */
    public StaticStack(int maxSize){if(maxSize < 0)
            return;
        // 初始动态栈数组
        this.staticStack = new Object[maxSize];
        this.maxSize = maxSize;
    }

    @Override
    public void push(Object g) {
        // 如果动态栈满了，不可再入栈
        if(size == maxSize)
            return;

        // 在栈顶入栈，并栈顶角标加 1
        staticStack[++topIndex] = g;
        // 长度加一
        size++;
    }

    @Override
    public Object pop() {
        // 如果是空栈，不可出栈
        if (size == 0)
            return null;
        // 出栈，并栈顶角标减 1
        Object data = staticStack[topIndex--];
        // 长度减 1
        size--;
        return data;
    }

    @Override
    public int getSize() {return size;}

    @Override
    public Object peek() {if(size == 0)
            return null;
        return staticStack[topIndex];
    }

    @Override
    public boolean isEmpty() {return size == 0;}

    @Override
    public void display() {System.out.println("展现动态栈：");
        for (int i = topIndex;i >= 0;i--){System.out.print(staticStack[i]);
            System.out.print(" ");
        }
        System.out.println("");
    }
}

public static void main(String[] args) {
    /**
     * 动静栈
     */
    // 初始构建动静栈
    System.out.println("******** 初始化动静栈：********");
    DynamicStack dynamicStack = new DynamicStack();

    // 入栈
    System.out.println("入栈 hello world!：");
    dynamicStack.push("hello");
    dynamicStack.push("world!");
    dynamicStack.display();

    // 获取栈总数
    System.out.println("获取栈总数：");
    System.out.println(dynamicStack.getSize());

    // 出栈
    System.out.println("出栈一次");
    System.out.println("出栈值：" + dynamicStack.pop());
    dynamicStack.display();

    // 获取栈总数
    System.out.println("获取栈总数：");
    System.out.println(dynamicStack.getSize());

    /**
     * 动态栈
     */
    // 初始化动态栈
    System.out.println("******** 初始化动态栈：********");
    StaticStack staticStack = new StaticStack(10);

    // 入栈 hello world!
    System.out.println("入栈 hello world!：");
    staticStack.push("hello");
    staticStack.push("world!");
    staticStack.display();

    // 获取栈总数
    System.out.println("获取动态栈总数：");
    System.out.println(staticStack.getSize());

    // 出栈一次
    System.out.println("出栈一次：");
    System.out.println("出栈值：" + staticStack.pop());
    staticStack.display();

    // 获取栈总数
    System.out.println("获取动态栈总数：");
    System.out.println(staticStack.getSize());
}

例如：面试官：请判断 ({[]})，({[]]})，(({[]}) 这三组括号都是否合规，工夫复杂度为 O（logn）！解析：看到这个问题，我置信你脑中必定有很多试验的后果，但你会发现除了栈，其它的都很简单，而只有栈的准则，反而使这个问题很简略。咱们遇到 (,{,[，咱们都进栈，只有遇到).},] 这样的右括号就出栈，进行匹配判断即可！

接下来，咱们通过代码实操来看下：

 /**
     * 判断括号组是否合规 例如：不合规的：({[})，合规的：({[]})
     * @param str
     * @return
     */
    public static boolean isCorrectForBracketStr(String str){
        // 申明栈，在此用动态栈
        StaticStack staticStack = new StaticStack(str.length());
        // 将括号组字符串转换成字符数组
        char[] chars = str.toCharArray();
        for (int i = 0;i < chars.length;i++){char c = chars[i];
            if(c == '(' || c == '[' || c == '{'){
                // 入栈
                staticStack.push(c);
//                staticStack.display();}else if(c == ')' || c == ']' || c == '}'){
                // 判断是否为空栈, 如果是空栈，间接匹配到了右括号，则代表括号组不符合规范，返回谬误
                if(staticStack.getSize() == 0)
                    return false;

                // 取出栈顶值，进行判断，如果栈顶和 c 括号相匹配，则将栈顶出栈, 反之 不合规
                if(c == ')'){if("(".equals(staticStack.peek().toString())){
                        // 出栈
                        staticStack.pop();
//                        staticStack.display();}else{return false;}
                }

                if(c == '}'){if("{".equals(staticStack.peek().toString())){
                        // 出栈
                        staticStack.pop();
//                        staticStack.display();}else{return false;}
                }

                if(c == ']'){if("[".equals(staticStack.peek().toString())){
                        // 出栈
                        staticStack.pop();
//                        staticStack.display();}else{return false;}
                }

                // 判断栈和括号组是否匹配完，如果栈空，符号组也到最初，阐明合规，反之，则不合规
                // 判断字符组是否到最初
                if(i == chars.length - 1){
                    // 判断栈是否为空了
                    if(staticStack.getSize() == 0){return true;}else{return false;}
                }else{
                    // 如果字符组还有，但栈先空了，阐明右括号比左括号多，不合乎
                    if(staticStack.getSize() == 0)
                        return false;
                }

            }
        }
        return false;
    }

public static void main(String[] args) {
    // 括号组字符串
    String str = "({[]})";
    System.out.println(str + "字符组是否合规：" + isCorrectForBracketStr(str));

    // 括号组字符串
    String str2 = "({[]]})";
    System.out.println(str2 + "字符组是否合规：" + isCorrectForBracketStr(str2));

    // 括号组字符串
    String str3 = "(({[]})";
    System.out.println(str3 + "字符组是否合规：" + isCorrectForBracketStr(str3));
}

——————————————END——————————————————
本文为学习中的总结，心愿能够帮忙的诸位，如果贵人有发现文章有谬误之处，还请麻烦指出，谢谢！

正文完

java

发表至： java

2021-11-08

0

基于Datax的数据同步平台

关于java:前端面试题一

java集合Iterator接口

关于java:Spring-Boot-MDC-实现全链路调用日志跟踪这才叫优雅

关于.net:官宣-NET-RC-2

关于java:数据结构之栈初学只需一文

目录：

注释：

什么是栈？

栈有什么个性？

栈怎么实现？

创立栈接口类：

动静栈实现类：

动静栈依赖的 Node 结点类：

动态栈实现类：

测试：

后果：

栈具体怎么利用？

测试：

后果：

站内搜索