关于数据结构和算法:数据结构与算法分析学习笔记四-栈

0次阅读

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

软件世界是事实世界的投影。

软件世界的一些概念大多都不是凭空发明，这些概念大多都是从事实世界形象而来。就像咱们本文所探讨的 ” 栈 ” 一样，日常生活中也有这样的模型，比方叠成一摞的碗，最先搁置的反而放在最上面，像上面这样:

这与排队相同。排队对应的一种数据结构，咱们称之为队列。事实上栈这种数据结构在日常应用中还是十分罕用的，就比如说撤销操作，这是软件内广泛内置的操作，就像咱们在日常编码中做了一些批改，想回到上一步，咱们个别就是应用 ctrl + z。软件按工夫记录下了你的操作或者是输出，像上面这样:

工夫最靠前的反而在最上面，这样咱们就能吃后悔药了。在比方咱们写代码中的括号匹配，如果少写了一个，编译器是如何晓得的呢？咱们来剖析一下这个问题:

编号为括号的进入程序, 每个右括号将与最近遇到的那个未匹配的左括号相匹配，即 ” 后进的先出, 或者先进的后出 ”。

领会一下下面的话，每个右括号将与最近遇到的那个未匹配的左括号相匹配。咱们用 p 记录左括号的最新地位，用 q 指向以后新进入的括号，将 p 与 q 相比对，如果相匹配，则删除左括号，p 后退一位。如果匹配到最初还是有残余的左括号那么这个括号就是不匹配的。

再比方咱们罕用的函数相互调用，Java 总是从一个 main 函数开始，如果咱们的代码是 main 办法调用 a 办法，a 办法外面又调用 c 办法，c 办法外面又调用 d 办法，那么不言而喻的是 d 办法执行结束之后再执行 c 办法，c 办法执行完才执行 a 办法。这种执行模型也很像栈:

认真领会下面的用例，这些问题的独特的特点就是处理过程中都具备 ” 后进先出 ” 的个性，这是一类典型的问题，咱们将其形象进去也就是数据结构中的 ” 栈 ” 模型。上面开始解说一些栈的概念和一些根本利用。

上面是栈的一种示意图:

你能够将示意图中的长方体了解为一个竹筒，最下面闭口，最上面关闭，外面放的是写有编号的小球，放入程序根据小球程序，从小到大。如果咱们想从这个竹筒中取球，能够发现一种法则: 先放进去的只能后拿进去; 反之，后放进去的小球可能先拿进去，也就是先进后出，这是栈的典型特点。

当咱们把下面构造中的小球形象为数据结构中的结点时，因为结点间的关系是线性的，因而它也属于线性表，又因为它的操作只能在同一端进行，因而它是一个运算受限的线性表，咱们将这种类型线性表称之为栈。

当初咱们给出栈的定义: 栈是一种非凡的线性表，它所有的插入和删除都限度在表的同一端进行。栈中容许容许进行插入、删除操作的一段叫栈顶(top)，另一端则叫栈底(bottom)。当栈中没有元素时，称之为空栈

栈中的插入运算咱们通常称之为压栈、进栈或入栈 (PUSH), 栈的删除运算通常被称为弹栈(push) 出栈 (pop).
第一个进栈的元素在栈底，最初一个进栈的元素在栈顶，第一个出栈的元素为栈顶元素，最初一个出栈的元素为栈底元素。

可能会有人感觉为什么要引入栈，或者间接用数组和链表实现栈不就行了吗？为什么要专门划出一种数据结构来? 原则上咱们前面讲的队列、树、图也都是用数组和链表来实现，每一种数据结构都对应了一类专门的数据处理问题，像栈专门解决 ” 先进后出 ”，同时也简化了程序设计思路，放大了咱们的思考范畴。就算是用数组来实现栈，咱们也得让内部调用者无需放心下标越界以及增减的问题，那么这就是一种新的数组，只不过咱们习惯上用栈来称说而已。

同线性表根本相似，栈的根本运算如下:

栈初始化操作: 建设一个空栈表
栈判空: 判断栈是否为空
取栈顶元素: 取栈顶元素的值
压栈: 在栈 S 中插入元素 e, 使其成为新的栈顶元素
弹栈: 删除栈 S 的元素。

当初的许多高级语言，比如说 Java、C# 都内置了对栈数据结构的封装，咱们能够不必关注栈的实现细节，而间接应用对栈的 push 和 Pop 的操作。同时也能够借鉴设计思路。

用数组实现的栈咱们称之为程序栈，用链表实现的栈咱们个别就称之为链栈。对于程序栈其实也能够再进行细分，一种是一开始就给定栈的大小，入栈超出大小的时候咱们能够抉择将栈底的上一个元素称为栈底元素。第二种咱们称之为动静栈，栈的大小是动静的，也就是动静扩容，超出栈的下限的时候，主动扩容，栈的大小根本取决于内存的大小。

咱们尝试用数组来实现以下程序栈，其实程序栈相干的设计也能够参考 Java 中的相干的设计思路，咱们来看下 Java 中的 Stack:

操作也与咱们下面探讨的统一。那 peek 和 pop 有什么区别:

peek 取栈顶的元素不删除
pop 取栈顶的元素删除并返回栈顶元素
Java 中 Stack 的设计思路:
栈判空看数组的理论容量
push 操作将元素增加到数组的开端
peek 操作返回数组最初一个元素

pop 操作返回数组的最初一个元素, 同时栈顶元素向后挪动一个地位
咱们也能够让咱们建的程序栈继承咱们在数据结构与算法剖析(三) 线性表 SequenceList，这样扩容操作咱们就不必在重写一遍，只用实现栈的办法就能够了。对于办法的设计咱们能够齐全借鉴 Java 中的 Stack:

public class SequenceStack extends SequenceList {public SequenceStack() { }
  public int push(int data){add(data);
      return data;
  }
  /**
   * 返回数组的最初一个元素, 同时栈顶元素向后挪动一个地位
   * @return
   */
  public int pop(){if (size() == 0){// 抛出异样}
      int data = peek();
      remove(size() - 1);
      return data;
  }

  public int peek(){if (size() == 0){// 抛出异样}
      return  get(size()  - 1);
  }

  public boolean empty(){return size() == 0;
  }
}

采纳链式存储形式的栈咱们称之为链栈或链式栈。链栈有一个个结点形成，每个结点蕴含数据数据域和指针域两局部。在链式栈中，利用每一个结点的存储域存储栈中的每一个元素，利用指针域来示意元素之间的关系。像上面这样:

public class LinkedStack {
  private Node top; // 指向栈顶元素
  private class Node{
      private int data;
      private Node next;

      public Node(int data , Node next){
          this.data = data;
          this.next = next;
      }
      public int getData() {return data;}

      public Node getNext() {return next;}
  }

  public LinkedStack() {}
  /**
   * @param data
   * @return
   */
  public int push(int data){Node node = new Node(data,top);
      top = node;
      return data;
  }

  public int pop(){return peek();
  }

  public int peek(){
      int data = top.data;
      top = top.next;
      return data;
  }
  public boolean empty() {return top == null;}
}

十进制数到 R 进制数的转换，咱们个别采纳的办法是十进制数和进制取余，最高位往往是最初才呈现，刚好合乎后入先出的栈。例如 1024 转 8 进制:

最高位最初呈现, 但栈刚好是后进先出。进制转换示例:

 /**
     * 进制转换
     * @param input
     * @param decimal
     */
    private static void binaryConversion(int input, int decimal) {if(decimal == 0){return;}
        Stack<Integer> stack = new Stack<>();
        while (input != 0){stack.push(input % decimal);
            input = input /  decimal;
        }
        String result =  "";
        while (!stack.empty()){result = result + stack.pop();
        }
        System.out.println(result);
    }