Warning: Undefined array key "HTTP_ACCEPT_LANGUAGE" in /www/wwwroot/blog/wp-content/plugins/UEditor-KityFormula-for-wordpress/main.php on line 13
【数据结构】栈/队列的两种实现方式(顺序栈、链栈、顺序队列、链队列)(C语言) – Machine World

【背景】

        栈(stack)又名堆栈,它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。

        队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。

【源码运行环境】

操作系统:MAC OS X 10.13.4

编译环境:CLion (C++ 14) cmake

【源码实现】

S_Q.h源码部分:

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
//
// Created by WellLee on 2018/10/29.
//
 
#ifndef STACK_Queue_S_Q_H
#define STACK_Queue_S_Q_H
#include "stdio.h"
#include "stdlib.h"
#include "memory.h"
/*
 * 说明:define 定义一些常用的符号特性
 * 作用:增加代码可读性
 * Author: WellLee
 * Last Modified: 2018年10月31日23:16:07
 */
#define TRUE 1
#define FALSE 0
#define OVERFLOW -1
#define MAXSIZE 20
typedef int Status;
typedef int Elem;
/*
 * 结构:顺序栈
 * 作用:定义了顺序栈的一些结构特性,封装了常用的线性表操作
 * Author: WellLee
 * Last modified: 2018年10月31日23:17:31
 */
typedef struct Stack{
    Elem data[MAXSIZE];
    int top;
}Stack;
Status InitStack(Stack *S);
Status pop(Stack *S, Elem *e);
Status push(Stack *S, Elem e);
Status EmptyStack(Stack S);
Status ClearStack(Stack *S);
Status StackLength(Stack *S, int *length);
Status DestroyStack(Stack *S);
void showStackElements(Stack S);
 
/*
 * 结构:链栈
 * 作用:定义了链栈的一些结构特性,封装了常用的线性表操作
 * Author: WellLee
 * Last modified: 2018年10月31日23:17:31
 */
typedef struct Stacknode{
    Elem elem;
    struct Stacknode *next;
}stacknode,*StackNode;
typedef struct LinkStack{
    StackNode top;
    int length;
}*LStack;
Status InitLinkStack(LStack *LS);
Status LS_push(LStack *LS, Elem e);
Status LS_pop(LStack *LS, Elem *e);
Status LS_Clear(LStack *LS);
Status LS_Destroy(LStack *LS);
Status LS_Empty(LStack LS);
void LS_show(LStack LS);
 
 
/*
 * 结构:顺序队列
 * 作用:定义了顺序队列的一些结构特性,封装了常用的线性表操作
 * Author: WellLee
 * Last modified: 2018年10月31日23:17:31
 */
typedef struct SequenceQueue{
    Elem data[MAXSIZE];
    int front;
    int rear;
}SqQueue;
Status InitSqQueue(SqQueue *Q);
Status EnSqQueue(SqQueue *Q, Elem e);
Status DeSqQueue(SqQueue *Q, Elem *e);
Status ClearSqQueue(SqQueue *Q);
Status DestroySqQueue(SqQueue *Q);
Status QueueLength(SqQueue Q, int *length);
void showQueueElements(SqQueue Q);
 
 
/*
 * 结构:链队列
 * 作用:定义了链队列的一些结构特性,封装了常用的线性表操作
 * Author: WellLee
 * Last modified: 2018年10月31日23:17:31
 */
typedef struct QueueNode{
    Elem data;
    struct QueueNode *next;
}QNode,*QNodeptr;
typedef struct LinkQueue{
    QNodeptr rear;
    QNodeptr front;
}LinkQueue;
Status InitLkQueue(LinkQueue *Q);
Status EnLkQueue(LinkQueue *Q, Elem e);
Status DeLkQueue(LinkQueue *Q, Elem *e);
Status ClearLkQueue(LinkQueue *Q);
Status DestroyLkQueue(LinkQueue *Q);
Status LkQueueLength(LinkQueue Q, int *length);
void showLkQueue(LinkQueue Q);
 
 
#endif //STACK_Queue_S_Q_H

Stack.c源码部分:

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
//
// Created by WellLee on 2018/10/29.
//
#include "S_Q.h"
#include "time.h"
/*
 * 方法名:InitStack
 * 作用:初始化顺序栈
 * Author: WellLee
 * Last Modified:2018年10月31日23:21:09
 */
Status InitStack(Stack *S)
{
    S->top = -1;
    int StackLength = 0;
    Elem elem;
    srand(time(0));
    printf("请输入栈的元素个数");
    scanf("%d", &StackLength);
    for (int i = 0; i < StackLength; i++) {
        elem = rand() % 100 - 1;
        push(&*S, elem);
    }
    return TRUE;
}
/*
 * 方法名:push
 * 作用:顺序栈压栈操作
 * Author: WellLee
 * Last Modified:2018年10月31日23:21:09
 */
Status push(Stack *S, Elem e)
{
    if(S->top >= MAXSIZE)
    {
        printf("栈满\n");
        return OVERFLOW;
    }
    S->data[++S->top] = e;
    return TRUE;
}
/*
 * 方法名:StackEmpty
 * 作用:判断顺序栈是否为空
 * Author: WellLee
 * Last Modified:2018年10月31日23:21:09
 */
Status StackEmpty(Stack S)
{
    if(S.top == -1)
    {
        return TRUE;
    }
    return FALSE;
}
/*
 * 方法名:pop
 * 作用:顺序栈出栈操作
 * Author: WellLee
 * Last Modified:2018年10月31日23:21:09
 */
Status pop(Stack *S, Elem *e)
{
    if(StackEmpty(*S))
    {
        printf("栈空\n");
        return FALSE;
    }
    int top = S->top;
    *e = S->data[S->top--];
    S->data[top] = 0;
    return TRUE;
}
/*
 * 方法名:showStackElements
 * 作用:显示顺序栈元素
 * Author: WellLee
 * Last Modified:2018年10月31日23:21:09
 */
void showStackElements(Stack S)
{
    if(StackEmpty(S))
    {
        printf("栈空\n");
        return;
    }
    printf("栈元素如下:");
    printf("栈顶指向 -> %d \n",S.top);
    for(int i = 0; i <= S.top; i++){
        printf("%d ",S.data[i]);
    }
    printf("\n");
}
/*
 * 方法名:DestroyStack
 * 作用:销毁顺序栈
 * Author: WellLee
 * Last Modified:2018年10月31日23:21:09
 */
Status DestroyStack(Stack *S)
{
    free(S);
    return TRUE;
}
/*
 * 方法名:ClearStack
 * 作用:清空顺序栈
 * Author: WellLee
 * Last Modified:2018年10月31日23:21:09
 */
Status ClearStack(Stack *S)
{
    memset(S->data,0, sizeof(S->data));
    S->top = -1;
    return TRUE;
}
/*
 * 方法名:StackLength
 * 作用:获取顺序栈长度
 * Author: WellLee
 * Last Modified:2018年10月31日23:21:09
 */
Status StackLength(Stack *S, int *length)
{
    *length = S->top + 1;
    return TRUE;
}
 
 
 
 
 
 
 
/*
 * 方法名:InitLinkStack
 * 作用:初始化链栈
 * Author: WellLee
 * Last Modified:2018年10月31日23:21:09
 */
Status InitLinkStack(LStack *LS)
{
    srand(time(0));
    StackNode head = (StackNode)malloc(sizeof(stacknode));
    if(!head)
    {
        printf("内存不足\n");
        return OVERFLOW;
    }
    head->next = NULL;
    *LS = (LStack)malloc(sizeof(LStack));
    if(!*LS)
    {
        printf("内存不足\n");
        return OVERFLOW;
    }
    LStack ls = *LS;
    ls->top= head;
    ls->length = 0;
    printf("请输入栈的元素个数:");
    int length;
    scanf("%d", &length);
    for(int i = 0; i < length; i++)
    {
        Elem e = rand()%100 -1;
        LS_push(&ls, e);
    }
    printf("初始化成功\n");
    return TRUE;
 
}
/*
 * 方法名:LS_push
 * 作用:链栈压栈操作
 * Author: WellLee
 * Last Modified:2018年10月31日23:21:09
 */
Status LS_push(LStack *LS, Elem e)
{
    LStack ls = *LS;
    if(!ls)
    {
        printf("线性表参数有误\n");
        return OVERFLOW;
    }
    StackNode head = ls->top;
    StackNode elem = (StackNode)malloc(sizeof(stacknode));
    if(!elem)
    {
        printf("内存不足\n");
        return OVERFLOW;
    }
    elem->elem = e;
    elem->next = ls->top->next;
    head->next = elem;
    ls->length++;
    printf("%d 入栈\n", e);
    return TRUE;
}
/*
 * 方法名:LS_pop
 * 作用:链栈出栈操作
 * Author: WellLee
 * Last Modified:2018年10月31日23:21:09
 */
Status LS_pop(LStack *LS, Elem *e)
{
    if(LS_Empty(*LS))
    {
        printf("空栈,无元素出栈\n");
        return OVERFLOW;
    }
    LStack ls = *LS;
    StackNode node = ls->top;
    StackNode freenode = node->next;
    *e = freenode->elem;
    node->next = freenode->next;
    free(freenode);
    ls->length--;
    printf("%d 出栈\n", *e);
    return TRUE;
}
/*
 * 方法名:LS_Clear
 * 作用:清空链栈
 * Author: WellLee
 * Last Modified:2018年10月31日23:21:09
 */
Status LS_Clear(LStack *LS)
{
    LStack ls = *LS;
    if(!ls){
        printf("栈参数有误\n");
        return FALSE;
    }
    while(ls->length != 0)
    {
        Elem temp;
        LS_pop(&ls, &temp);
    }
    printf("栈已清空\n");
    return TRUE;
}
/*
 * 方法名:LS_Destroy
 * 作用:销毁链栈
 * Author: WellLee
 * Last Modified:2018年10月31日23:21:09
 */
Status LS_Destroy(LStack *LS)
{
    free(*LS);
    printf("栈已销毁\n");
    return TRUE;
}
/*
 * 方法名:LS_Empty
 * 作用:判断链栈是否为空
 * Author: WellLee
 * Last Modified:2018年10月31日23:21:09
 */
Status LS_Empty(LStack LS)
{
    if(LS->length == 0)
    {
        return TRUE;
    }
    return FALSE;
}
/*
 * 方法名:LS_show
 * 作用:显示链栈元素
 * Author: WellLee
 * Last Modified:2018年10月31日23:21:09
 */
void LS_show(LStack LS)
{
    if(LS_Empty(LS))
    {
        printf("空栈\n");
        return;
    }
    StackNode head = LS->top->next;
    printf("当前栈有%d个元素,如下所示:\n",LS->length);
    while(head!=NULL)
    {
        printf("%d ",head->elem);
        head = head->next;
    }
    printf("\n");
 
}

Queue.c 源码如下

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
//
// Created by WellLee on 2018/10/31.
//
#include "S_Q.h"
/*
 * 方法名:InitSqQueue
 * 作用:初始化顺序队列
 * Author: WellLee
 * Last Modified:2018年10月31日23:42:16
 */
Status InitSqQueue(SqQueue *Q)
{
    Q->front = 0;
    Q->rear = 0;
    return TRUE;
}
/*
 * 方法名:EnSqQueue
 * 作用:顺序队列入队操作
 * Author: WellLee
 * Last Modified:2018年10月31日23:42:16
 */
Status EnSqQueue(SqQueue *Q, Elem e)
{
    if((Q->rear + 1) % MAXSIZE == Q->front)
    {
        printf("队列满\n");
        return OVERFLOW;
    }
    Q->data[Q->rear] = e;
    Q->rear = (Q->rear+1) % MAXSIZE;
    return TRUE;
}
/*
 * 方法名:DeSqQueue
 * 作用:顺序队列出队操作
 * Author: WellLee
 * Last Modified:2018年10月31日23:42:16
 */
Status DeSqQueue(SqQueue *Q, Elem *e)
{
    if(Q->rear == Q->front)
    {
        printf("队空\n");
        return FALSE;
    }
    *e = Q->data[Q->front];
    Q->front = (Q->front + 1) % MAXSIZE;
}
/*
 * 方法名:ClearSqQueue
 * 作用:清空顺序队列
 * Author: WellLee
 * Last Modified:2018年10月31日23:42:16
 */
Status ClearSqQueue(SqQueue *Q)
{
    memset(Q->data,0, sizeof(Q->data));
    InitSqQueue(Q);
    return TRUE;
}
/*
 * 方法名:DestroySqQueue
 * 作用:销毁顺序队列
 * Author: WellLee
 * Last Modified:2018年10月31日23:42:16
 */
Status DestroySqQueue(SqQueue *Q)
{
    ClearSqQueue(Q);
    printf("队列已经销毁\n");
    return TRUE;
}
/*
 * 方法名:QueueLength
 * 作用:获取顺序队列长度
 * Author: WellLee
 * Last Modified:2018年10月31日23:42:16
 */
Status QueueLength(SqQueue Q, int *length)
{
    *length = (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
    return TRUE;
}
/*
 * 方法名:showQueueElements
 * 作用:输出顺序队列中的元素
 * Author: WellLee
 * Last Modified:2018年10月31日23:42:16
 */
void showQueueElements(SqQueue Q)
{
    int length = 0;
    QueueLength(Q, &length);
    if(length == 0)
    {
        printf("队空\n");
        return;
    }
    printf("当前队列元素如下\n");
    for(int i = 0; i < length; i++)
    {
        printf("%d ", Q.data[Q.front + i]);
    }
    printf("\n");
}
 
 
 
 
/*
 * 方法名:InitLkQueue
 * 作用:初始化链队
 * Author: WellLee
 * Last Modified:2018年10月31日23:42:16
 */
Status InitLkQueue(LinkQueue *Q)
{
    QNodeptr head = (QNodeptr )malloc(sizeof(QNode));
    if(!head)
    {
        printf("内存不足\n");
        return OVERFLOW;
    }
    head->next = NULL;
    Q->front = head;
    Q->rear = head;
    return TRUE;
}
/*
 * 方法名:EnLkQueue
 * 作用:链队压栈操作
 * Author: WellLee
 * Last Modified:2018年10月31日23:42:16
 */
Status EnLkQueue(LinkQueue *Q, Elem e)
{
    QNodeptr node = (QNodeptr )malloc(sizeof(QNode));
    if(!node)
    {
        printf("内存不足\n");
        return OVERFLOW;
    }
    node->data = e;
    node->next = NULL;
    Q->rear->next = node;
    Q->rear = node;
    return TRUE;
}
/*
 * 方法名:DeLkQueue
 * 作用:链队出栈操作
 * Author: WellLee
 * Last Modified:2018年10月31日23:42:16
 */
Status DeLkQueue(LinkQueue *Q, Elem *e)
{
    if(Q->rear == Q->front)
    {
        printf("队空\n");
        return FALSE;
    }
    QNodeptr temp = Q->front->next;
    Q->front->next = temp->next;
    *e = temp->data;
    if(Q->front->next == NULL)
    {
        Q->rear = Q->front;
    }
    free(temp);
    return TRUE;
 
}
/*
 * 方法名:ClearLkQueue
 * 作用:清除链队所有数据
 * Author: WellLee
 * Last Modified:2018年10月31日23:42:16
 */
Status ClearLkQueue(LinkQueue *Q)
{
    while(Q->front != Q->rear)
    {
        Elem temp;
        DeLkQueue(Q, &temp);
    }
    return TRUE;
 
}
/*
 * 方法名:DestroyLkQueue
 * 作用:销毁链队
 * Author: WellLee
 * Last Modified:2018年10月31日23:42:16
 */
Status DestroyLkQueue(LinkQueue *Q)
{
    free(Q->front);
    return TRUE;
}
/*
 * 方法名:LkQueueLength
 * 作用:获取链队元素长度
 * Author: WellLee
 * Last Modified:2018年10月31日23:42:16
 */
Status LkQueueLength(LinkQueue Q, int *length)
{
    QNodeptr temp = Q.front->next;
    int i = 0;
    while(temp != NULL)
    {
        i++;
        temp = temp->next;
    }
    *length  = i;
}
/*
 * 方法名:showLkQueue
 * 作用:显示链队所有元素
 * Author: WellLee
 * Last Modified:2018年10月31日23:42:16
 */
void showLkQueue(LinkQueue Q)
{
    QNodeptr temp = Q.front;
    temp = temp->next;
    if(temp == NULL)
    {
        printf("队空\n");
        return;
    }
    printf("队列元素如下\n");
    while(temp != NULL)
    {
        printf("%d ",temp->data);
        temp = temp->next;
    }
}

【分析】

  • 栈和队列都是特殊的线性表,只不过是对插入和删除做了限制。

  • 栈(Stack)是限定仅在表尾进行插入和删除操作的线性表。根据这样的特性又可以称它为:后进先出表(LIFO)。

  • 队列(Queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。根据这样的特性又可以称它为:先进先出表(FIFO)。

  • 它们均可以用线性表顺序存储结构来实现,但都存在顺序存储的一些弊端,因此它们各自有各自的技巧来解决这个问题。

  • 对于栈来说,如果是两个相同数据类型的栈,可以用数组的两端作为栈底的方法来让两个栈共享数据,这就可以最大化利用数组的空间。

  • 对于队列来说,为了避免数组插入和删除时需要移动数据,于是引进了循环队列,使得队头和队尾可以在数组中循环变化。解决了移动数据的时间损耗,使得原来的删除和插入式O(n)的时间复杂度编程了O(1)。

  • 它们也都可以用链式存储来实现,实现原则上与线性表基本相同。

【总结】

    本文通过学习栈和队列两种数据结构的定义,性质和实现方式,给出了栈/队列的C语言程序实现。加深了对栈/队列的认识,也接触了一些栈在计算机中的应用(递归,中缀->后缀表达式等)。也在从线性表表示栈/队列过程中学习到了一些前人解决问题的思想(共享栈、循环队列的引入)。而这两种数据结构的引入简化了程序设计的问题,划分了不同关注层次,使得思考范围缩小,更更加聚焦于我们要解决问题的核心。

【参考文献】

《大话数据结构》.程杰.清华大学出版社

作者 WellLee

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注