本文共 3014 字，大约阅读时间需要 10 分钟。

第三章 栈和队列

3.1.1 栈的基本概念

3.1.2 顺序栈的实现

#include <stdio.h>#define MaxSize 10typedef struct {   	int date[MaxSize];	int top;}SqStack;void InitStack(SqStack& S){   	S.top = -1;}bool StackEmpty(SqStack S){   	if (S.top == -1)	{   		return true;	}	else	{   		return false;	}}bool Push(SqStack& S, int x){   	printf("请输入要进栈的数:");	while(S.top!=MaxSize - 1)	{   		scanf_s("%d", &x);		S.top = S.top + 1;		S.date[S.top] = x;	}	return true;}void print(SqStack& S){   	for (int i = 0; i <= S.top; i++)	{   		printf("%d ", S.date[i]);	}	printf("\n");}bool Pop(SqStack& S, int &x){   	if (S.top == -1)	{   		return false;	}	x = S.date[S.top];	S.top = S.top - 1;	return true;}void main(){   	int x = 0;	SqStack S;	InitStack(S);	StackEmpty(S);	Push(S, x);	printf("进栈的数有:");	print(S);	Pop(S,x);	printf("出栈的栈顶为:%d\n",x);	printf("新栈的数有:");	print(S);}//请输入要进栈的数:65 43 43 76 65 34 76 23 43 12//进栈的数有 : 65 43 43 76 65 34 76 23 43 12//出栈的栈顶为 : 12//新栈的数有 : 65 43 43 76 65 34 76 23 43

#include <stdio.h>#define MaxSize 10typedef struct {   	int date[MaxSize];	int top;}SqStack;void InitStack(SqStack& S){   	S.top = 0;}bool StackEmpty(SqStack S){   	if (S.top == 0)	{   		return true;	}	else	{   		return false;	}}bool Push(SqStack& S, int x){   	printf("请输入要进栈的数:");	while(S.top!=MaxSize)	{   		scanf_s("%d", &x);		S.date[S.top] = x;		S.top = S.top + 1;	}	return true;}void print(SqStack& S){   	for (int i = 0; i < S.top; i++)	{   		printf("%d ", S.date[i]);	}	printf("\n");}bool Pop(SqStack& S, int &x){   	if (S.top ==0)	{   		return false;	}	S.top = S.top - 1;	x = S.date[S.top];	return true;}void main(){   	int x = 0;	SqStack S;	InitStack(S);	StackEmpty(S);	Push(S, x);	printf("进栈的数有:");	print(S);	Pop(S,x);	printf("出栈的栈顶为:%d\n",x);	printf("新栈的数有:");	print(S);}//请输入要进栈的数:65 43 43 76 65 34 76 23 43 12//进栈的数有 : 65 43 43 76 65 34 76 23 43 12//出栈的栈顶为 : 12//新栈的数有 : 65 43 43 76 65 34 76 23 43

3.1.3 链栈的实现

带头结点

在这里插入代码片

不带头结点

在这里插入代码片

3.2.1 队列的基本概念

3.2.2 队列的顺序实现

#include<stdio.h>#define MaxSize 10typedef struct{   	int data[MaxSize];	int front, rear;}SqQueue;//初始化队列void InitQueue(SqQueue &Q){   	Q.front = Q.rear = 0;}//判断队列是否为空bool QueueEmpty(SqQueue Q){   	if (Q.rear == Q.front)	{   		return true;	}	else	{   		return false;	}}//打印void print(SqQueue& Q){   	for (int i = Q.front; i < Q.rear; i++)	{   		printf("%d ", Q.data[i]);	}	printf("\n");}//入队bool EnQueue(SqQueue &Q,int x){   	printf("请输入入队的值:");	while ((Q.rear + 1) % MaxSize != Q.front)	{   		scanf_s("%d", &x);		Q.data[Q.rear] = x;		Q.rear = (Q.rear + 1) % MaxSize;	}	return true;}//出队bool DeQueue(SqQueue& Q, int& x){   	while (Q.rear == Q.front)	{   		return false;	}	x = Q.data[Q.front];	Q.front=(Q.front + 1) % MaxSize;	return true;}void main(){   	int x = 0;	SqQueue Q;	InitQueue(Q);	QueueEmpty(Q);	EnQueue(Q,x);	printf("入队的数有:");	print(Q);	DeQueue(Q, x);	printf("出队元素的值为:%d\n", x);	printf("现在的队伍有:");	print(Q);}//请输入入队的值:23 43 76 86 98 56 78 56 45 98//入队的数有 : 23 43 76 86 98 56 78 56 45//出队元素的值为 : 23//现在的队伍有 : 43 76 86 98 56 78 56 45

3.2.3 队列的链式实现

在这里插入代码片

3.2.4 双端队列