数据结构与算法--栈（Stack）

"数据结构与算法"不管是在Java还是在任何语言中都是核心基础知识，就像是盖楼的地基一样，它被广泛的应用于架构的最底层，对于这部分知识的掌握程度能够决定读者以后的高度。

出于这个初衷开更本系列文章，希望能对读者有所帮助。

读者的收获

1、了解栈的结构

2、栈的特性

3、栈的实现方式

4、栈的日常应用

1

栈的结构

”栈“是一种“操作受限”的数据结构，栈的顶端叫做“栈顶”，栈的底端叫做“栈底”，对于数据的插入操作叫做“入栈”，剔除数据叫做“出栈”。

2

栈的特性

1、数据的“插入”和“删除”只能从栈顶操作，也就是单端操作（中端和底端都不可）。

2、顺序入栈，倒序出栈，即先入后出，后入先出原则。

看到这里读者可能会想：“栈这种只能单端操作的特性使得栈的灵活性很差，那这种数据结构到底有何用处呢？”，带着这个疑问后面为你解答。

3

栈的实现方式

前面两篇文章已经介绍了“数组”、“链表”两种数据结构，之所以将这两个放到前面讲是因为之后的一些数据结构会基于这两个实现，本篇的“栈”就是典型例子：

补课通道

数据结构与算法--数组（Array）

数据结构与算法--链表（Linked list）

一、基于数组的：顺序栈

1、定义数组

//定义数组，长度10
int[] arr = new int[10]; 
//记录数组中元素个数
int count = 0;

2、入栈

public boolean push(int newInt) {
  // 数组空间不够了，直接返回false，入栈失败。
  if (count > 10) return false;
  // 将item放到下标为count的位置，并且count加一
  items[count] = newInt;
  count++;
  return true;
}

3、出栈

public boolean pop() {
  // 栈为空，则直接返回null
  if (count == 0) return false;
  // 返回下标为count-1的数组元素，并且栈中元素个数count减一
  String tmp = items[count-1];
  count--;
  return true;
}

二、基于链表的：链式栈

1、定义链表

// 链表的第一个节点充当栈顶元素
LinkStack.Entry<Integer> bottom =new LinkStack.Entry<Integer>(null, null); 
int count; // 记录链表节点的个数

2、入栈

public void push(Integer val){
    //插入栈顶节点
    LinkStack.Entry<Integer> node = new LinkStack.Entry<Integer>(val, bottom.next);
    //将链表头部指针指向新的栈顶节点
    bottom.next = node;
    count++;
}

3、出栈

public boolean pop(){
    //链式栈为空，返回失败
    if(bottom.next == null) return false;
    //链表头部指针指向顺延栈顶节点
    bottom.next = bottom.next.next;
    count--;
    return true;
}

通过上面的介绍读者已经了解了栈的两种实现方式，接下来就为读者解答刚才的疑问，栈的应用：

4

栈的日常应用

在构思这一模块的时候，收集了大量网络资料，总结出最常用的两种应用场景，供读者参考：

一、浏览器网页前进、后退功能

通常在浏览器中，当你在页面A进行了一系列跳转B>C，浏览器的左上角会为你提供后退和前进功能，也就是说从C可以后退回B，然后又可以从B再前进到C，这背后的设计思路就可以用栈数据结构来实现：

准备两个栈，分别存放前进页、后退页

二、编译器的表达式运算

对于计算一个表达式来说，人脑和计算机的逻辑是不一样的，举个例子：6+4*9-2，对于人脑来说直接从左到右计算即可，但对于计算机来说这个表达式是难以理解且无法直接计算的，需要通过两个栈来实现计算逻辑：