数据结构--栈和队列

1.顺序栈各种基本运算的算法：

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

#define Maxsize 100

typedef char ElemType;

typedef struct
{
	ElemType data[Maxsize];
	int top;
}SqStack;

//初始化
void InitStack(SqStack** s)
{
	*s = (SqStack*)malloc(sizeof(SqStack));
	(*s)->top = -1;
}

//销毁
void destroyStack(SqStack** s)
{
	free(*s);
	*s = NULL;
}

//判断栈空
void StackEmpty(SqStack* s)
{
	if (s->top == -1)
	{
		printf("栈为空\n");
	}
	else
	{
		printf("栈为非空\n");
	}
}

//进栈
bool Push(SqStack** s, ElemType e)
{
	if ((*s)->top == Maxsize - 1)
	{
		return false;
	}

	(*s)->top++;
	(*s)->data[(*s)->top] = e;
	return true;
}

//出栈
bool Pop(SqStack** s, ElemType* e)
{
	if ((*s)->top == -1)
	{
		return false;
	}

	*e = (*s)->data[(*s)->top];
	(*s)->top--;

	return true;
}

bool GetTop(SqStack* s, ElemType* e)
{
	if (s->top == -1)
	{
		return false;
	}

	*e = s->data[s->top];


	return true;
}

int main()
{
	ElemType e;
	SqStack* s;

	//初始化
	InitStack(&s);

	//判断是否为空
	printf("初始化后：");
	StackEmpty(s);

	//入栈
	Push(&s, 'a');
	Push(&s, 'b');
	Push(&s, 'c');
	Push(&s, 'd');
	Push(&s, 'e');

	printf("入栈之后：");
	StackEmpty(s);

	//取顶
	if (GetTop(s, &e))
	{
		printf("当前栈顶元素为:%c\n", e);
	}

	printf("元素出栈：");
	//出栈
	while (s->top != -1)
	{
		Pop(&s, &e);
		printf("%c ", e);
	}

	printf("\n");

	//销毁
	destroyStack(&s);

	return 0;
}

2.链栈各种基本运算的算法：

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

typedef char ElemType;

typedef struct
{
	ElemType data;
	struct linknode* next;
}LinkStNode;

//初始化
void initStack(LinkStNode** s)
{
	*s = (LinkStNode*)malloc(sizeof(LinkStNode));
	(*s)->next = NULL;
}

//销毁
void destroyStack(LinkStNode** s)
{
	LinkStNode* current = *s;
	LinkStNode* n = NULL;

	while (current != NULL)
	{
		n = current->next;
		free(current);
		current = n;
	}
	free(*s);
	*s = NULL;
}

//判断栈空
void emptyStack(LinkStNode* s)
{
    // 检查头节点的 next 指针是否为 NULL 来判断链栈是否为空
    if (s != NULL && s->next == NULL)
    {
        printf("栈为空\n");
    }
    else
    {
        printf("栈为非空\n");
    }
}

//进栈
void Push(LinkStNode** s, ElemType e)
{
	LinkStNode* newNode = (LinkStNode*)malloc(sizeof(LinkStNode));

	newNode->data = e;
	newNode->next = (*s)->next;
	(*s)->next = newNode;
}

//出栈
bool Pop(LinkStNode** s, ElemType* e)
{
	LinkStNode* pNode = (LinkStNode*)malloc(sizeof(LinkStNode));

	if ((*s)->next == NULL)
	{
		return false;
	}

	pNode = (*s)->next;
	*e = pNode->data;
	(*s)->next = pNode->next;

	free(pNode);

	return true;
}

//取顶
bool GetTop(LinkStNode* s, ElemType* e)
{
	if (s->next == NULL)
	{
		return false;
	}

	s = s->next;
	*e = s->data;
	return true;
}


int main()
{
	ElemType e;
	LinkStNode* s;

	//初始化
	initStack(&s);

	//判断是否为空
	printf("初始化后：");
	emptyStack(s);

	//入栈
	Push(&s, 'a');
	Push(&s, 'b');
	Push(&s, 'c');
	Push(&s, 'd');
	Push(&s, 'e');

	printf("入栈之后：");
	emptyStack(s);

	
	if (GetTop(s, &e))
	{
		printf("当前栈顶元素为:%c\n", e);
	}

	printf("元素出栈：");
	//出栈
	while (s->next != NULL)
	{
		Pop(&s, &e);
		printf("%c ", e);
	}

	printf("\n");

	//销毁
	destroyStack(&s);

	return 0;
}

3.循环队列各种基本运算的算法：

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

#define MaxSize 100

typedef char ElemType;

typedef struct
{
	ElemType data[MaxSize];
	int front;
	int rear;
}SqQueue;

//初始化
void initQueue(SqQueue** q)
{
	*q = (SqQueue*)malloc(sizeof(SqQueue));
	(*q)->front = (*q)->rear = NULL;
}

//销毁
void destroyQueue(SqQueue** q)
{
	free(q);
}

//判断队空
void emptyQueue(SqQueue* q)
{
	if ((q->rear + 1) % MaxSize == q->front)
	{
		printf("队满\n");
	}
	else
	{
		printf("队空\n");
	}
}

//进队
void enQueue(SqQueue** q, ElemType e)
{
	if (((*q)->rear + 1) % MaxSize == (*q)->front)
	{
		printf("队满\n");
	}

	(*q)->rear = ((*q)->rear + 1) % MaxSize;
	(*q)->data[(*q)->rear] = e;
}

//出队
bool deQueue(SqQueue** q, ElemType* e)
{
	if ((*q)->front == (*q)->rear)
	{
		return false; // 队列为空，无法出队
	}

	(*q)->front = ((*q)->front + 1) % MaxSize;
	*e = (*q)->data[(*q)->front];
	return true; // 出队成功
}


int main()
{
	ElemType e;
	SqQueue* q;

	//初始化
	initQueue(&q);

	//判断空满
	emptyQueue(q);

	//入队
	enQueue(&q, 'a');
	enQueue(&q, 'b');
	enQueue(&q, 'c');
	enQueue(&q, 'd');
	enQueue(&q, 'e');

	printf("入队之后：");
	emptyQueue(q);

	printf("元素出队：");
	//出栈
	while (!(q->front == q->rear))
	{
		deQueue(&q, &e);
		printf("%c ", e);
	}

	printf("\n");

	//销毁
	destroyQueue(&q);

	return 0;
}

4.顺序队列非循环队列各种基本算法的实现：

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

#define MaxSize 100
typedef char ElemType;
typedef struct
{
	ElemType data[MaxSize];
	int front, rear;						//队头和队尾指针
} SqQueue;

void initQueue(SqQueue** q)
{
	*q = (SqQueue*)malloc(sizeof(SqQueue));
	(*q)->front = (*q)->rear = -1;
}

void destroyQueue(SqQueue** q)			//销毁队列
{
	free(*q);
}

void emptyQueue(SqQueue* q)				//判断队列是否为空
{
	if (q->front == q->rear)
	{
		printf("队满\n");
	}
	else
	{
		printf("队空\n");
	}
}

void enQueue(SqQueue** q, ElemType e)	//进队
{
	if ((*q)->rear == MaxSize - 1)				//队满上溢出
		printf("队满\n");				//返回假

	(*q)->rear++;							//队尾增1
	(*q)->data[(*q)->rear] = e;					//rear位置插入元素e

}

bool deQueue(SqQueue** q, ElemType* e)	//出队
{
	if ((*q)->front == (*q)->rear)				//队空下溢出
		return false;
	(*q)->front++;
	*e = (*q)->data[(*q)->front];
	return true;
}

int main()
{
	ElemType e;
	SqQueue* q;

	//初始化
	initQueue(&q);

	//判断空满
	emptyQueue(q);

	//入队
	enQueue(&q, 'a');
	enQueue(&q, 'b');
	enQueue(&q, 'c');
	enQueue(&q, 'd');
	enQueue(&q, 'e');

	printf("入队之后：");
	emptyQueue(q);

	printf("元素出队：");
	//出栈
	while (!(q->front == q->rear))
	{
		deQueue(&q, &e);
		printf("%c ", e);
	}

	printf("\n");

	//销毁
	destroyQueue(&q);

	return 0;
}

5.链队列各种基本运算的算法：

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

typedef char ElemType;

typedef struct DataNode
{
	ElemType data;
	struct DataNode* next;
}DataNode;

typedef struct
{
	DataNode* front;
	DataNode* rear;
}LinkQueue;

//初始化
void initQueue(LinkQueue** q)
{
	*q = (LinkQueue*)malloc(sizeof(LinkQueue));
	(*q)->front = (*q)->rear = NULL;
}

//销毁
void destroyQueue(LinkQueue** q)
{
	DataNode* current = (*q)->front;
	DataNode* next;

	while (current != NULL)
	{
		next = current->next;
		free(current);
		current = next;
	}

	free(*q);
	*q = NULL; // 将指针置为空，以避免悬空指针
}


//判断队空
void emptyQueue(LinkQueue* q)
{
	if (q->front == NULL || q->rear == NULL)
	{
		printf("队空\n");
	}
	else
	{
		printf("队满\n");
	}
}

//进队
void enQueue(LinkQueue** q, ElemType e)
{
	DataNode* newNode = (DataNode*)malloc(sizeof(DataNode));

	newNode->data = e;
	newNode->next = NULL;

	if ((*q)->front == NULL || (*q)->rear == NULL)
	{
		(*q)->front = (*q)->rear = newNode;
	}
	else
	{
		(*q)->rear->next = newNode;
		(*q)->rear = newNode;
	}
}

//出队
bool deQueue(LinkQueue** q, ElemType* e)
{
	DataNode* todelete = (DataNode*)malloc(sizeof(DataNode));

	if ((*q)->front == NULL || (*q)->rear == NULL)
		return false;

	todelete = (*q)->front;

	if ((*q)->front == (*q)->rear)
		(*q)->front = (*q)->rear = NULL;
	else
		(*q)->front = (*q)->front->next;

	*e = todelete->data;
	free(todelete);

	return true;

}


int main()
{
	ElemType e;
	LinkQueue* q;

	//初始化
	initQueue(&q);

	//判断空满
	emptyQueue(q);

	//入队
	printf("依次入队");
	enQueue(&q, 'a');
	enQueue(&q, 'b');
	enQueue(&q, 'c');
	enQueue(&q, 'd');
	enQueue(&q, 'e');

	printf("入队之后：");
	emptyQueue(q);

	printf("元素出队：");
	//出栈
	while (!(q->front == NULL || q->rear == NULL))
	{
		deQueue(&q, &e);
		printf("%c ", e);
	}

	printf("\n");

	//销毁
	destroyQueue(&q);

	return 0;
}

6.栈实现迷宫求解的最短路径：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MaxSize 100
#define M 4
#define N 4
int mg[M + 2][N + 2] =
{
	{1,1,1,1,1,1},
	{1,0,0,0,1,1},
	{1,0,1,0,0,1},
	{1,0,0,0,1,1},
	{1,1,0,0,0,1},
	{1,1,1,1,1,1}
};

//迷宫栈基本运算
#define MaxSize 100 // 假设的最大大小

// 定义结构体类型
typedef struct {
	int i;  // 当前方块的行号
	int j;  // 当前方块的列号
	int di; // di是下一可走相邻方位的方位号
} Box;

// 使用定义好的结构体类型来声明数组
Box St[MaxSize], Path[MaxSize];

int top = -1;
int count = 1;
int minlen = MaxSize;

//输出一条路径并求最短路径
void dispapath()
{
	int k;
	printf("%5d: ", count++);

	for (k = 0; k <= top; k++)
	{
		printf("( %d , %d )", St[k].i, St[k].j);
	}
	printf("\n");

	if (top + 1 < minlen)
	{
		for (k = 0; k <= top; k++)
		{
			Path[k] = St[k];
		}
		minlen = top + 1;
	}
}

//输出第一条最短路径
void dispminpath()
{
	printf("最短路径如下：\n");
	printf("长度：%d\n", minlen);
	printf("路径:\n");
	int k;
	for (k = 0; k <= minlen; k++)
	{
		printf("( %d , %d )", Path[k].i, Path[k].j);
	}
	printf("\n");
}

//---------------------------------------------------------
void mgpath(int xi, int yi, int xe, int ye)	//求解路径为:(xi,yi)->(xe,ye)
{
	int i, j, di, i1, j1, k;
	bool find;
	top++;
	
	St[top].i = xi;
	St[top].j = yi;
	St[top].di = -1;

	mg[xi][yi] = -1;

	while (top > -1)					//栈不空时循环
	{
		i = St[top].i; 
		j = St[top].j; 
		di = St[top].di;

		if (i == xe && j == ye)					//找到了出口,输出该路径
		{
			dispapath();
			mg[i][j] = 0;
			top--;
			i = St[top].i;
			j = St[top].j;
			di = St[top].di;
		}
		find = false;

		while (di < 4 && !find)				//找相邻可走方块(i1,j1)
		{
			di++;
			switch (di)
			{
			case 0:i1 = i - 1; j1 = j;   break;
			case 1:i1 = i;   j1 = j + 1; break;
			case 2:i1 = i + 1; j1 = j;   break;
			case 3:i1 = i;   j1 = j - 1; break;
			}
			if (mg[i1][j1] == 0) find = true;	//找到一个相邻可走方块，设置find我真
		}
		if (find)							//找到了一个相邻可走方块(i1,j1)
		{

			St[top].di = di;		//修改原栈顶元素的di值
			
			top++;
			St[top].i = i1;
			St[top].j = j1;
			St[top].di = -1;

			mg[i1][j1] = -1;					//(i1,j1)的迷宫值置为-1避免重复走到该方块
		}
		else								//没有路径可走,则退栈
		{
			mg[i][j] = 0;//让退栈方块的位置变为其他路径可走方块
			top--;
		}
	}
	dispminpath();
}
int main()
{
	printf("所有路径如下:\n");
	mgpath(1, 1, M, N);
	return 0;
}

7.栈实现中缀转后缀表达式：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define Maxsize 100

typedef char ElemType;

typedef struct
{
	ElemType data[Maxsize];
	int top;
}SqStack;

//初始化
void InitStack(SqStack** s)
{
	*s = (SqStack*)malloc(sizeof(SqStack));
	(*s)->top = -1;
}

//销毁
void destroyStack(SqStack** s)
{
	free(*s);
	*s = NULL;
}

//判断栈空
bool StackEmpty(SqStack* s)
{
	if (s->top == -1)
	{
		return true;
	}
	else
	{
		return false;
	}
}

//进栈
bool Push(SqStack** s, ElemType e)
{
	if ((*s)->top == Maxsize - 1)
	{
		return false;
	}

	(*s)->top++;
	(*s)->data[(*s)->top] = e;
	return true;
}

//出栈
bool Pop(SqStack** s, ElemType* e)
{
	if ((*s)->top == -1)
	{
		return false;
	}

	*e = (*s)->data[(*s)->top];
	(*s)->top--;

	return true;
}

bool GetTop(SqStack* s, ElemType* e)
{
	if (s->top == -1)
	{
		return false;
	}

	*e = s->data[s->top];


	return true;
}


void trans(ElemType* exp, ElemType postexp[])	//将算术表达式exp转换成后缀表达式postexp
{
	ElemType e;
	SqStack* Optr;						//定义运算符栈
	InitStack(&Optr);					//初始化运算符栈

	int i = 0;							//i作为postexp的下标
	while (*exp != '\0')					//exp表达式未扫描完时循环
	{
		switch (*exp)
		{
		case '(':						//判定为左括号
			Push(&Optr, '(');				//左括号进栈
			exp++;						//继续扫描其他字符
			break;
		case ')':						//判定为右括号
			Pop(&Optr, &e);				//出栈元素e
			while (e != '(')				//不为'('时循环
			{
				postexp[i++] = e;			//将e存放到postexp中
				Pop(&Optr, &e);			//继续出栈元素e
			}
			exp++;						//继续扫描其他字符
			break;
		case '+':						//判定为加或减号
		case '-':
			while (!StackEmpty(Optr))	//栈不空循环
			{
				GetTop(Optr, &e);			//取栈顶元素e
				if (e != '(')				//e不是'('
				{
					postexp[i++] = e;		//将e存放到postexp中
					Pop(&Optr, &e);		//出栈元素e
				}
				else					//e是'(时退出循环
					break;
			}
			Push(&Optr, *exp);			//将'+'或'-'进栈
			exp++;						//继续扫描其他字符
			break;
		case '*':						//判定为'*'或'/'号
		case '/':
			while (!StackEmpty(Optr))	//栈不空循环
			{
				GetTop(Optr, &e);			//取栈顶元素e
				if (e == '*' || e == '/')	//将栈顶'*'或'/'运算符出栈并存放到postexp中
				{
					postexp[i++] = e;		//将e存放到postexp中
					Pop(&Optr, &e);		//出栈元素e
				}
				else					//e为非'*'或'/'运算符时退出循环
					break;
			}
			Push(&Optr, *exp);			//将'*'或'/'进栈
			exp++;						//继续扫描其他字符
			break;
		default:				//处理数字字符
			while (*exp >= '0' && *exp <= '9') //判定为数字
			{
				postexp[i++] = *exp;
				exp++;
			}
			postexp[i++] = '#';	//用#标识一个数值串结束
		}
	}
	while (!StackEmpty(Optr))	//此时exp扫描完毕,栈不空时循环
	{
		Pop(&Optr, &e);			//出栈元素e
		postexp[i++] = e;			//将e存放到postexp中
	}
	postexp[i] = '\0';			//给postexp表达式添加结束标识
	destroyStack(&Optr);			//销毁栈		
}



typedef struct
{
	double data[Maxsize];			//存放数值
	int top;						//栈顶指针
} SqStack1;

void InitStack1(SqStack1** s)		//初始化栈
{
	*s = (SqStack1*)malloc(sizeof(SqStack1));
	(*s)->top = -1;
}

void DestroyStack1(SqStack1** s)	//销毁栈
{
	free(*s);
}

bool StackEmpty1(SqStack1* s)		//判断栈是否为空
{
	return(s->top == -1);
}
bool Push1(SqStack1* s, double e)	//进栈元素e
{
	if (s->top == Maxsize - 1)
		return false;
	s->top++;
	s->data[s->top] = e;
	return true;
}

bool Pop1(SqStack1** s, double* e)	//出栈元素e
{
	if ((*s)->top == -1)
		return false;
	*e = (*s)->data[(*s)->top];
	(*s)->top--;
	return true;
}

bool GetTop1(SqStack1* s, double* e)	//取栈顶元素e
{
	if (s->top == -1)
		return false;
	*e = s->data[s->top];
	return true;
}



double compvalue(char* postexp)	//计算后缀表达式的值
{
	double d, a, b, c, e;
	SqStack1* Opnd;				//定义操作数栈
	InitStack1(&Opnd);			//初始化操作数栈
	while (*postexp != '\0')		//postexp字符串未扫描完时循环
	{
		switch (*postexp)
		{
		case '+':				//判定为'+'号
			Pop1(&Opnd, &a);		//出栈元素a
			Pop1(&Opnd, &b);		//出栈元素b
			c = b + a;				//计算c
			Push1(Opnd, c);		//将计算结果c进栈
			break;
		case '-':				//判定为'-'号
			Pop1(&Opnd, &a);		//出栈元素a
			Pop1(&Opnd, &b);		//出栈元素b
			c = b - a;				//计算c
			Push1(Opnd, c);		//将计算结果c进栈
			break;
		case '*':				//判定为'*'号
			Pop1(&Opnd, &a);		//出栈元素a
			Pop1(&Opnd, &b);		//出栈元素b
			c = b * a;				//计算c
			Push1(Opnd, c);		//将计算结果c进栈
			break;
		case '/':				//判定为'/'号
			Pop1(&Opnd, &a);		//出栈元素a
			Pop1(&Opnd, &b);		//出栈元素b
			if (a != 0)
			{
				c = b / a;			//计算c
				Push1(Opnd, c);	//将计算结果c进栈
				break;
			}
			else
			{
				printf("\n\t除零错误!\n");
				exit(0);		//异常退出
			}
			break;
		default:				//处理数字字符
			d = 0;				//将连续的数字字符转换成对应的数值存放到d中
			while (*postexp >= '0' && *postexp <= '9')   //判定为数字字符
			{
				d = 10 * d + *postexp - '0';
				postexp++;
			}
			Push1(Opnd, d);		//将数值d进栈

			break;
		}
		postexp++;				//继续处理其他字符
	}
	GetTop1(Opnd, &e);			//取栈顶元素e
	DestroyStack1(&Opnd);		//销毁栈		
	return e;					//返回e
}

int main()
{
	char exp[] = "(56-20)/(4+2)";
	char postexp[Maxsize];
	trans(exp, postexp);
	printf("中缀表达式:%s\n", exp);
	printf("后缀表达式:%s\n", postexp);
	printf("表达式的值:%g\n", compvalue(postexp));
	return 0;
}