1.栈的顺序存储结构
//*********************************stack_array.h************************************
#ifndef STACK_ARRAY_H
#define STACK_ARRAY_H
#define MAXSIZE 1000
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
typedef int datatype;
typedef struct stack_array
{
datatype data[MAXSIZE];
size_t top;
}SqStack;
//栈初始化
bool InitStack(SqStack *p);
//入栈
bool push(SqStack *stack,datatype e);
//出栈
bool pop(SqStack *stack,datatype *e);
#endif //STACK_ARRAY_H
//*********************************stack_array.c************************************
#include "stack_array.h"
//栈初始化
bool InitStack(SqStack *p)
{
if(NULL == p)return false;
p->top = -1;
return true;
}
//入栈
bool push(SqStack *stack,datatype e)
{
if(MAXSIZE-1 == stack->top)return false;//栈满
++stack->top;//入栈
stack->data[stack->top] = e;
return true;
}
//出栈
bool pop(SqStack *stack,datatype *e)
{
if(-1 == stack->top)return false;
*e = stack->data[stack->top];
--stack->top;
return true;
}
//*********************************stack_arrayTest.c************************************
#include "stack_array.h"
int main()
{
SqStack stack;
InitStack(&stack);
for(int i = 1;i <= 10;i++)
{
push(&stack,i);
}
datatype tmp;
for(int i =1;i <= 10;i++)
{
pop(&stack,&tmp);
printf("%d \n",tmp);
}
}104
1
//*********************************stack_array.h************************************
2
#ifndef STACK_ARRAY_H
3
#define STACK_ARRAY_H
4
5
#define MAXSIZE 1000
6
#include <stdio.h>
7
#include <stdbool.h>
8
#include <stdlib.h>
9
typedef int datatype;
10
11
typedef struct stack_array
12
{
13
datatype data[MAXSIZE];
14
size_t top;
15
}SqStack;
16
17
18
//栈初始化
19
bool InitStack(SqStack *p);
20
21
22
//入栈
23
bool push(SqStack *stack,datatype e);
24
25
26
//出栈
27
bool pop(SqStack *stack,datatype *e);
28
29
30
#endif //STACK_ARRAY_H
31
32
33
//*********************************stack_array.c************************************
34
35
#include "stack_array.h"
36
37
//栈初始化
38
bool InitStack(SqStack *p)
39
{
40
if(NULL == p)return false;
41
p->top = -1;
42
return true;
43
}
44
45
//入栈
46
bool push(SqStack *stack,datatype e)
47
{
48
if(MAXSIZE-1 == stack->top)return false;//栈满
49
50
++stack->top;//入栈
51
stack->data[stack->top] = e;
52
53
return true;
54
}
55
56
57
//出栈
58
bool pop(SqStack *stack,datatype *e)
59
{
60
if(-1 == stack->top)return false;
61
*e = stack->data[stack->top];
62
--stack->top;
63
return true;
64
}
65
66
67
68
//*********************************stack_arrayTest.c************************************
69
70
#include "stack_array.h"
71
72
73
74
75
76
int main()
77
78
{
79
80
SqStack stack;
81
82
InitStack(&stack);
83
84
for(int i = 1;i <= 10;i++)
85
86
{
87
88
push(&stack,i);
89
90
}
91
92
datatype tmp;
93
94
for(int i =1;i <= 10;i++)
95
96
{
97
98
pop(&stack,&tmp);
99
100
printf("%d \n",tmp);
101
102
}
103
104
}
2.两栈共享空间（栈的顺序存储结构）
//*******************************stack_share.h***********************************
#ifndef STACK_SHARE_H
#define STACK_SHARE_H
#define MAXSIZE 1000
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <memory.h>
typedef int datatype;
typedef struct stack_share
{
datatype data[MAXSIZE];
size_t top1;
size_t top2;
}SqDoubleStack;
//初始化栈
void InitStack(SqDoubleStack *stack);
//压栈
bool push(SqDoubleStack *stack,datatype e,int num);
//弹栈
bool pop(SqDoubleStack *stack,datatype *e,int num);
#endif //STACK_SHARE_H
//*******************************stack_share.c***********************************
#include "stack_share.h"
//初始化栈
void InitStack(SqDoubleStack *stack)
{
stack->top1 = -1;
stack->top2 = MAXSIZE;
}
//压栈
bool push(SqDoubleStack *stack,datatype e,int num)
{
if(stack->top1+1 == stack->top2)return false;
if(1 == num)
{
stack->data[++stack->top1] = e;
}
else if(2 == num)
{
stack->data[--stack->top2] = e;
}
return true;
}
//弹栈
bool pop(SqDoubleStack *stack,datatype *e,int num)
{
if(1 == num)
{
if(-1 != stack->top1)return false;
*e = stack->data[stack->top1--];
}
else if(2 == num)
{
if(MAXSIZE != stack->top2)return false;
*e = stack->data[stack->top2++];
}
return true;
}
//*******************************stack_shareTest.c***********************************
#include "stack_share.h"
int main()
{
SqDoubleStack stack;
InitStack(&stack);
memset(stack.data,0,sizeof(int)*1000);
for(int i =1;i <= 10;i++)
{
push(&stack,i,1);
}
for(int i =1;i <= 10;i++)
{
push(&stack,i,2);
}
for(int i = 0;i < 1000;i++)
{
printf("%d ",stack.data[i]);
}
return 0;
}126
1
//*******************************stack_share.h***********************************
2
3
#ifndef STACK_SHARE_H
4
#define STACK_SHARE_H
5
6
#define MAXSIZE 1000
7
#include <stdio.h>
8
#include <stdbool.h>
9
#include <stdlib.h>
10
#include <memory.h>
11
typedef int datatype;
12
13
typedef struct stack_share
14
{
15
datatype data[MAXSIZE];
16
size_t top1;
17
size_t top2;
18
}SqDoubleStack;
19
20
21
//初始化栈
22
void InitStack(SqDoubleStack *stack);
23
24
//压栈
25
bool push(SqDoubleStack *stack,datatype e,int num);
26
27
//弹栈
28
bool pop(SqDoubleStack *stack,datatype *e,int num);
29
30
31
32
#endif //STACK_SHARE_H
33
34
35
//*******************************stack_share.c***********************************
36
37
#include "stack_share.h"
38
39
//初始化栈
40
void InitStack(SqDoubleStack *stack)
41
{
42
stack->top1 = -1;
43
stack->top2 = MAXSIZE;
44
}
45
46
//压栈
47
bool push(SqDoubleStack *stack,datatype e,int num)
48
{
49
if(stack->top1+1 == stack->top2)return false;
50
51
if(1 == num)
52
{
53
stack->data[++stack->top1] = e;
54
}
55
else if(2 == num)
56
{
57
stack->data[--stack->top2] = e;
58
}
59
return true;
60
}
61
62
//弹栈
63
bool pop(SqDoubleStack *stack,datatype *e,int num)
64
{
65
if(1 == num)
66
{
67
if(-1 != stack->top1)return false;
68
*e = stack->data[stack->top1--];
69
}
70
else if(2 == num)
71
{
72
if(MAXSIZE != stack->top2)return false;
73
*e = stack->data[stack->top2++];
74
}
75
return true;
76
}
77
78
79
80
//*******************************stack_shareTest.c***********************************
81
82
#include "stack_share.h"
83
84
85
86
87
88
int main()
89
90
{
91
92
SqDoubleStack stack;
93
94
InitStack(&stack);
95
96
memset(stack.data,0,sizeof(int)*1000);
97
98
for(int i =1;i <= 10;i++)
99
100
{
101
102
push(&stack,i,1);
103
104
}
105
106
for(int i =1;i <= 10;i++)
107
108
{
109
110
push(&stack,i,2);
111
112
}
113
114
115
116
for(int i = 0;i < 1000;i++)
117
118
{
119
120
printf("%d ",stack.data[i]);
121
122
}
123
124
return 0;
125
126
}
3.*****链栈*****
//****************************stack_link.h************************************
#ifndef STACK_LINK_H
#define STACK_LINK_H
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
typedef int datatype;
typedef struct StackNode
{
datatype data;
struct StackNode *next;
}StackNode;
typedef struct StackLink
{
StackNode *top;
size_t count;
}Stack;
//创建链栈
Stack *create();
//压栈
bool push(Stack *stack,datatype e);
//弹栈
bool pop(Stack *stack,datatype *e);
#endif //STACK_LINK_H
//****************************stack_link.c************************************
#include "stack_link.h"
//创建链栈
Stack *create()
{
Stack *stack = (Stack *)malloc(sizeof(Stack));
stack->top = NULL;
stack->count = 0;
return stack;
}
//压栈
bool push(Stack *stack,datatype e)
{
if(NULL == stack)return false;
StackNode *node = (StackNode *)malloc(sizeof(StackNode)); //申请新节点
node->data = e;//为新节点赋值
node->next = stack->top;
stack->top = node;//使top指向新节点
++stack->count;//count++
return true;
}
//弹栈
bool pop(Stack *stack,datatype *e)
{
if(NULL == stack->top)return false;//如果栈空，弹出失败
StackNode *curr = stack->top;//保存栈顶节点地址
StackNode *next = curr->next;//保存栈顶下一个节点地址
*e = curr->data;//保存弹出值
stack->top = next;//使top指向原栈顶下一个节点
--stack->count;
free(curr);
return true;
}
//****************************stack_linkTest.c************************************
#include "stack_link.h"
int main()
{
Stack *stack = create();
for(int i = 1;i <= 10;i++)
{
push(stack,i);
}
datatype tmp;
for(int i = 1;i <= 10;i++)
{
pop(stack,&tmp);
printf("%d ",tmp);
}
printf("\n");
return 0;
}x
1
//****************************stack_link.h************************************
2
#ifndef STACK_LINK_H
3
4
#define STACK_LINK_H
5
6
7
8
#include <stdio.h>
9
#include <stdbool.h>
10
#include <stdlib.h>
11
typedef int datatype;
12
13
14
typedef struct StackNode
15
16
{
17
18
datatype data;
19
20
struct StackNode *next;
21
22
}StackNode;
23
24
typedef struct StackLink
25
26
{
27
28
StackNode *top;
29
30
size_t count;
31
32
}Stack;
33
34
35
36
//创建链栈
37
Stack *create();
38
39
//压栈
40
41
bool push(Stack *stack,datatype e);
42
43
//弹栈
44
45
bool pop(Stack *stack,datatype *e);
46
47
48
#endif //STACK_LINK_H
49
50
51
52
//****************************stack_link.c************************************
53
#include "stack_link.h"
54
55
56
//创建链栈
57
58
Stack *create()
59
60
{
61
62
Stack *stack = (Stack *)malloc(sizeof(Stack));
63
64
stack->top = NULL;
65
66
stack->count = 0;
67
68
return stack;
69
70
}
71
72
73
74
//压栈
75
76
bool push(Stack *stack,datatype e)
77
78
{
79
80
if(NULL == stack)return false;
81
82
83
84
StackNode *node = (StackNode *)malloc(sizeof(StackNode)); //申请新节点
85
86
87
88
node->data = e;//为新节点赋值
89
90
node->next = stack->top;
91
92
93
94
stack->top = node;//使top指向新节点
95
96
++stack->count;//count++
97
98
return true;
99
100
}
101
102
103
104
105
106
//弹栈
107
108
bool pop(Stack *stack,datatype *e)
109
110
{
111
112
if(NULL == stack->top)return false;//如果栈空，弹出失败
113
114
115
116
StackNode *curr = stack->top;//保存栈顶节点地址
117
118
StackNode *next = curr->next;//保存栈顶下一个节点地址
119
120
121
122
*e = curr->data;//保存弹出值
123
124
stack->top = next;//使top指向原栈顶下一个节点
125
126
--stack->count;
127
128
129
130
free(curr);
131
132
return true;
133
134
}
135
136
137
138
//****************************stack_linkTest.c************************************
139
#include "stack_link.h"
140
141
142
143
int main()
144
145
{
146
147
Stack *stack = create();
148
149
for(int i = 1;i <= 10;i++)
150
151
{
152
153
push(stack,i);
154
155
}
156
157
datatype tmp;
158
159
for(int i = 1;i <= 10;i++)
160
161
{
162
163
pop(stack,&tmp);
164
165
printf("%d ",tmp);
166
167
}
168
169
printf("\n");
170
171
return 0;
172
173
}
4.循环队列（顺序存储结构）
//************************************circular_queue.h****************************************
#ifndef CIRCULAR_LINK_H
#define CIRCULAR_LINK_H
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#define MAXSIZE 1000
typedef int datatype;
typedef struct
{
datatype data[MAXSIZE];
size_t front;
size_t rear;
}SqQueue;
//初始化队列
void InitQueue(SqQueue *Q);
//求队列长度
size_t length(SqQueue Q);
//入队
bool EnQueue(SqQueue *Q,datatype e);
//出队
bool DeQueue(SqQueue *Q,datatype *e);
#endif //CIRCULAR_LINK_H
//************************************circular_queue.c****************************************
#include "circular_queue.h"
//初始化队列
void InitQueue(SqQueue *Q)
{
Q->front = 0;
Q->rear = 0;
}
//求队列长度
size_t length(SqQueue Q)
{
return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
}
//入队
bool EnQueue(SqQueue *Q,datatype e)
{
if((Q->rear+1)%MAXSIZE == Q->front)return false;
Q->data[Q->rear] = e;
Q->rear = (Q->rear+1)%MAXSIZE;
return false;
}
//出队
bool DeQueue(SqQueue *Q,datatype *e)
{
if(Q->front == Q->rear)return false;
*e = Q->data[Q->front];
Q->front = (Q->front+1)%MAXSIZE;
return true;
}
//************************************circular_queueTest.c****************************************
#include "circular_queue.h"
int main()
{
SqQueue Q;
InitQueue(&Q);
printf("length:%d \n",length(Q));
for(size_t i = 1;i <= 1000;i++)
{
EnQueue(&Q,i);
}
printf("length:%d \n",length(Q));
size_t temp;
for(size_t i = 1;i <= 10;i++)
{
DeQueue(&Q,&temp);
printf("%d ",temp);
}
printf("\n");
printf("length:%d \n",length(Q));
for(size_t i = 1;i <= 10;i++)
{
EnQueue(&Q,i);
}
printf("length:%d \n",length(Q));
for(size_t i = 1;i <= 1000;i++)
{
DeQueue(&Q,&temp);
printf("%d ",temp);
}
printf("length:%d \n",length(Q));
return 0;
}x
112
1
//************************************circular_queue.h****************************************
2
#ifndef CIRCULAR_LINK_H
3
#define CIRCULAR_LINK_H
4
5
#include <stdio.h>
6
#include <stdbool.h>
7
#include <stdlib.h>
8
#define MAXSIZE 1000
9
typedef int datatype;
10
11
typedef struct
12
{
13
datatype data[MAXSIZE];
14
size_t front;
15
size_t rear;
16
}SqQueue;
17
18
19
//初始化队列
20
void InitQueue(SqQueue *Q);
21
22
//求队列长度
23
size_t length(SqQueue Q);
24
25
//入队
26
bool EnQueue(SqQueue *Q,datatype e);
27
28
//出队
29
bool DeQueue(SqQueue *Q,datatype *e);
30
31
32
#endif //CIRCULAR_LINK_H
33
34
35
//************************************circular_queue.c****************************************
36
#include "circular_queue.h"
37
38
39
//初始化队列
40
void InitQueue(SqQueue *Q)
41
{
42
Q->front = 0;
43
Q->rear = 0;
44
}
45
46
//求队列长度
47
size_t length(SqQueue Q)
48
{
49
return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
50
}
51
52
//入队
53
bool EnQueue(SqQueue *Q,datatype e)
54
{
55
if((Q->rear+1)%MAXSIZE == Q->front)return false;
56
57
Q->data[Q->rear] = e;
58
Q->rear = (Q->rear+1)%MAXSIZE;
59
return false;
60
}
61
62
//出队
63
bool DeQueue(SqQueue *Q,datatype *e)
64
{
65
if(Q->front == Q->rear)return false;
66
67
*e = Q->data[Q->front];
68
Q->front = (Q->front+1)%MAXSIZE;
69
return true;
70
}
71
72
73
74
//************************************circular_queueTest.c****************************************
75
#include "circular_queue.h"
76
77
78
int main()
79
{
80
SqQueue Q;
81
InitQueue(&Q);
82
83
printf("length:%d \n",length(Q));
84
85
for(size_t i = 1;i <= 1000;i++)
86
{
87
EnQueue(&Q,i);
88
}
89
printf("length:%d \n",length(Q));
90
size_t temp;
91
92
for(size_t i = 1;i <= 10;i++)
93
{
94
DeQueue(&Q,&temp);
95
printf("%d ",temp);
96
}
97
printf("\n");
98
printf("length:%d \n",length(Q));
99
for(size_t i = 1;i <= 10;i++)
100
{
101
EnQueue(&Q,i);
102
}
103
104
printf("length:%d \n",length(Q));
105
for(size_t i = 1;i <= 1000;i++)
106
{
107
DeQueue(&Q,&temp);
108
printf("%d ",temp);
109
}
110
printf("length:%d \n",length(Q));
111
return 0;
112
}
5.链队列
//*******************************queue_link.h****************************************
#ifndef QUEUE_LINK_H
#define QUEUE_LINK_H
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
typedef int datatype;
typedef struct QNode
{
datatype data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
QueuePtr front,rear;
}LinkQueue;
//创建队列
LinkQueue create();
//入队
bool EnQueue(LinkQueue *Q,datatype e);
//出队
bool DeQueue(LinkQueue *Q,datatype *e);
#endif //QUEUE_LINK_H
//*******************************queue_link.c****************************************
#include "queue_link.h"
//创建队列
LinkQueue create()
{
QueuePtr head = (QueuePtr)malloc(sizeof(QNode));
head->next = NULL;
LinkQueue Q;
Q.front = head;
Q.rear = head;
return Q;
}
//入队
bool EnQueue(LinkQueue *Q,datatype e)
{
QueuePtr s = (QueuePtr)malloc(sizeof(QNode));//创建新节点
if(!s)return false;
s->data = e; //设置新节点数据
s->next = NULL;
Q->rear->next = s; //将原来的队尾指向新节点
Q->rear = s; //队尾指针指向s
return true;
}
//出队
bool DeQueue(LinkQueue *Q,datatype *e)
{
if(Q->front == Q->rear)return false;
QueuePtr node = Q->front->next;//保存要删除节点的地址
QueuePtr behind = node->next;//保存要删除节点下一个节点的地址
*e = node->data;//保存数据
Q->front->next = behind;//使front指向下一个节点
if(Q->rear == node)Q->rear = Q->front;//假如出队前队列只有一个元素，则出队后队列为空，队尾应该指向头节点。
free(node);
return true;
}
//*******************************queue_linkTest.c****************************************
#include "queue_link.h"
int main()
{
LinkQueue Q = create();
for(size_t i = 1;i <= 10;i++)
{
EnQueue(&Q,i);
}
size_t tmp;
for(size_t i = 1;i <= 10;i++)
{
DeQueue(&Q,&tmp);
printf("%d ",tmp);
}
printf("\n");
return 0;
}x
150
1
//*******************************queue_link.h****************************************
2
#ifndef QUEUE_LINK_H
3
#define QUEUE_LINK_H
4
5
6
#include <stdio.h>
7
#include <stdbool.h>
8
#include <stdlib.h>
9
10
11
12
typedef int datatype;
13
14
15
16
typedef struct QNode
17
18
{
19
20
datatype data;
21
22
struct QNode *next;
23
24
}QNode,*QueuePtr;
25
26
27
typedef struct
28
29
{
30
31
QueuePtr front,rear;
32
33
}LinkQueue;
34
35
//创建队列
36
37
LinkQueue create();
38
39
//入队
40
41
bool EnQueue(LinkQueue *Q,datatype e);
42
43
//出队
44
45
bool DeQueue(LinkQueue *Q,datatype *e);
46
47
48
#endif //QUEUE_LINK_H
49
50
51
//*******************************queue_link.c****************************************
52
#include "queue_link.h"
53
54
55
//创建队列
56
57
LinkQueue create()
58
59
{
60
61
QueuePtr head = (QueuePtr)malloc(sizeof(QNode));
62
63
head->next = NULL;
64
65
LinkQueue Q;
66
67
Q.front = head;
68
69
Q.rear = head;
70
71
return Q;
72
73
}
74
75
76
77
//入队
78
79
bool EnQueue(LinkQueue *Q,datatype e)
80
81
{
82
83
QueuePtr s = (QueuePtr)malloc(sizeof(QNode));//创建新节点
84
85
if(!s)return false;
86
87
88
89
s->data = e; //设置新节点数据
90
91
s->next = NULL;
92
93
94
95
Q->rear->next = s; //将原来的队尾指向新节点
96
97
Q->rear = s; //队尾指针指向s
98
99
return true;
100
101
}
102
103
104
105
//出队
106
107
bool DeQueue(LinkQueue *Q,datatype *e)
108
109
{
110
111
if(Q->front == Q->rear)return false;
112
113
114
115
QueuePtr node = Q->front->next;//保存要删除节点的地址
116
117
QueuePtr behind = node->next;//保存要删除节点下一个节点的地址
118
119
120
121
*e = node->data;//保存数据
122
123
124
125
Q->front->next = behind;//使front指向下一个节点
126
127
128
129
if(Q->rear == node)Q->rear = Q->front;//假如出队前队列只有一个元素，则出队后队列为空，队尾应该指向头节点。
130
131
132
133
free(node);
134
135
136
137
return true;
138
139
}
140
141
142
143
144
145
//*******************************queue_linkTest.c****************************************
146
#include "queue_link.h"
147
148
149
150
int main()
151
152
{
153
154
LinkQueue Q = create();
155
156
157
158
for(size_t i = 1;i <= 10;i++)
159
160
{
161
162
EnQueue(&Q,i);
163
164
}
165
166
167
168
size_t tmp;
169
170
for(size_t i = 1;i <= 10;i++)
171
172
{
173
174
DeQueue(&Q,&tmp);
175
176
printf("%d ",tmp);
177
178
}
179
180
printf("\n");
181
182
return 0;
183
184
}