七、栈和队列

简介: 七、栈和队列

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。

88c4d2c9a1c24afaa7a0da5a443083c5.png

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


9cdca237f38a4fc3a707f6b3d8c1bdce.png


栈总结:

59c9de0e75b64394a59a45e14c7a1312.png




3、队列-queue


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

7855a35f1db345359bc179c23e2552c2.png


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


f28d2ab27c384ea39c2147a53d027245.png



4、栈和队列的案例


4.1 进制转换-栈

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


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



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


8d74167fd49c437db7aeb7a098673885.png

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 检验括号是否匹配-栈


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


3fab0c8323b546609eedd2eb9662c8cb.png


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


(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 舞伴问题-队列


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


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

a97f6336fc2d45e2a709d7867377f157.png


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



5、栈的表示和实现



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

f9dbec8e220243be97d244acd7585ac6.png


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


5.1 顺序栈的表示和实现


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

906929cc28d146a5af67042881145f4c.png

当  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;
}
相关文章
|
4天前
|
DataX
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
|
1月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
142 77
|
1月前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
38 7
|
1月前
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
44 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
1月前
|
存储 C语言 C++
【C++数据结构——栈与队列】链栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现链栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储整数,最大
46 9
|
3月前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
99 5
|
3月前
|
算法
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能,支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构,并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示,系统在处理小规模购物车时表现良好,但在大规模购物车操作下可能存在性能瓶颈。
72 0
|
3月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
55 1
|
3月前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
116 21
|
3月前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。

热门文章

最新文章