栈及应用
栈及应用
栈
栈是限定仅在表尾进行插入和删除操作的线性表
允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom）,不含任何数据元素的栈称为空栈。栈又称为后进先出的线性表
栈与队列
栈是限定仅在表尾进行插入和删除操作的线性表。
队列是只允许在一端进行插入操作、而在另一端进行删除操作的线性表。
栈（stack）是限定仅在表尾进行插入和删除操作的线性表。
我们把允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom），不含任何数据元素的栈称为空栈。栈又称为后进先出（LastIn First Out）的线性表，简称LIFO结构。
- 理解栈的定义需要注意：
首先它是一个线性表，也就是说，栈元素具有线性关系，即前驱后继关系。只不过它是一种特殊的线性表而已。定义中说是在线性表的表尾进行插入和删除操作，这里表尾是指栈顶，而不是栈底。
它的特殊之处就在于限制了这个线性表的插入和删除位置，它始终只在栈顶进行。这也就使得：栈底是固定的，最先进栈的只能在栈底。
栈的插入操作，叫作进栈，也称压栈、入栈。 类似子弹入弹夹，如图4-2-2所示。
栈的删除操作，叫作出栈，也有的叫作弹栈。 如同弹夹中的子弹出夹，如图4-2-3所示。
4-2-2
4-2-3
栈的顺序存储结构
既然栈是线性表的特例，那么栈的顺序存储其实也是线性表顺序存储的简化，我们简称为顺序栈。线性表是用数组来实现的，下标为0的一端作为栈底比较好，因为首元素都存在栈底，变化最小，所以让它作栈底。
栈的顺序存储结构
栈的链式存储结构
链式存储结构：是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。数据元素的存储关系并不能反映其逻辑关系，因此需要用一个指针存放数据元素的地址，这样通过地址就可以找到相关联数据元素的位置（如图1-5-6所示）。
1-5-6
栈的实现
顺序方式
-
入栈操作
入栈操作
/* 插入元素e为新的栈顶元素 */
Status Push(SqStack *S, SElemType e)
{
/* 栈满 */
if (S->top == MAXSIZE - 1)
{
return ERROR;
}
/* 栈顶指针增加一 */
S->top++;
/* 将新插入元素赋值给栈顶空间 */
S->data[S->top] = e;
return OK;
}
- 出栈操作
/* 若栈不空，则删除S的栈顶元素，用e返回其值，
并返回OK；否则返回ERROR */
Status Pop(SqStack *S, SElemType *e)
{
if (S->top == -1)
return ERROR;
/* 将要删除的栈顶元素赋值给e */
*e = S->data[S->top];
/* 栈顶指针减一 */
S->top--;
return OK;
}
两者没有涉及到任何循环语句，因此时间复杂度均是O(1)。
- Stack.java源码
Java Stack的详细实现分析
面试常问：Vector与ArrayList区别
Vector与ArrayList一样，也是通过数组实现的，不同的是它支持线程的同步，即某一时刻只有一个线程能够写Vector，避免多线程同时写而引起的不一致性，但实现同步需要很高的花费，因此，访问它比访问ArrayList慢。
参考
链式方式
-
对于链栈来说，基本不存在栈满的情况，除非内存已经没有可以使用的空间，如果真的发生，那此时的计算机操作系统已经面临死机崩溃的情况，而不是这个链栈是否溢出的问题。
但对于空栈来说，链表原定义是头指针指向空，那么链栈的空其实就是top=NULL的时候。 -
入栈操作
“对于链栈的进栈push操作，假设元素值为e的新结点是s，top为栈顶指针，示意图如下图所示代码如下。”
/* 插入元素e为新的栈顶元素 */
Status Push(LinkStack *S, SElemType e)
{
LinkStackPtr s
= (LinkStackPtr)malloc(sizeof(StackNode));
s->data = e;
/* 把当前的栈顶元素赋值给新结点的直接后继，如图中① */
s->next = S->top;
/* 将新的结点s赋值给栈顶指针，如图中② */
S->top = s;
S->count++;
return OK;
}
-
出栈操作
至于链栈的出栈pop操作，也是很简单的三句操作。假设变量p用来存储要删除的栈顶结点，将栈顶指针下移一位，最后释放p即可。
出栈操作
/* 若栈不空，则删除S的栈顶元素，用e返回其值，
并返回OK；否则返回ERROR */
Status Pop(LinkStack *S, SElemType *e)
{
LinkStackPtr p;
if (StackEmpty(*S))
return ERROR;
*e = S->top->data;
/* 将栈顶结点赋值给p，如图③ */
p = S->top;
/* 使得栈顶指针下移一位，指向后一结点，如图④ */
S->top = S->top->next;
/* 释放结点p */
free(p);
S->count--;
return OK;
}
链栈的进栈push和出栈pop操作都很简单，没有任何循环操作，时间复杂度均为O(1)。
对比一下顺序栈与链栈，它们在时间复杂度上是一样的，均为O(1)。
对于空间性能来说
顺序栈需要事先确定一个固定的长度，可能会存在内存空间浪费的问题，但它的优势是存取时定位很方便;
而链栈则要求每个元素都有指针域，这同时也增加了一些内存开销，但对于栈的长度无限制。所以它们的区别和线性表中讨论的一样，如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最好是用链栈，反之，如果它的变化在可控范围内，建议使用顺序栈会更好一些。
逆波兰表达式
-
标准四则运算表达式—中缀表达式
9+(3-1)X3+10/2 20
计算机采用—后缀表达式
9 3 1 - 3 * + 10 2 / + 20 -
中缀表达式转换成后缀表达式
-
下图中横向表示栈顶，竖向表示取到的操作符
-
数字输出，运算符进栈，括号匹配出栈，比栈顶优先级低就出栈（表中1>2）
-
计算结果
1.数字入栈
2.符号就取2个进行计算，再入栈
递归基础
程序调用自身的编程技巧称为递归（recursion）。
- 递归定义
在高级语言中，调用自己和其他函数并没有本质的不同。我们把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称做递归函数。
递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法
它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，
递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。
递归的能力在于用有限的语句来定义对象的无限集合。
一般来说，递归需要有边界条件、递归前进段和递归返回段。
当边界条件不满足时，递归前进；当边界条件满足时，递归返回。
执行特点
斐波那契数列
如果兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。假设所有兔都不死，那么一年以后可以繁殖多少对兔子呢？
我们拿新出生的一对小兔子分析一下：第一个月小兔子没有繁殖能力，所以还是一对；两个月后，生下一对小兔子数共有两对；三个月以后，老兔子又生下一对，因为小兔子还没有繁殖能力，所以一共是三对……依次类推可以列出下表
如果用数学函数式来定义就是：
下面是java代码实现：
/**
* fibonacciSequence数列 8=7+6 7=6+5 6=5+4
* 1 1 2 3 5 8 13 21 34 55 89 144......
* 返回第n项
*/
public int fibonacciSequence(int n){
if(n==1 || n==2){
return 1;
}else{
return fibonacciSequence(n-1)+fibonacciSequence(n-2);
}
}
汉诺塔算法
从左到右有A、B、C三根柱子，其中A柱子上面有从小叠到大的n个圆盘，现要求将A柱子上的圆盘移到C柱子上去，期间只有一个原则：一次只能移到一个盘子且大盘子不能在小盘子上面，求移动的步骤和移动的次数
/**
* @param n 盘子的个数
* @param start 开始的柱子
* @param middle 中介柱子
* @param end 结果柱子
*/
public static void hanoi(int n,int start,int middle,int end){
if(n<=1){
System.out.println(start+"----->"+end);
}else{
hanoi(n-1,start,end,middle);
System.out.println(start+"----->"+end);
hanoi(n-1,middle,start,end);
}
}
摘录来自: 程杰. “大话数据结构。” Apple Books.
