数据结构之栈与队列（一）

一.栈与队列的定义与特点

栈：栈（stack）又名堆栈，它是限定在表的一端进行插入和删除操作的线性表（后进先出）。这一端被称为栈顶，相对地，把另一端称为栈底。不含元素的空表称为空栈。
队列：和栈相反，队列（queue）是一种先进先出的线性表。它只允许在表的前端进行删除操作，而在表的后端进行插入操作。允许插入的一端称为队尾（rear），允许删除的一端称为队头（front）。
向一个栈插入新元素又称作入栈，从一个栈删除元素又称作出栈。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。和线性表一样，栈和队列的存储结构也包括顺序和链式两种。
原文链接：https://blog.csdn.net/qq_41117236/article/details/80764231

小结：栈与队列本质上都是线性表，只不过是操作受限。

二.栈与队列的应用

案例一：

进制之间的转换：我们往往会用辗转相除法，比如把十进制的161转换为八进制

案例二. 括号匹配：

我们在写代码的时候，往往会用到许多的括号嵌套使用，计算机则利用栈的特点进行匹配。

案例三.表达式值：

比如一个表达式（a+b）*c+e/f

计算机也是利用栈来进行计算，首先创建算符栈OPTR 操作数栈OPND

*扫描到数，压入栈OPND；

若扫描到运算符，则：

若运算符比OPTR栈顶运算符优先级高，则入栈OPTR（刚开始OPTR没有元素时，运算符直接入栈）
若运算符比OPTR栈顶运算符优先级低，则从OPND栈顶弹出两个数计算，并将计算结果压入栈OPND

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

三.循环队列

循环队列就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。

这里只讲循环队列的程序实现，至于其他的顺序栈，链栈等等，在我的前面关于顺序表，链表中都有介绍，且变化不大。

之所以有循环队列而无循环栈的原因是，队列是“先进先出”的，所以会使得空间得以循环利用。我们假设MAXQSIZE为队列的长度，Q.rear指向最后一个元素的下一个元素。Q.front指向起点元素。

首先创建一个队列

 #define MAXQSIZE 64 struct data{        char name[];        int age;}; struct  Com {         struct data  arr[MAXQSIZE];         int rear = 0;        int front = 0;          };int main{        struct Com member;        return 0;}

插入元素

        void insert( struct Com member , struct data ele  )        {        if((member.rear+1)%MAXQSIZE==member.front)                   return ;         else                        {                  * (member.arr[member.front])=ele;                  member.rear=(member.rear+1)%MAXQSIZE;                 }        }       // 由此可见，循环队列要掌握%的运算就不难了。

一.栈与队列的定义与特点

二.栈与队列的应用

三.循环队列

更多相关文章

随机推荐