乐趣区

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

作者：

jiezi

在

目录：

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

注释：

什么是栈？

栈（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("");
    }
}

动静栈依赖的Node结点类：

/**
 * 单链表采纳了结点，所以须要以下定义
 * 次要两个属性，一个是数据域(存放数据内容)，一个是指针域(寄存下一个的结点的地址)
 */
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——————————————————
本文为学习中的总结，心愿能够帮忙的诸位，如果贵人有发现文章有谬误之处，还请麻烦指出，谢谢！

评论

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

这个站点使用 Akismet 来减少垃圾评论。了解你的评论数据如何被处理。

更多文章