栈和队列.zip

#include<stdio.h> #include<stdlib.h> typedef struct LinkNode//链式队列节点 { int data;//数据域 struct LinkNode *next;//指针域 }LinkNode; typedef struct//链式队列 { LinkNode *front, *rear;//队列的队头指针和队尾指针 }LinkQueue; void InitQueue(LinkQueue &Q)//初始化 { Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode)); Q.front->next = NULL;//让队头指针指向空指针 } bool EnQueue(LinkQueue &Q)//入队 { char a; printf("是否进行入队操作（Y/N）："); getchar(); scanf("%c", &a); if (a == 'N') { printf("入队失败\n"); return false; } int b; printf("请输入要入队的元素个数："); scanf("%d", &b); for (int i = 0; i < b;i++)//用循环进行多次入队操作 { int x; printf("请输入要入队的元素（一次输入一个数字）："); scanf("%d", &x); LinkNode *s = (LinkNode*)malloc(sizeof(LinkNode));//用malloc函数申请空间给新的节点s if (s == NULL) { printf("入队失败\n"); return false; } s->data = x;//把输入的数放进新节点 s->next = NULL;//让新节点指向空指针 Q.rear->next = s;//新节点插入到rear后 Q.rear = s;//修改表尾指针 printf("入队成功，入队的元素是：%d\n", x); } return true; } bool DeQueue(LinkQueue &Q)//出队 { char a; printf("是否进行出队操作（Y/N）："); getchar(); scanf("%c", &a); if (a == 'N') { printf("出队失败\n"); return false; } if (Q.rear == Q.front)//判断是否空队 return false; LinkNode *p = Q.front->next;//新建一个指针指向出队元素所在的那个节点 int x = p->data;//把队首元素的值放入x中 printf("出队的元素是：%d\n", x); Q.front->next = p->next;//修改头节点的next指针 if (Q.rear == p)//此次是最后一个节点出队 Q.rear = Q.front;//修改rear指针 free(p);//释放指针p指向的元素所在的节点空间 return true; } bool FrontQueue(LinkQueue &Q)//取队首元素 { if (Q.rear == Q.front) { printf("空队，无队头元素\n"); return false; } printf("队头元素是：%d\n", Q.front->next->data);//打印队头指针指向的下一个节点的元素值 return true; } bool EmptQueue(LinkQueue &Q)//判空 { if (Q.rear == Q.front) { printf("空队列\n"); return true; } else printf("不是空队列\n"); return false; } bool Print(LinkQueue &Q)//输出队列元素 { if (Q.front == Q.rear)//判空 { printf("队列为空\n"); return false; } LinkNode *p = Q.front->next;//新建一个指针指向队首元素所在的节点 printf("队列的元素是："); while (1) { printf("%d ", p->data); if (p == Q.rear)//判断p是否指向队尾节点 { printf("\n"); return true; } p = p->next;//节点p指向下一个节点 } } bool DeleQueue(LinkQueue &Q)//销毁队列 { char a; printf("是否销毁队列（Y/N）："); getchar(); scanf("%c", &a); if (a == 'N') { printf("队列销毁失败\n"); return false; } LinkNode *p, *q;//新建两个指针 p = Q.front;//指针p指向头节点 while (p != NULL)//当头结点的指针域不为0，即不是链尾时 { q = p->next;//让q指向头结点的后续结点 free(p);//把p指针指向的节点空间释放了，但是p指针还存在。 p = q;//让p和q都指向后续结点，此时p和q指针指向的都是下一个节点，接下来重复这一段的操作就好了。 } Q.rear = Q.front;//让队头指针和队尾指针都指向头节点 printf("队列销毁成功\n"); return true; } int main() { LinkQueue Q; InitQueue(Q);//初始化 EnQueue(Q);//入队 FrontQueue(Q);//取队头元素 Print(Q);//输出队列所有元素 DeQueue(Q);//出队 Print(Q);//输出队列所有元素 EmptQueue(Q);//判空 DeleQueue(Q);//销毁队列 Print(Q);//输出队列所有元素 return 0; }