数据结构与算法（4）栈
由于栈比较简单，也很容易理解，学过的人都知道一句话就可以描述栈的特性：后进先出。所以这篇文章主要是写如何使用代码来描述栈，当然也是让大家很容易理解的语言。还是先给出这篇文章的大致脉络。
首先，对栈有一个基本认识
接下来，用代码实现栈，以及栈的常用操作
然后，介绍栈的几种应用场景
最后，小结一下。
OK，开始。
一、初识栈
栈其实就是一个后进先出的线性表。就好比有很多辆车进了一个死胡同，第一进去的，总是最后一个出来。下面图来演示一下：
这个图我是用画图工具画的，所以画的不好看，还请见谅，但是基本上都能看懂，第一辆进去的车，总是最后一个出去。
有了这个概念，我们再来看一下栈的分类。栈的分类是根据其存储结构来划分的。有顺序存储结构和链式存储结构。这个两种结构也会有相应的代码实现。
然后就是栈的常用操作：
（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/+。
第二步：使用栈来计算（图解）：碰见数字就入栈，碰见符号先运算。
从上面的例子应该能看懂，只需要掌握一句话：遇见数字就入栈，遇见符号就出栈，然后把结果再入栈。
2、递归
我们都知道有一个著名的函数叫斐波那契数列，它是由另外一个著名的例子引出来的
假如说兔子在出生两个月就有繁殖能力，以后一对兔子每个月能生一对小兔子，假设所有兔子不死，也不考虑近亲结婚这些情况，一年后一共有多少只兔子。
我们可以看出，几个月之后，老兔子可以生小兔子，一开始生的小兔子也可以生小小兔子了，无穷无尽。这个就是一个斐波那契数列。1:1:2:3:5:8:13.。。。。。
当我们使用栈就可以很容易解决这个问题，
代码就是一个递归函数。我可以给出
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我会在集合专题讲解，还请大家支持关注。说到底栈还是比较简单的，包括队列，其特点很容易理解，关键在于应用和平时的面试题。谢谢。
更多相关文章
- jQuery的DOM操作实例（3）——创建节点&&编写一个弹窗
- jQuery编程基础精华02（属性、表单过滤器，元素的each，表单选择器，子元
- 如何在java脚本中获取节点内部文本?
- Study JQuery《zTree自动点击第一个节点》
- 如何使用ajax GET或POST方法将数据传递到amazon lambda节点。js
- jQuery.zTree 点击节点展开折叠子节点
- easyui-tree根据叶子节点获取父节点值(N层)
- PHP递归函数删除所有子节点导致stackoverflow
- php时间函数——获取过去24小时内每个小时的节点