【数据结构之栈、队列、数组】

3.1栈

• 3.1栈

  定义：只允许在一端进行插入或删除操作的线性表

  结构：栈顶（top）：线性表允许插入删除的那一端

  栈底（bottom）：固定的，不允许插入删除的那一端

  基本操作：初始化initStack、判空stackEmpty、出栈Pop、读栈顶getPop、销毁栈destoryStack

  顺序栈：采用顺序存储的栈为顺序栈，存放自栈底到栈顶的数据元素，附设一个指针（top）指示当前栈的位置。

  栈顶指针：S.top

  栈顶元素：S.data[S.top]

  栈空条件：S.top==-1 栈满条件;S.top==Maxsize-1 栈长：S.top+1

  基本操作：初始化initStack、判空stackEmpty、出栈Pop、读栈顶getPop、销毁栈destoryStack

3.2队列

• 3.2队列

  1、基本概念

  定义：只允许在一端插入另一端删除的线性表，先进先出

  队头：允许删除的一端；队尾：允许插入的一端；空队列：不含任何元素的空表

  插入元素叫入队；删除元素叫离队

  队头指针front，队尾指针rear

  基本操作：初始化initQueue、判空QueueEmpty、enQueue入队、deQueue离队、getHead（Q，&x）读队头元素

  2、顺序存储队列

  顺序队列：采用顺序存储的队列为顺序队列，存放数据元素，附设两个指针，

  队头指针front指向队头元素，队尾指针rear指向队尾元素。

  初始条件：Q.frontQ.rear0

  进队操作：队不满时，送至队尾元素，rear指针加一

  出队操作：队不空时，先取出队头元素，front指针加一

  

  循环队列：特殊的顺序存储队列，把元素从逻辑上视为一个环

3、链式存储队列

链队列：同时带头指针和尾指针的单链表。

可分为带头结点和不带头结点

当Q.frontnull，Q.rearnull时，链队列为空

4、双端队列

双端队列：只允许从双端插入和删除的线性表

例子：

栈

输入受限的

输出受限

3.3栈和队列的应用

• 3.3栈和队列的应用

  1、括号匹配

  最后出现的左括号最先匹配（先进先出）
  
  

  实现算法;

  

  2、表达式求值

3、递归

计算正整数的阶乘n!;求斐波那契数列

函数调度栈可称为递归工作栈，每进一层，将递归调用信息压入栈顶，每出一层递归，从栈顶弹出信息，缺点是太多层递归会导致栈溢出。

4、队列的应用

OS中解决多用户引起的资源竞争问题；解决外部设备和主机速度不匹配问题；实现图的广度有限遍历；树的层次遍历

3.4矩阵

• 3.4矩阵（不是重点）

  对称矩阵

  三角矩阵

  三对角矩阵

  稀疏矩阵
  

6.25、6.26、6.28