数据结构 | C 与 C++ 描述 | 三、栈和队列



栈(Stack)是只允许在一端进行插入或删除操作的线性表

  • 栈只能在栈顶进行插入和删除操作,进栈次序依次为 a1, a2, a3, a4,而出栈次序则依次为 a4, a3, a2, a1。(Last In First Out, LIFO)
  • n 个不同元素进栈,则出栈元素不同排列的个数为 1/(n+1) 乘 C的2n到n

基本操作

  • InitStack(&S):初始化
  • StackEmpty(S):判断栈是否为空
  • Push(&S, x):进栈,栈未满则插入 x 成为新栈顶
  • Pop(&S, &x):出栈,栈非空则弹出栈顶元素,用 x 返回
  • GetTop(S, &x):读栈顶元素,栈非空则用 x 返回栈顶元素
  • DestroyStack(&S):销毁栈,并释放栈 S 占用的空间

逻辑结构 - 线性

存储结构

栈是一种操作受限的线性表,有两种存储方式

顺序栈

利用一组地址连续的存储单元存放自栈底到栈顶的数据元素,同时附设一个指针(top)指向栈顶元素的地址。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#define MaxSize 50

// 定义
typedef struct{
ElemType data[MaxSize];
int top;
}SqStack;

// 初始化
bool InitStack(SqStack &S) {
S.top = -1; // 一般令 top 指针为 -1,这样指针总指在当前值;为 0 则是指针指向下一个待定栈顶(还没数据)
return true;
}

// 判空
bool StackEmpty(SqStack S) {
if(S.top == -1)
return true;
else
return false;
}

// 进栈
bool Push(SqStack &S, Elemtype x) {
if(S.top == MaxSize - 1) // 栈满报错
return false;
S.data[++S.top] = x; // 从 -1 开始,需先将指针前移一位,再传入值
return true;
}

// 出栈
bool Pop(SqStack &S, Elemtype &x) {
if(S.top == -1)
return false;
x = S.data[S.top--];
return true;
}

// 读栈顶元素
bool GetTop(SqStack S, Elemtype &x) {
if(S.top == -1)
return false;
x = S.data[S.top]; // 这里如果 top 从 0 开始,就需要指针往后移一位
return true;
}

// 销毁栈
bool DestroyStack(SqStack &S) {
S.top == -1;
return true;
}

链栈

采用链式存储的栈。入栈、出栈的操作都在表头进行。

  • 链栈的优点是便于多个栈共享存储空间和提高其效率,且不存在栈满上溢的情况。
  • 通常链栈不定义头结点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// 定义
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode, *LinkStack;

// 初始化
bool InitStack(LinkStack &S) {
S = NULL;
return true;
}

// 判空
bool Empty(LinkStack S) {
return (S == NULL);
}

// 进栈
bool Push(LinkStack &S, Elemtype x) {
LNode *q = (LNode*)malloc(sizeof(LNode));
q->next = S;
q->data = x;
S = q;
return true;
}

// 出栈
bool Pop(LinkStack &S, Elemtype &x) {
if(S == NULL)
return false;
LNode *q = S; // 建立一个中间指针指向头元素,后续释放头元素空间
x = q->data;
S = S->next;
free(q);
return true;
}

// 读栈顶元素
bool GetTop(SqStack S, Elemtype &x) {
if(S == NULL)
return false;
x = S->data;
return true;
}

队列

队列(Queue),一种操作受限的线性表,只允许在表的一端进行插入,而在表的另一端进行删除。

  • 通常队列都是头部进行删除操作,尾部进行插入操作,因此最早入队的也是最早出队的(First In First Out, FIFO)

基本操作

  • InitQueue(&Q):初始化
  • QueueEmpty(Q):判队列空
  • EnQueue(&Q, x):入队,队列未满则插入 x 作为新队尾
  • DeQueue(&Q, &x):出队,队列非空则删除对头元素,用 x 返回
  • GetHead(Q, &x):读队头元素,若队列非空,用 x 返回队头元素

逻辑结构 - 线性

存储结构

顺序存储

队列的顺序存储是分配一块连续的存储单元存放队列中的元素,并附设两个指针,front 指针指向队头的位置,rear 指针指向队尾元素的下一个位置(也就是待插入元素的空位置)

传统顺序存储实现的顺序链表,在判断队满/对空的时候会存在问题,当指针 Q.front = Q.rear = 0,可以作为判空的条件,而 Q.rear = MaxSize 则不一定为满,有可能为空(刚插满又删完,两指针都移动到刚好超出 MaxSize 的位置,此时为“假溢出”)。因此使用循环队列的概念。

循环队列

循环链表,即把存储队列元素的表从逻辑上视为一个环,当队首指针 Q.front = MaxSize - 1(即连续空间中最后一个位置),再往前进一个位置就又从 0 开始,利用取余运算实现:Q.front = (Q.front + 1) % MaxSize,同时新元素入队 rear 指针也会按顺时针方向向前进一。

  • 循环链表的队空为 Q.front == Q.rear,但等到队满后头尾指针也会相遇,因此使用三种方法用以区分:
    1. 牺牲一个单元来区分队空和队满,入队时少用一个队列单元,约定队头指针在队尾指针的下一位只作为队满的标志:(Q.rear + 1) % MaxSize == Q.front ,而队空条件依旧为两指针相同,此时队列中的元素个数为 (Q.rear - Q.front + MaxSize) % MaxSize
    2. 类型中增设表示元素个数的数据成员,队空的条件为:Q.size == 0,队满的条件为:Q.size == MaxSize
    3. 类型中增设 tag 数据成员,用以标记上一步操作是入队还是出队,判断队空的条件就为:Q.front == Q.rear && Q.tag == 0,队满的条件是:Q.front == Q.rear && Q.tag == 1

牺牲一个单元

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#define MaxSize 50

// 定义
typedef struct{
ElemType data[MaxSize];
int front, rear;
}SqQueue;

// 初始化
bool InitQueue(SqQueue &Q) {
Q.front = Q.rear = 0;
return true;
}

// 判空
bool QueueEmpty(SqQueue Q) {
if(Q.front == Q.rear)
return true;
else
return false;
}

// 入队 - 判断队满
bool EnQueue(SqQueue &Q, ElemType x) {
if((Q.rear + 1) % MaxSize == Q.front) // rear 再往后移一位是 front,就不添加元素了,rear 当前指的这个空单元就被废弃了
return false;
Q.data[Q.rear] = x;
Q.rear = (Q.rear + 1) % MaxSize; // rear 加 1 取余,往前移一位
return true;
}

// 出队 - 判断队空
bool DeQueue(SqQueue &Q, ElemType &x) {
if(Q.front == Q.rear)
return false;
x = Q.data[Q.front];
Q.front = (Q.front + 1) % MaxSize; // front 加 1 取余,往前移一位
return true;
}

// 读队头元素 - 判断队空
bool GetHead(SqQueue Q, ElemType &x) {
if(Q.front == Q.rear)
return false;
x = Q.data[Q.front];
return true;
}

增设 size

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#define MaxSize 50

// 定义
typedef struct{
ElemType data[MaxSize];
int front, rear, size;
}SqQueue;

// 初始化
bool InitQueue(SqQueue &Q) {
Q.front = Q.rear = 0;
Q.size = 0;
return true;
}

// 判空
bool QueueEmpty(SqQueue Q) {
if(Q.size == 0)
return true;
else
return false;
}

// 入队
bool EnQueue(SqQueue &Q, ElemType x) {
if(Q.size == MaxSize)
return false;
Q.data[Q.rear] = x;
Q.rear = (Q.rear + 1) % MaxSize;
Q.size++;
return true;
}

// 出队
bool DeQueue(SqQueue &Q, ElemType &x){
if(Q.size == 0)
return false;
x = Q.data[Q.front];
Q.front = (Q.front + 1) % MaxSize;
Q.size--;
return true;
}

增设 tag

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#define MaxSize 50

// 定义
typedef struct{
ElemType data[MaxSize];
int front, rear, tag;
}SqQueue;

// 初始化
bool InitQueue(SqQueue &Q) {
Q.front = Q.rear = 0;
Q.tag = 0;
return true;
}

// 判空
bool QueueEmpty(SqQueue Q) {
if(Q.front == Q.rear && Q.tag == 0)
return true;
else
return false;
}

// 入队
bool EnQueue(SqQueue &Q, ElemType x) {
if(Q.front == Q.rear && Q.tag = 1)
return false;
Q.data[Q.rear] = x;
Q.rear = (Q.rear + 1) % MaxSize;
Q.tag = 1; // 有新元素入队,改变 tag 的状态为 1
return true;
}

// 出队
bool DeQueue(SqQueue &Q, ElemType &x){
if(Q.front == Q.rear && Q.tag = 0)
return false;
x = Q.data[Q.front];
Q.front = (Q.front + 1) % MaxSize;
Q.tag = 0; // 有元素出队,改变 tag 的状态为 0
return true;
}

链队列

采用链式存储的队列。同时带有队头指针和队尾指针的单链表,front 指向队头结点(一般为头结点),rear 指向队尾结点;用头指针进行删除操作,尾指针进行插入操作。

  • 用单链表表示的链式队列特别适用于数据元素变动比较大的情形,且不存在队列满、产生溢出的问题;
  • 使用多个队列时,最好使用链队,存储分配会更合理,也不会存在溢出问题;
  • 通常链队会定义头结点,这样插入、删除操作会统一。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
// 定义
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode;

typedef struct{
LNode *front, *rear;
}LinkQueue;

// 初始化
bool InitQueue(LinkQueue &Q) {
Q.front = Q.rear = (LNode*)malloc(sizeof(LNode));
Q.front->next = NULL; // Q.front 指向头结点,进行插入操作
return true;
}

// 判空
bool QueueEmpty(SqQueue Q) {
if(Q.front == Q.rear)
return true;
else
return false;
}

// 入队
bool EnQueue(LinkQueue &Q, ElemType x) {
LNode *s = (LNode*)malloc(sizeof(LNode));
s->data = x; s->next = NULL;
Q.rear->next = s;
Q.rear = s;
return true;
}

// 出队
bool DeQueue(LinkQueue &Q, ElemType &x) {
if(Q.front == Q.rear)
return false;
LNode *s = Q.front->next;
x = s->data; // 将待删元素返回
Q.front->next = s->next;
if(Q.rear = s) // 当只有一个元素,此时 rear 指针需要回到头结点,不然就被释放掉了
Q.rear = Q.front;
free(s);
return true;
}

// 读队头元素
bool GetHead(SqQueue Q, ElemType &x) {
if(Q.front == Q.rear)
return false;
x = Q.front->next->data;
return true;
}

双端队列

允许两端都可以进行入队和出队操作的队列。由此可以推广出输出受限的双端队列,即一端允许插入、删除,另一端只允许插入;与输入受限的双端队列,即一端允许插入、删除,另一端只允许删除。同栈一样,一般会考察输入输出次序的问题