1、栈和队列的定义和特点

栈和队列是两种常用的，重要的数据结构，栈和队列是限定插入和删除只能在表的“端点”进行的特殊的线性表。

栈的特点是先进后出，由于栈具有这个特点，使得栈称为程序设计中的有用工具，如果问题求解的过程具有先进后出的特点，则求解的算法中必然需要利用到栈。如下述问题的算法设计，都需要用到栈：数值转换，表达式求解，括号匹配的检验，八皇后问题，行编辑程序，函数调用，迷宫求解，递归调用的实现。

Insert(S,n+1,e);//栈只能插入表尾部
Delete(S,n);  //栈只能删除表尾部

队列的特点是先进先出，由于队列的这个特点，使得队列称为程序设计中解决类似排队问题的有用工具：脱机打印输出；多用户系统中，多个用户排成队，分时循环使用CPU和主存；按用户的优先级排成多个队，每个优先级一个队列；实时控制系统中，信号按接收的先后顺序依次处理；网络电文传输，按到达时间先后顺序依次进行

Insert(Q,n+1,e);//队列只能插入表尾部
Delete(Q,1);  //队列只能删除表头部

栈和队列是线性表的子集，是插入和删除位置受限的线性表。

2、栈-stack

栈是仅在表尾进行插入、删除操作的线性表。表尾(即 a n a_n an端)称为栈顶Top；表头(即 a 1 a_1 a1端)称为栈底Base。

插入到栈顶的操作，称为入栈；从栈顶删除最后一个元素的操作，称为出栈。

栈总结：

3、队列-queue

队列是一种先进先出(FIFO)的线性表。在表的一端插入(表尾)，在另一端(表头)删除。

KaTeX parse error: Undefined control sequence: \qquda at position 1: \̲q̲q̲u̲d̲a̲队列总结：

4、栈和队列的案例

4.1 进制转换-栈

十进制整数N向其他进制数d(二、八、十六)的转换是计算机实现的基本问题。转换的法则是：除以d倒取余数，该法则对应一个简单的算法原理：

n=(n  div  d)∗d+n  mod  d

其中，div为整除运算，mod为求余运算。

string BaseConversion(long long orgNum, int base)
{
  string res;
  if (orgNum == 0 || base == 0)
    return res;
  bool posiFlag = true;
  if (orgNum < 0)
    posiFlag = false;
  orgNum *= !posiFlag  ? -1:1;    //将初始数字全部转化为正数
  stack<int> tRes;    //记录结果栈
  while (orgNum)
  {
    tRes.push(orgNum % base);
    orgNum /= base;
  }
  if (!posiFlag)
    res.push_back('-');
  while (!tRes.empty())
  {
    res.push_back(tRes.top() + '0');
    tRes.pop();
  }
  return res;
}

4.2 检验括号是否匹配-栈

假设表达式中允许包含两种括号，圆括号和方括号，其嵌套的书序随意，但是括号之间左括号和右括号出现的嵌套顺序必须相同，同时，左右括号的数量必须匹配。

算法思路如下：可以利用一个栈的结构保存每个出现的左括号，当遇到右括号时，从栈中弹出左括号，检验匹配情况。在检验的过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论：

(1) 当遇到某一个右括号时，栈已经空了，说明有括号多于左括号；

(2) 从栈中弹出的左括号与当前检验的右括号的类型不同，说明出现了类型交叉的情况；

(3) 算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号。

bool ParenthesisMatching(string Parenthesis)
{
  stack<char> rec;
  for (const auto e : Parenthesis)
  {
    if ((e == ')' || e == ']') && rec.empty())
      return false;
    if (!rec.empty() &&(
      (rec.top() == '(' && e == ')') ||
      (rec.top() == '[' && e == ']')))
    {
      rec.pop();
      continue;
    }
    if (!rec.empty() &&(
      (rec.top() == '(' && e == ']') ||
      (rec.top() == '[' && e == ')')))
      return false;
    rec.push(e);
  }
  if (!rec.empty()) return false;
  return true;
}

4.3 表达式求值-栈

表达式求值是程序设计语言编译中的一个最基本的问题，它的实现也需要运用栈。这里介绍的算法是由运算符优先级确定运算顺序的对表达式求值的算法–算符优先算法。

表达式的组成：操作数(operand)：常数、变量；运算符(operator)：算术运算符，关系运算符和逻辑运算符；界限符(delimiter)：左右括号和表达式结束符。

任何一个算术表达式都由操作数(常量、变量)、算术运算符(+,-,*,/)和界限符(括号、表达式结束符’#’，虚设的表达式起始符’#’)组成。后两者统称为算符。例如：# 3*(7-2)#

为了实现表达式的求值，需要设置两个栈：一个是运算符栈OPTR，用于寄存运算符，另一个称为操作数栈OPND，用于寄存运算数和运算结果。

求值的处理过程是从左到右扫描表达式的每一个字符，当扫描到的是运算数时，将其压入栈OPND。

当扫描到的是运算符时：

若这个运算符OPTR栈顶运算符的优先级高，则入栈OPTR，继续向后处理；

若这个运算符比OPTR栈顶运算符优先级低，则从OPND栈中弹出两个运算数，从栈OPTR中弹出栈顶运算符进行运算，并将运算结果压入栈OPND中。

继续处理当前字符，直到遇到结束符为止。

4.1 舞伴问题-队列

假设在舞会上，男士和女士各自排成一队。舞会开始时，依次从男队和女队的对头各出一人配成舞伴。如果两队的初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一个算法模拟上述舞伴配对问题。

该问题有典型的先进先出的特点，可以用队列作为算法的数据结构。

在这里插入图片描述 \qquad 首先构造两个队列；依次从将队头的元素出队配成舞伴；当某个队列为空，则另外一队等待的人即是下一轮舞曲第一个可以获得舞伴的人。

5、栈的表示和实现

栈的抽象数据类型表示如下所示：

由于栈的本质是线性表，所以栈也有顺序存储和链式存储两种实现方式，站的书序存储叫做顺序栈；栈的链式存储叫做链栈。

5.1 顺序栈的表示和实现

栈的存储方式：同一般线性表的顺序存储结构完全相同，利用一组地址连续的存储单元一次存放自栈底到栈顶的数据元素栈底一般在低地址端。附设top指针，知识栈顶元素在顺序栈中的位置，一般top指针指示的是真正栈顶元素之上的下标地址；附设base指针，指示栈底元素在顺序栈中的位置；用stackSize表示栈可以使用的最大容量。

当  top==base时，表示栈空；当op−base==stacksize时表示栈满。上溢出(OverFlow)： 栈已经满了，但是还要继续压入元素；下溢出(underFlow)： 栈已经空了，但是还要弹出元素。

顺序栈的表示：

#define MAXSIZE 100
class sqStack
{
  SElemType *base;    //栈底指针
  SElemType *top;     //栈顶指针
  int stackSize;      //栈可用最大容量
};

顺序栈的初始化：

sqStack()
{//构造函数
  try{
    base = new SElemType[MAXSIZE];//申请栈空间
  }
  catch(...)
  {
    cout << "栈空间分配失败"<<endl;
    exit(-1);
  }
  top = base;//空栈，栈顶指针等于栈底指针
  stackSize = MAXSIZE;
}

顺序栈的销毁：

~sqStack()
{
  if(base)
  {
    delete base;
    base = top = nullptr;
    stackSize = 0;
  }
}

判断顺序栈是否为空：

bool StackEmpty()
{
  if(top == base)
    return true;
  else return false;
}

求顺序栈的长度：

int StackLength(sqStack &S)
{
  return S.top-S.base;
}

清空顺序栈：

void ClearStack()
{
  if(base)
    top = base;
}

顺序栈的入栈：

void StackPush(SElemType &e)
{
  if(base && //栈不为null
  top-base < stackSize)//栈不满
  {
    *top = e;
    ++top;
    //*top++ = e;  //上面两句可以合为一句
  }
  else
  {
    cout<<"栈没申请空间或者栈满了"<<endl;
    exit(-1);
  }
}

顺序栈的出栈：

bool Pop(SqStack &S, SElemType &e)
{
  if(S.top==S.base)
  {
    cout << "栈已经空了！" <<endl;
    return false;
  }
  e = *--S.top();
  return true;
}