数据结构中的队列的知识（数据结构-栈和队列.md）

数据结构中的队列的知识（数据结构-栈和队列.md）链栈的入栈 1.2 栈的链式存储数据结构（链式栈）栈的抽象数据类型分为顺序栈和链式栈两种 栈接口的继承和实现关系如下图 1.1 栈的顺序存储结构（顺序栈）如用数组实现，栈底是下标为0的元素。

栈与队列数据结构概述

栈是限定仅在表尾进行插入和删除操作的线性表；

队列是只允许在一端进行插入操作、而在另一端进行删除操作的线性表;

1 栈

允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom） 不含任何数据元素的栈称为空栈。栈又称为后进先出的线性表，栈的数据存储结构分为以下两种。

栈的抽象数据类型分为顺序栈和链式栈两种 栈接口的继承和实现关系如下图

1.1 栈的顺序存储结构（顺序栈）

如用数组实现，栈底是下标为0的元素。

1.2 栈的链式存储数据结构（链式栈）

链栈的入栈

链栈的出栈

1.3 栈的应用场景

** 1、栈是嵌套调用机制的实现基础**

嵌套调用定义：在一个函数中调用另一个函数被称为嵌套调用。

由于函数的调用顺序和返回顺序正好相反，如果借助一个栈“记住”函数从何而来，就能获得函数的返回路径。

当函数被调用的时候操作系统将该函数的有关信息（地址，参数，局部变量等）入栈这个过程称为保护现场。

一个函数执行完返回时，出栈，获得调用函数信息，称为恢复现场，程序返回调用函数继续运行。

** 2、 逆波兰表达式 **

定义：

传统的四则运算被称作是中缀表达式，即运算符实在两个运算对象之间的。逆波兰表达式被称作是后缀表达式，表达式是在运算对象的后面。

逆波兰表达式：

a b ---> a b

a (b-c) ---> a b c -

a (b-c)d ---> a b c - d

a d(b-c)--->a d b c -

a=1 3 ---> a=1 3

http=(smtp http telnet)/1024 写成什么呢？

http=smtp http telnet 1024 /

代码实现 :

/** * 计算算数表达式的值 * For example: * ["2" "1" " " "3" "*"] -> ((2 1) * 3) -> 9 * ["4" "13" "5" "/" " "] -> (4 (13 / 5)) -> 6 * @author zl * 思路： * 这个问题可以通过使用堆栈来解决。 * （1）我们可以循环遍历给定数组中的每个元素。 * （2）当它是一个数字，把它推到堆栈。 * (3) 当它是一个操作符时，从堆栈中弹出两个数字，进行计算，并推回结果。 * */ public class EvaluateValueOfArithmeticExpression { private static void evoe(String[] strArr){ String str = " -*/"; Stack<String> stack = new Stack<String>(); //2.0遍历数组中的每一个元素 for(String s : strArr){ if(!str.contains(s)){//如果是数字 放入栈中 stack.push(s); }else{ int a = Integer.valueOf(stack.pop()); int b = Integer.valueOf(stack.pop()); switch(s){ case " " : stack.push(String.valueOf(a b)); break; case "-" : stack.push(String.valueOf(b-a)); break ; case "*" : stack.push(String.valueOf(a*b)); break; case "/" : stack.push(String.valueOf(b/a)); break ; } } } System.out.println(stack.pop()); } public static void main(String[] args) { //1.0创建数组 String [] strArr = { "0" "2" "-" "3" " " }; evoe(strArr); }

2 队列

队列（Queue）只允许一端进行插入一端进行删除的线性表。插入的一端称为队尾（Rear），删除的一端称为队头（Front）。其中插入元素的过程叫做入队（Enqueue），删除元素过程叫做出队（Dequeue）

队列的存储结构分为顺序存储，链式存储。如下

2.1 队列的顺序存储

1. 使用顺序表，出队效率低。

入队操作执行顺序表队尾插入时间复杂度为o(1) 出队操作顺序表头删除元素，需要将所有元素向前移动所以时间复杂度为o(n)因此出队效率低。

1. 使用数组，存在假溢出。

不是因为存储空间不足（元素出队后会有释放空间）而产生的溢出称之为假溢出。

2.2 队列的链式存储结构

队列的链式存储结构其实就是链表的单链表。只不过只允许头出、尾进。如下图：