运维开发网

数据结构与算法(4)栈

运维开发网 https://www.qedev.com 2021-01-17 08:32 出处:51CTO 作者:mb5ffd6fed5661e
由于栈比较简单,也很容易理解,学过的人都知道一句话就可以描述栈的特性:后进先出。所以这篇文章主要是写如何使用代码来描述栈,当然也是让大家很容易理解的语言。还是先给出这篇文章的大致脉络。首先,对栈有一个基本认识接下来,用代码实现栈,以及栈的常用操作然后,介绍栈的几种应用场景最后,小结一下。OK,开始。一、初识栈栈其实就是一个后进先出的线性表。就好比有很多辆车进了一个死胡同,第一进去的,总是最后一个出

由于栈比较简单,也很容易理解,学过的人都知道一句话就可以描述栈的特性:后进先出。所以这篇文章主要是写如何使用代码来描述栈,当然也是让大家很容易理解的语言。还是先给出这篇文章的大致脉络。

首先,对栈有一个基本认识

接下来,用代码实现栈,以及栈的常用操作

然后,介绍栈的几种应用场景

最后,小结一下。

OK,开始。

一、初识栈

栈其实就是一个后进先出的线性表。就好比有很多辆车进了一个死胡同,第一进去的,总是最后一个出来。下面图来演示一下:

数据结构与算法(4)栈

这个图我是用画图工具画的,所以画的不好看,还请见谅,但是基本上都能看懂,第一辆进去的车,总是最后一个出去。

有了这个概念,我们再来看一下栈的分类。栈的分类是根据其存储结构来划分的。有顺序存储结构和链式存储结构。这个两种结构也会有相应的代码实现。

然后就是栈的常用操作:

(1)判断栈是否为空、是否已满

(2)入栈、出栈操作

(3)获取栈顶元素

(4)获取栈的大小

这里面比较重要的就是入栈和出栈操作了。因此下面先用两张图来表示一下,入栈和出栈的操作。

然后就是出栈操作

OK,到这首先总结一下,在第一部分,提到栈的特点:后进先出。然后讲有两个分类,最后给出了常用方法。下面这一部分就开始使用代码去实现一个栈了。

二、栈的实现

1、顺序栈

顺序栈是根据顺序存储结构来写的,底层是由数组来实现的。因此在这里我们不需要定义节点,在这里用java代码实现顺序栈有两个步骤,

第一:定义栈的接口,接口内部定义了栈的常用操作方法

第二:然后就是接口的实现了。

下面按照这个步骤一步一步来看。

第一步:定义接口

public interface Stack {

   //入栈

   public void push(Object obj) throws Exception;

   //出栈

   public Object pop() throws Exception;

   //获取栈顶元素

   public Object getTop() throws Exception;

   //判断栈是否为空

   public boolean isEmpty();

}

第二步:接口的实现

//顺序栈

public class SqStack implements Stack {

   Object[] stack; //对象数组,顺序栈是用数组来实现的

   final int defaultSize = 10; //默认长度

   int top; //栈顶位置(的一个下标)

   int maxSize; //最大长度

   //无参构造方法:默认长度

   public SqStack() {

       init(defaultSize);

  }

   //带参构造方法:最大长度

   public SqStack(int size) {

       init(size);

  }

   public void init(int size) {

       this.maxSize = size;

       top = 0;

       stack = new Object[size];

  }

   //获取栈顶元素

   @Override

   public Object getTop() throws Exception {

       if (isEmpty()) {

           throw new Exception("堆栈为空!");

      }

       return stack[top - 1];

  }

   //判断栈是否为空

   @Override

   public boolean isEmpty() {

       return top == 0;

  }

    //入栈操作

   @Override

   public void push(Object obj) throws Exception {

       //首先判断栈是否已满

       if (top == maxSize) {

           throw new Exception("栈已满!");

      }

       stack[top] = obj;

       top++;

  }

   //出栈操作

   @Override

   public Object pop() throws Exception {

       if (isEmpty()) {

           throw new Exception("栈空!");

      }

       top--;

       return stack[top];

  }

}

从上面的操作可以看到,一共实现了4个方法,其中有两个构造方法和初试化方法。有一个知识点需要掌握,就是入栈的时候,先插入再移动。出栈的时候,先移动再插入。代码很简单。注释的很清晰。毕竟只有当你有需要的时候,才会去认真看代码。下面看看链式栈

2、链式栈

这个链式栈就需要你定义节点了,因为链式栈的每一个节点要存的信息比较多,比如当前节点的数据值,还有下一个节点的地址,因此实现一个链式栈,也需要两个步骤:

第一:定义节点

第二:根据节点定义栈的接口

第三:实现接口

下面就根据上面的步骤来一步一步实现:

第一步:定义节点

//结点类

public class Node {

   Object element; //数据

   Node next;  //下一个节点的指针

   //头结点的构造方法

   public Node(Node nextval) {

       this.next = nextval;

  }

   //非头结点的构造方法

   public Node(Object obj, Node nextval) {

       this.element = obj;

       this.next = nextval;

  }

//getter和setter方法

//toString方法

}

第二步:根据节点定义接口:

//栈接口

public interface Stack {

   //入栈

   public void push(Object obj) throws Exception;

   //出栈

   public Object pop() throws Exception;

   //获得栈顶元素

   public Object getTop() throws Exception;

   //判断栈是否为空

   public boolean isEmpty();

}

第三步:实现栈接口

public class LinkStack implements Stack {

   Node head;  //栈顶指针

   int size;  //结点的个数

   public LinkStack() {

       head = null;

       size = 0;

  }

//取得栈顶元素

   @Override

   public Object getTop() throws Exception {

       return head.getElement();

  }

   //判断栈是否为空

   @Override

   public boolean isEmpty() {

       return head == null;

  }

   //入栈

   @Override

   public void push(Object obj) throws Exception {

       head = new Node(obj, head);

       size++;/大小增加一个

  }

//出栈

   @Override

   public Object pop() throws Exception {

       if (isEmpty()) {

           throw new Exception("栈为空!");

      }

       Object obj = head.getElement();

       head = head.getNext();//将栈顶指针指向下一个

       size--;//大小减小一个

       return obj;

  }

}

OK,这个链式栈其实和顺序栈差不多,稍微麻烦一点,不过这些代码看起来也比较简单,比如说我出栈的时候要先判断当前栈是否为空。入栈的时候要判断栈是否已满。有了对栈的基本操作,我们就可以进入下一阶段的学习,也就是栈的使用场景

三、栈的使用场景

1、表达式计算

比如现在有一个表达式1+(4-6*3)/2=2。然后我们使用栈,看看如何去计算他。

第一步:我们需要将这个表达式表示为后缀表达式1463*-2/+。

第二步:使用栈来计算(图解):碰见数字就入栈,碰见符号先运算。

数据结构与算法(4)栈

从上面的例子应该能看懂,只需要掌握一句话:遇见数字就入栈,遇见符号就出栈,然后把结果再入栈。

2、递归

我们都知道有一个著名的函数叫斐波那契数列,它是由另外一个著名的例子引出来的

假如说兔子在出生两个月就有繁殖能力,以后一对兔子每个月能生一对小兔子,假设所有兔子不死,也不考虑近亲结婚这些情况,一年后一共有多少只兔子。

我们可以看出,几个月之后,老兔子可以生小兔子,一开始生的小兔子也可以生小小兔子了,无穷无尽。这个就是一个斐波那契数列。1:1:2:3:5:8:13.。。。。。

当我们使用栈就可以很容易解决这个问题,

数据结构与算法(4)栈

代码就是一个递归函数。我可以给出

public class Demo {

   public static int f(int n) throws Exception {

       if(n==0){

          throw new Exception("参数错误!");

      }

       if (n == 1 || n == 2) {

           return 1;

      } else {

           return f(n-1)+f(n-2);//自己调用自己

      }

    }

   public static void main(String[] args) throws Exception {

       for (int i = 1; i <=10; i++) {

           System.out.print(f(i)+" ");

      }

  }  

}

3、括号匹配

这个问题,说实话自己是最熟悉的,因为我考研究生的时候,机试就有这道题,还在考前狠狠的复习了好几遍。括号匹配跟表达式求解的形式差不多,但是稍微有一点出入。举个例子吧

输入一个字符串 里面只含有 [ , ] , ( , ) 四种括号 ; 现要求判断这个字符串 是否满足括号匹配 。如    ([])()    是匹配的    ([)]是不匹配的

给出代码

public void check(String str) {

    Stack<Character> stack = new Stack<Character>();

    // 如果该String长度为奇数,不匹配

    if (str.length() % 2 == 1) {

        System.out.println("No");

    } else {

    stack = new Stack<Character>();

    for (int i = 0; i < str.length(); i++) {

               // 当前栈是空的 存入当前位置的字符

        if (stack.isEmpty()) {

            stack.push(str.charAt(i)); 

        } else if ((stack.peek() == '[' && str.charAt(i) == ']')

            || (stack.peek() == '(' && str.charAt(i) == ')')) {

                stack.pop();

// 满足上面的条件 表示相邻的两个字符是一对匹配的括号 进行出栈操作

        } else {

            stack.push(str.charAt(i));

        }

    }

 //最后看栈内的情况,如果为空那么说明全部匹配,如果不为空说明有符号为匹配。

        if (stack.isEmpty()) {

            System.out.println("Yes");

        } else {

            System.out.println("No");

        }

    }

}

四、总结

由于这里主要讲解数据结构中的栈,所以就不给出java中的栈了,java中的stack我会在集合专题讲解,还请大家支持关注。说到底栈还是比较简单的,包括队列,其特点很容易理解,关键在于应用和平时的面试题。谢谢。

扫码领视频副本.gif

0

精彩评论

暂无评论...
验证码 换一张
取 消

关注公众号