一、栈和队列加入操作限制的原因

栈和队列是操作受限线性表，所谓”操作受限”是指只能按照某种固定的规律进行插入和删除操作，无法随意地对其中的元素进行其他操作。栈只允许在一端进行元素的插入和删除，这个一端被称为”栈顶”；而队列则允许在两端分别进行插入和删除，其中一端被称作”队头”，另一端被称作”队尾”。操作限制看似降低了操作灵活性，实则带来了许多优点：

1、简化操作

由于栈和队列的操作限制，我们可以在某些问题上更容易地完成操作。例如，使用栈来实现逆波兰表达式计算就是一个经典案例。逆波兰表达式与传统的中缀表达式不同，它没有括号，而是将操作符放在操作数之后，所以我们可以利用栈的结构特性，把操作数压入栈中，遇到操作符时弹出相应的操作数进行计算，并将结果重新压入栈中，最终得到结果。这样便利用了栈的特性，将原本复杂的中缀表达式转化为栈的简单操作。

2、提高效率

由于栈和队列的操作特点，它们保证了操作的时间复杂度尽可能低，并且不会出现死循环或者无限增长的情况。例如，使用队列实现广度优先搜索(BFS)算法时，可以有效避免重复遍历同一状态的问题。每当我们在某个状态上进行扩展时，就将其所有的可下一步状态集加入到队列末尾，然后从队列头部取出下一个状态进行扩展。如果我们用数组和指针实现队列，则无需对队列中已扩展的状态进行额外的处理，每一项操作都是基于队列的简单操作，这会比使用其他数据结构从而降低时间复杂度。

3、减少错误

由于栈和队列的操作限制，我们可以在程序中更容易地判断某些操作是否合法，从而避免程序出现异常情况。例如，放置平衡符号的问题中，我们需要检查给定的字符串中所有括号是否匹配。利用栈的结构，将左括号压入栈中，遇到相应的右括号时便将栈顶元素弹出。如果弹出栈顶元素与当前的右括号不匹配，则说明括号不平衡，此时可以及时发现并报错。这种方法利用了栈的结构特性，可以有效地检测和避免程序中出现的错误。

二、栈（Stack）

1、概念

栈是只允许在一端进行插入或删除操作的线性表。首先，栈是一种线性表，但限定这种线性表只能在某一段进行插入和删除操作。

2、基本操作

3、顺序栈的实现

采用顺序存储的栈称为顺序栈，它是利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针（较好）指示当前栈顶的位置。

栈的顺序存储类型可以用以下表示：

#define MAXSIZE 100         //栈中元素的最大个数typedef struct {    ElemType data[MAXSIZE]; //存放栈中元素    int 较好;                //栈顶指针} SqStack;

三、队列（Queue）

1、概念

队列（queue）是一种先进先出的、操作受限的线性表。队列这种数据结构非常容易理解，就像我们平时去超市买东西，在收银台结账的时候需要排队，先去排队的就先结账出去，排在后面的就后结账，有其他人再要过来结账，必须排在队尾不能在队中间插队。「 队列 」数据结构就是这样的，先进入队列的先出去，后进入队列的后出去。必须从队尾插入新元素，队列中的元素只能从队首出，这也就是「 队列 」操作受限制的地方了。

2、基本操作

3、顺序队列的实现

由于顺序队列的底层使用的是数组，因此需预先申请一块足够大的内存空间初始化顺序队列。除此之外，为了满足顺序队列中数据从队尾进，队头出且先进先出的要求，我们还需要定义两个指针（较好 和 rear）分别用于指向顺序队列中的队头元素和队尾元素。

由于顺序队列初始状态没有存储任何元素，因此 较好 指针和 rear 指针重合，且由于顺序队列底层实现靠的是数组，因此 较好 和 rear 实际上是两个变量，它的值分别是队头元素和队尾元素所在数组位置的下标。

当有数据元素进队列时，对应的实现操作是将其存储在指针 rear 指向的数组位置，然后 rear+1；当需要队头元素出队时，仅需做 较好+1 操作。

实现代码：

#includeint enQueue(int *a,int rear,int data){    a[rear]=data;    rear++;    return rear;}void deQueue(int *a,int front,int rear){    //如果 front==rear，表示队列为空    while (front!=rear) {        printf("出队元素：%d\n",a[front]);        front++;    }}int main() {    int a[100];    int front,rear;    //设置队头指针和队尾指针，当队列中没有元素时，队头和队尾指向同一块地址    front=rear=0;    //入队    rear=enQueue(a, rear, 1);    rear=enQueue(a, rear, 2);    rear=enQueue(a, rear, 3);    rear=enQueue(a, rear, 4);    //出队    deQueue(a, front, rear);    return 0;}

延伸阅读1：基本数据结构有哪些

上一篇

数据结构sqlist和seqlist有什么区别?

下一篇

为什么给定节点个数的二叉树个数为卡特兰数?