楚河汉界

你只可至此，不可再逾越 | Designed by Mr.wisdom

栈与队列

发表于 分类于
本文字数： 2.4k 阅读时长 ≈ 2 分钟

栈

前言

栈是只允许在一段进行插入和删除操作的特殊的线性表。上课时老师把栈类比为弹匣，子弹被压进弹匣，不能从另一端出来，所以后面放进来的反而能先出，正所谓”后来居上”。

栈的基本操作大同小异，基本如下：

1.初始化一个空栈

2.判断栈是否为空

3.将一个元素入栈：记得检查是否栈满,链栈不必检查

4.将一个元素出栈：记得检查是否栈空

5.返回栈顶的值

6.销毁栈，释放空间

顺序栈

顺序栈顾名思义，就是用顺序结构实现的栈，其主要特点和顺序表一致，需要划一片连续的存储空间来进行存储，基本上通过数组实现。

栈的顺序存储类型可描述为：

1
2
3
4
5
typedef struct 
{ 
  int data[MaxSize]; // 创建栈的空间，用数组表示
  int top; // 用于表示栈顶元素的在数组中的位置
}SqStack;

top可以设置为-1也可以设置为0，这个每个题目不同视情况而定。

但顺序栈的缺点和顺序表一样，空间大小是固定死的，不能随机应变，而且还要连续的存储空间，有时候不易实现。

顺序栈中为了更加有效利用存储空间，提出共享栈，让两个顺序栈共享一个一维数组空间，两个栈的空间相互调节，通过两个栈顶指针相减为1判断栈满，减少存储空间，降低发生上溢的可能。

链栈

链栈也很明显，采用了链式存储结构，优点在于便于多个栈共享存储空间和提高其效率，并且不会存在栈满上溢的情况。所有的操作都是在单链表的表头进行。

队列的基本操作如下：

1.初始化队列

2.判断队列是否为空

3.入队，要检查队列是否满了

4.出队，要检查队列是否为空

5.读队头元素。

队列

前言

队列和栈一样，也是受到限制的线性表，他只能在一端输出一端输入，和我们平时的排队很像，不允许插队，也不能中途离队，只能从队尾开始排，从队头出。

顺序队列

顺序队列还是一样还是顺序结构，分配一块连续的存储空间存放队列的元素，并附设两个指针：队头指针和队尾指针。

队列的顺序存储类型可描述为：

1
2
3
4
5
#define MaxSize 10
typedef struct { 
    int data[MaxSize];// 用于存放队列元素
    int front, rear;// 用于存放队头和队尾指针，分别指向队头元素在队列数组中的位置和队尾元素的下一个位置
}SqQueue;

队尾指针指向的位置也是可以变动的，视情况而定。

但是顺序队列有他的局限性，那就是判断队列是否满了不好判断，举个例子：

先将队列填满，那么rear队尾指针就已经到了maxsize-1，但是这时队头出去一个，那么这个队列就空出了一个，那么这个队列就没有满，但是rear的指针是不变的，所以并不能通过rear指针的位置判断队列是否满。

循环队列

刚才说了顺序队列的缺陷，现在顺势引出循环队列，循环队列可以将其看作是一个环状的图形，将存储队列的元素从逻辑上看作是一个环，称为循环队列。但是当rear指针指到maxsize-1时，下一个就要到位置为0的地方，所以得到的结果应该通过取余数的方式实现 **%**。

那么循环队列判断队空和队满的条件是什么？显然队空的条件是Q.front==Q.rear。若入队元素的速度快于出队元素的速度，那队尾指针很快就会赶上队首指针，到时候队满的条件也成了 Q.front==Q.rear。以下有三种方法解决：

1.空出一个单元不存储数据，这样的话入队就少了一个队列单元，这种做法比较普遍。那么队头指针在队尾指针的下一个位置是队满的标志。

队满条件：(Q.rear+1)%MaxSize==Q.front.

队空条件：Q.front==Q.rear.

队列中元素的个数：(Q.rear-Q.front+MaxSize)%MaxSize.

2.类型增设表示元素个数的数据成员size。

队满条件：Q.size=MaxSize。

队空条件：Q.Size=0.

3.类型中设置tag数据成员，以区分队空还是队满。tag=0时，就表示上一个操作为删除，如果Q.front==Q.rear，那就是队空；tag=1时，表示上一个操作为插入，如果Q.front==Q.rear，就表示队满。

链式队列

链式存储

队列的链式表示被称为链队列，它是一个同时带有队头指针和队尾指针的单链表。头指针指向队头结点，尾指针指向队尾结点，及单链表最后一个结点。但是要注意头指针和头结点是不一样的，一个指向的是逻辑结构上的队头，一个指向链表的表头。以下是队列的链式存储类型：

1
2
3
4
5
6
7
8
9
10
11
// 定义链式队列的结点
typedef struct {
    int data;
    struct LinkNode *next;
}LinkNode;
// 定义链式队列
typedef struct {
    LinkNode *front, *rear;// 链式队列中包含指向队头和队尾的指针，由于队列是队头进队尾出，因此需要标记队尾指针
    int length;// 用于记录队列的长度
}LinkQueue;

   值得注意的是，不带头结点的链式队列在操作上往往比较麻烦，因此通常将链式队列设计成一个带头结点的单链表，这样操作和删除操作就统一了。

    用单链表表示的链式队列特别适合数据元素变动比较大的情形，而且不存在队列满且溢出的问题。另外，如果程序中要使用多个队列，与多个栈的情形一样，最好使用链式队列，这样不会出现存储分配不合理和“溢出”的问题。所以之前提到的循环队列用在链式队列中纯属画蛇添足。

双端队列

栈和队列的应用

栈的应用

例题

1.

相关文章
钟永龙打钱！