数据结构学习---栈和队列

栈和队列的定义和特点

1、栈

• 栈和队列是限定插入和删除只能在表的“端点”进行的线性表
• 表尾称为栈顶（top），表底称为栈底（bottom）
• 不含有元素的空表称为空栈
• 与线性表不同，栈插入的只能插入在最后的位置，删除也只能删除最后的位置（后进先出）
• 一般用于解决下列的问题
  • 数制转换
  • 表达式求值
  • 括号匹配检验
  • 八皇后问题
  • 行编辑程序
  • 函数调用
  • 迷宫求解
  • 递归调用的实现等

一般线性表	栈
逻辑结构	一对一
存储结构	顺序表、链表	顺序表、链栈
运算规则	随机存取	后进先出（LIFO）

2、队列

• 队列是一种先进先出的线性表
• 插入的时候只能插入在队尾（rear），删除的时候只能在队头（front）删除（先进先出）
• 一般用于解决类似下列的问题
  • 脱机打印输出
  • 多用户系统中，用于用户排成队，分时地循环使用CPU和主存
  • 按用户的优先级排成多个队，每个优先级一个队列
  • 实时控制系统中，信号按接收的先后顺序依次处理
  • 网络电文传输，按到达时间先后顺序依次进行等
• 队列的特点

队列
存储方式	顺序队、链队
	先进先出
实现方式	入队和出队操作，具体实现依顺序队或链队的不同而不同

栈与队列的应用案例

• 1.进制的转换，如将十进制转换为八进制数
  • 将十进制数除以8，然后将余数分别入栈，最后在出栈，出栈的顺序就是最终转换为8进制的结果
• 2.括号匹配的检验，括号在实际使用的时候一定是成对出现的，现在可以使用过堆栈来检测使用的括号是否是成对出现的
  • 将左括号分别入栈，当检测到一个有括号的时候，就将栈顶的元素与之对应 出栈一个，如果存在不匹配的情况，那么入栈的和出栈之间就不能配对，这样就起到了检测括号是否成对的效果。
• 3.表达式求值，实际应用中，加减乘除与括号优先级不同，需要按照优先级进行计算，此时可以使用栈来解决优先级问题
  • 使用两个栈，一个存放运算符，另外一个存放运算数
  • 当扫描的是运算数的时候直接压入栈
  • 当时运算符的时候
    • 若这个运算符比运算符（OPTR）栈顶优先级高，则入栈继续向后处理
    • 若这个运算符比OPTR栈顶运算符优先级低，则从OPTR栈中弹出两个运算数，从栈OPTR中弹出栈顶运算符进行运算，并将运算结果压入存放运算数（OPND）的栈
  • 继续处理当前字符，直到遇到结束符为止
  • 实际上还能将标准的运算式转换为中缀表达式，仅需要使用一个栈即可完成运算
• 舞伴问题
  • 问题：假设在舞会上，男士和女士各自排成一队，舞会开始时，依次从男队和女队的队头各出一人配成舞伴，如果两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。
  • 思路：首先构造两个队列，依次将队头元素出队配成舞伴，某队为空，则另外一对等待着则是下一舞曲第一个可获得舞伴的人

栈的表示和操作的实现

• 栈的抽象数据类型定义(后面将会在顺序和链式结构中实现)

// 1、初始化堆栈
InitStack(&s)
// 2、销毁栈操作
DestroyStack(&S)
// 3、判定S是否为空栈
StackEmply(S)
// 4、求栈的长度
StackLength(S)
// 5、取栈顶元素
GetTop(S, &e)
// 6、栈置空操作
ClearStack(&S)
//  7、入栈操作
Push(&S, e)
// 出栈操作
Pop(&S, &e)

           

• 1、栈在顺序表中的实现（顺序栈）

  利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，栈底一般在低地址端

  • 附设top指针，指示栈底元素在顺序栈中的位置
  • 另设base指针，指示栈底元素在顺序栈中的位置

//顺序栈的存储结构
#define MAXSIZE 100
typedef struct
{
  SElemType *base;
  SElemType *top;
  int stacksize;
}SqStack;
           

• base 为栈底指针，初始化完成后，栈底指针base始终指向栈底的位置，若base的值为NULL，则表明栈结构不存在。top为栈顶指针，其初值指向栈底。每当插入新的栈顶元素时，指针top增1; 删除栈顶元素时，指针top减l。因此，栈空时，top和base的值相等，都指向栈底；栈非空时，top始终指向栈顶元素的上一个位置。
• stacksize指示栈可以使用的最大容量
• 两个指针相减，相当于获得两个元素之间差几个元素，也就是两个元素之间的元素个数。

//顺序栈的初始化
Status InitStack(SqStack &S)
{
  S.base = new SElemType[MAXSIZE];  //c++中，使用该方法删除的时候需要使用delete S；
  if(!S.base)
    exit(OVERFLOW);                 //存储空间分配失败
  S.top = S.base;
  S.stacksize = MAXSIZE;
  return OK;
  
}
           

//判断栈是否为空
Status StackEmpty(SqStack S)
{
  if(S.top == S.base)
    return TRUE;
  else
    return FALSE;
}
           

//求顺序栈的长度
int StackLength(SqStack S)
{
  return S.top-S.base;  //直接使用栈顶减去栈底就是栈的长度
}
           

//清空顺序栈，栈仍然保留，但是里面的元素为空，不用将所有的数据删除，
//直接将指针指向栈底即可，新数据入栈时自然会将就数据覆盖掉
Status ClearStack(SqStack &S)
{
  if(S.base)
    S.top = S.base;
  return OK;
}

           

//销毁一个栈，与清空不一样，空间全部需要释放了
Status DestroyStack(SqStack &S)
{
  if(S.base)
  {
    delete S.base;     //释放空间
    S.stacksize = 0;
    S.base = S.top = NULL;
  }
  return OK;
}

           

//顺序栈的入栈操作，在栈顶插入元素e
Status Push(SqStack &S, SElemType e)
{
  if(S.top-S.base == S.stacksize)    //判断栈是否满了
    return ERROR;                    //栈已满，上溢
  *S.top++ = e;                      //两步合成一步 *S.top = e; S.top++;存完后指针后一位
  return OK;
}

           

//出栈操作
Status Pop(SqStack &S,SElemType &e)
{
   //删除s的栈顶元素，用e返回删除的值
   if(S.top == S.base)
      return ERROR;
    e = *--S.top;      //栈顶指针是指向最上面元素在往后一个位置的，所以要先--才能访问到栈顶的值
    return OK;
}


           

//取出顺序栈的栈顶元素
SElemType GetTop(SqStack S)
{
  //返回栈顶元素，不修改栈顶指针
  if(S.top != S.base)      //栈非空
    return *(S.top - 1);   //返回栈顶元素的值，栈顶指针不变
}