一、栈

1、基本概念

栈（Stack）是只允许在表尾进行插入和删除操作的线性表。对栈来说，表尾端称为栈顶（top），表头端称为栈底（Bottom）。不含元素的空表称为空栈。栈的示意图如下：

栈的逻辑结构

栈的修改是按后进先出的原则进行的，因此栈又称为后进先出（Last In First Out, LIFO）的线性表。

栈有如下的基本操作：

操作 说明
init(&S) 初始化一个空栈
isEmpty(S) 判断一个栈是否为空，若为空返回true，否则返回false
push(&S, x) 进栈
pop(&S, &x) 出栈
getTop(S, &x) 读栈顶元素
destroy(&S) 销毁栈

2、存储结构

栈是一种操作受限的线性表，类似于线性表，它也有对应的两种存储方式。

（1）顺序栈

采用顺序存储的栈称为顺序栈。它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针指向当前栈顶元素的位置。用C语言可对顺序栈作如下定义：

1
2
3
4
5
6
7
#define MAXSIZE 50 // 定义栈中元素的最大个数

typedef struct
{
    ElemType data[MAXSIZE]; // 存放栈中元素
    int top; // 栈顶指针
}SqStack;

下面对栈的一些基本操作进行实现：

  • 初始化
1
2
3
4
void init(SqStack &S)
{
	S.top = -1; // 初始化栈顶指针
}

注：栈顶指针的初始值除了可以设置为 -1 外，还可以设置为 0，这相当于规定栈顶指针指向栈顶元素的下一个存储单元。

  • 判断栈是否为空
1
2
3
4
5
6
7
bool isEmpty(SqStack &S)
{
    if (S.top == -1) // 栈空
        return true;
    else // 非空
        return false;
}
  • 进栈
1
2
3
4
5
6
7
bool push(SqStack &S, ElemType x)
{
    if (S.top == MAXSIZE - 1) // 栈满，报错
        return false;
    S.data[++S.top] = x; // 指针先加1，再入栈
    return true;
}

注：如果初始化时 top 为 0，则进栈时应先入栈，再将 top 加1。

  • 出栈
1
2
3
4
5
6
7
bool pop(SqStack &S, ElemType &x)
{
    if (S.top == -1) // 栈空，报错
        return false;
    x = S.data[S.top--]; // 先出栈，指针再减1
    return true;
}

注：如果初始化时 top 为 0，则 top 需要先减1再进行出栈操作。

  • 读栈顶元素
1
2
3
4
5
6
7
bool getTop(SqStack S, ElemType &x)
{
    if (S.top == -1)
        return false;
    x = S.data[S.top];
    return true;
}

注：如果初始化时 top 为 0，则读取 top -1 位置的数据元素。

（2）链栈

采用链式存储的栈称为链栈，链栈的优点是便于多个栈共享存储空间和提高效率，且不存在栈满上溢的情况，通常采用单链表实现。用C语言可对链栈作如下定义：

1
2
3
4
5
typedef struct LinkNode
{
    ElemType data; // 存放栈中元素
    struct LinkNode *next; // 栈顶指针
}*LiStack;

链栈的操作于链表相似，这里不再赘述。

二、队列

1、基本概念

队列（Queue）是一种操作受限的线性表，只允许在表的一端进行插入，而在另一端进行删除。向队列中插入元素称为入队或进队，删除元素称为出队或离队。队列的示意图如下：

队列的逻辑结构

队列是一种先进先出（First In First Out, FIFO）的线性表。

下面给出队列的一些基本操作：

操作 说明
InitQueue 初始化队列
QueueEmpty 判断队列是否为空，若队列为空返回true，否则返回false
EnQueue 入队
DeQueue 出队
GetHead 读队头元素

2、存储结构

（1）顺序存储

队列的顺序存储是指分配一块连续的存储单元存放队列中的元素，并附设两个指针：队头指针 front 指向队头元素，队尾指针 rear 指向队尾元素的下一个位置（也可以指向队尾元素）。用C语言可对队列作如下定义：

1
2
3
4
5
6
7
#define MAXSIZE 50

typedef struct
{
    ElemType data[MAXSIZE]; //存放队列元素
    int front, rear; // 队头指针和队尾指针
}SqQueue;

为了在C语言中描述方便起见，在此约定：初始化创建空队列时，令 front = rear = 0，每当插入新的队列尾元素时，尾指针 rear 加 1；每当删除队列头元素时，头指针 front 加 1。因此，在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置，如下图所示。

队列的顺序存储

假设当前队列分配的最大空间为 6，则当队列处于上图 (d) 所示的状态时不可再继续插入新的队尾元素，否则会出现溢出现象，即因数组越界而导致程序的非法操作错误。事实上，此时队列的实际可用空间并未占满，所以这种现象称为“假溢出”。这是由“队尾人队，队头出队”这种受限制的操作造成的。怎样解决这种“假溢出”问题呢? 一个较巧妙的办法是将顺序队列变为一个环状的空间，如下图所示，称之为循环队列。

循环队列

头、尾指针以及队列元素之间的关系不变，只是在循环队列中，头、尾指针“依环状增 1” 的操作可用“模”运算来实现。通过取模，头指针和尾指针就可以在顺序表空间内以头尾衔接的方式“循环”移动。

循环队列的存储结构

  • 初始时：Q.front = Q.rear = 0
  • 入队：Q.rear = (Q.rear + 1) % MAXSIZE
  • 出队：Q.front = (Q.front + 1) % MAXSIZE
  • 队列长度：(Q.rear + MAXSIZE - Q.front) % MAXSIZE

由上图可知，队空和队满时都有 Qfront == Q.rear，那么该如何判断队列是否为空呢？下面介绍几种常见的解决方法：

  • 牺牲一个单元来区分队空和队满，入队时少用一个队列单元，以队头指针在队尾指针的下一位置作为队满的标志，如上图 (d) 所示。
  • 类型中增设表示元素个数的数据成员。
  • 类型中增设 tag 数据成员，以区分是队满还是队空。

下面对队列的一些基本操作进行实现：

  • 初始化
1
2
3
4
void InitQueue(SqQueue &Q)
{
    Q.rear = Q.front = 0; // 初始化队首、队尾指针
}
  • 判断队列是否为空
1
2
3
4
bool isEmpty(SqQueue Q)
{
    return Q.rear == Q.front; // 队空条件
}
  • 入队
1
2
3
4
5
6
7
8
bool EnQueue(SqQueue &Q, ElemType x)
{
    if ((Q.rear + 1) % MAXSIZE == Q.front) // 队满则报错
        return false;
    Q.data[Q.rear] = x;
    Q.rear = (Q.rear + 1) % MAXSIZE; // 队尾指针加 1 取模
    return true;
}
  • 出队
1
2
3
4
5
6
7
8
bool DeQueue(SqQueue &Q, ElemType &x)
{
    if (Q.rear == Q.front) // 队空则报错
        return false;
    x = Q.data[Q.front];
    Q.front = (Q.front + 1) % MAXSIZE; // 队头指针加 1 取模
    return true;
}
（2）链式存储

队列的链式表示称为链队列，它实际上是一个同时带有队头指针和队尾指针的单链表。头指针指向队头结点，尾指针指向队尾结点，即单链表的最后一个结点。用C语言可对链队作如下定义：

1
2
3
4
5
6
7
8
9
10
typedef struct
{
    ElemType data;
    struct LinkNode *next;
}LinkNode; // 链式存储结点

typedef struct
{
    LinkNode *front, *rear; // 队列的队头和队尾
}LinkQueue; // 链式队列

链式队列的基本操作本质上与顺序队列相同，只是具体实现不同，这里不再进行赘述。