目录
一、栈系列基础8道题
1.顺序栈的建立
1.定义顺序栈的存储结构
2.初始化顺序栈为空栈（InitStack_Sq）
3.输入要入栈的元素个数n
4.向顺序栈中压入n个元素（Push_Sq）
5.将顺序栈中的元素从栈顶到栈底依次输出（StackTraverse_Sq）
6.销毁顺序栈（DestroyStack_Sq）
例如：
5
4 3 5 10 9
9 10 5 3 4 //遍历输出时最后一个元素后有一个空格
#include <stdio.h> #include <stdlib.h> #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status; typedef int SElemType; #define MAXSIZE 100 typedef struct { SElemType *base; SElemType *top; int stacksize; }SqStack; Status InitStack_Sq(SqStack *S) { S->base=(int*)malloc (sizeof(int)*MAXSIZE); if(!S->base) exit(OVERFLOW); S->top=S->base; S->stacksize=MAXSIZE; return OK; } void DestroyStack_Sq(SqStack *S) { if(S->base) free(S->base); S->top=S->base=NULL; } //在此处定义入栈函数Push_Sq int Push_Sq(SqStack *S,int n) { for(int i=0;i<n;i++) { int e; scanf("%d",&e); *S->top=e; S->top++; } } void StackTraverse_Sq(SqStack *S,int n) { for(int i=0;i<n;i++) { S->top--; printf("%d ",*S->top); } } int main() { SqStack S; InitStack_Sq(&S); int n; SElemType e; scanf("%d",&n); Push_Sq(&S,n); StackTraverse_Sq(&S,n); DestroyStack_Sq(&S); return 0; }
2.顺序栈的入栈
1.定义顺序栈入栈函数（Push_Sq）
2.输入要入栈的元素个数n
3.向顺序栈中压入n个元素
4.将顺序栈中的元素从栈顶到栈底依次输出（StackTraverse_Sq）
5.销毁顺序栈（DestroyStack_Sq）
例如：
5
6 2 8 10 9
9 10 8 2 6 //遍历输出时最后一个元素后有一个空格
#include <stdio.h> #include <stdlib.h> #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status; typedef int SElemType; #define MAXSIZE 100 typedef struct { SElemType *base; SElemType *top; int stacksize; }SqStack; Status InitStack_Sq(SqStack *S) { S->base=(int*)malloc (sizeof(int)*MAXSIZE); if(!S->base) exit(OVERFLOW); S->top=S->base; S->stacksize=MAXSIZE; return OK; } void DestroyStack_Sq(SqStack *S) { if(S->base) free(S->base); S->top=S->base=NULL; } //在此处定义入栈函数Push_Sq int Push_Sq(SqStack *S,int n) { for(int i=0;i<n;i++) { int e; scanf("%d",&e); *S->top=e; S->top++; } } void StackTraverse_Sq(SqStack *S,int n) { for(int i=0;i<n;i++) { S->top--; printf("%d ",*S->top); } } int main() { SqStack S; InitStack_Sq(&S); int n; SElemType e; scanf("%d",&n); Push_Sq(&S,n); StackTraverse_Sq(&S,n); DestroyStack_Sq(&S); return 0; }
3.顺序栈的出栈
1.定义顺序栈出栈函数（Pop_Sq）
2.定义求顺序栈栈长函数（StackLength_Sq）
3.输入要入栈的元素个数n
4.向顺序栈中压入n个元素
5.将顺序栈中的元素从栈顶到栈底依次输出（StackTraverse_Sq）
6.销毁顺序栈（DestroyStack_Sq）
例如：
4
2 4 6 8
8 6 4 2 //遍历输出时最后一个元素后有一个空格
4
6 4 2 //遍历输出时最后一个元素后有一个空格
8
3
#include <stdio.h> #include <stdlib.h> #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status; typedef int SElemType; #define MAXSIZE 100 typedef struct { SElemType *base; SElemType *top; int stacksize; }SqStack ; Status InitStack_Sq(SqStack *S) { S->base=(SElemType*) malloc (sizeof(int)*MAXSIZE); if(!S->base) exit(OVERFLOW); S->top=S->base; S->stacksize=MAXSIZE; return OK; } void DestroyStack_Sq(SqStack *S) { if(S->base) free (S->base); S->top=S->base=NULL; } //此处定义求栈长函数StackLength_Sq void StackLength_Sq(SqStack *S) { if(S->top==S->base) { exit(0); } int y=S->top-S->base; printf("%d ",y); } Status Push_Sq(SqStack *S,SElemType e) { if(S->top-S->base==S->stacksize) return ERROR; *S->top++=e; return OK; } //此处定义出栈函数 int Pop_Sq(SqStack* S) { int e; S->top--; e=*S->top; //printf("%d ",e); return e; } void StackTraverse_Sq(SqStack *S,int n) { int e; int *p=S->top; for(int i=0;i<n;i++) { S->top--; e=*S->top; printf("%d ",e); } S->top=p; } SqStack* yazhan(SqStack *S,int n) { int u; for(int i=0;i<n;i++) { scanf("%d",&u); *S->top++=u; } return S; } int main() { SqStack S; SElemType e; InitStack_Sq(&S); int n; //SElemType y; scanf("%d",&n); yazhan(&S,n); StackTraverse_Sq(&S,n); printf("\n"); StackLength_Sq(&S); printf("\n"); e=Pop_Sq(&S); StackTraverse_Sq(&S,S.top-S.base); printf("\n"); printf("%d",e); printf("\n"); StackLength_Sq(&S); return 0; }
4.顺序栈栈顶元素的获取
1.定义获取顺序栈栈顶元素函数（GetTop_Sq）
2.输入要入栈的元素个数n
3.向顺序栈中压入n个元素
4.将顺序栈中的元素从栈顶到栈底依次输出（StackTraverse_Sq）
5.获取栈顶元素
6.输出栈顶元素
7.销毁顺序栈（DestroyStack_Sq）
例如：
4
2 4 6 8
8 6 4 2 //遍历输出时最后一个元素后有一个空格
8
/*1.定义获取顺序栈栈顶元素函数（GetTop_Sq） 2.输入要入栈的元素个数n 3.向顺序栈中压入n个元素 4.将顺序栈中的元素从栈顶到栈底依次输出（StackTraverse_Sq） 5.获取栈顶元素 6.输出栈顶元素 7.销毁顺序栈（DestroyStack_Sq） 例如： 4 2 4 6 8 8 6 4 2 //遍历输出时最后一个元素后有一个空格 8*/ #include <stdio.h> # include <stdlib.h> #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status; typedef int SElemType; #define MAXSIZE 100 typedef struct { SElemType *base; SElemType *top; int stacksize; }SqStack; Status InitStack_Sq(SqStack *S) { S->base=(int *) malloc (sizeof(int)*MAXSIZE); if(!S->base) exit(OVERFLOW); S->top=S->base; S->stacksize=MAXSIZE; return OK; } void DestroyStack_Sq(SqStack *S) { if(S->base) free(S->base); S->top=S->base=NULL; } //此处定义获取栈顶元素函数GetTop_Sq int GetTop_Sq(SqStack *S) { int *p=S->top; int y; S->top--; y=*S->top; S->top=p; return y; } Status Push_Sq(SqStack *S,SElemType e) { if(S->top-S->base==S->stacksize) return ERROR; *S->top++=e; return OK; } void StackTraverse_Sq(SqStack* S,int n) { int w; int *p; p=S->top; for(int i=0;i<n;i++) { S->top--; w=*S->top; printf("%d ",w); } S->top=p; printf("\n"); } SqStack * shuru(SqStack *S,int n) { int y; for(int i=0;i<n;i++) { scanf("%d",&y); *S->top++=y; } return S; } int main() { SqStack S; SElemType e; InitStack_Sq(&S); int n; scanf("%d",&n); S=*shuru(&S,n); // printf("\n"); StackTraverse_Sq(&S,n); //此处调用获取栈顶元素函数，将其存储在参数e中 e=GetTop_Sq(&S); printf("%d ",e); return 0; }
5.链栈的建立
1.定义链栈的结点存储结构
2.初始化链栈为空栈（InitStack_Link）
3.输入要入栈的元素个数n
4.向链栈中压入n个元素（Push_Link）
5.从栈顶到栈底遍历链栈数据（StackTraverse_Link）
6.销毁链栈（DestroyStack_Link）
例如：
5
4 3 5 10 9
9 10 5 3 4 //遍历输出时最后一个元素后有一个空格
# include<stdio.h> # include <stdlib.h> typedef struct Lstack { int data; struct Lstack *next; }Lstack,*LinkStack; int InitStack_Link(LinkStack S) { S=NULL; return 1; } void StackTraverse_Link(LinkStack S) { //int i=0; LinkStack p=S; while(p) { // i++; printf("%d ",p->data); p=p->next; } } LinkStack Push_Link(LinkStack S,int n) { int y; LinkStack p; for(int i=0;i<n;i++) { if(i==0) { p=(LinkStack)malloc(sizeof(Lstack)); scanf("%d",&y); p->data=y; p->next=NULL; S=p; } else{ p=(LinkStack)malloc(sizeof(Lstack)); scanf("%d",&y); p->data=y; p->next=S; S=p; } } return S; } void DestroyStack_Link(LinkStack S) { LinkStack p=S; while(p){ S=S->next; free(p); p=S; }} int main() { LinkStack S; int n; InitStack_Link(S); scanf("%d",&n); S=Push_Link(S,n); StackTraverse_Link(S); printf("\n"); DestroyStack_Link(S); // printf("over"); return 0; }
6.链栈的入栈
1.定义链栈的入栈函数（Push_Link）
2.输入要入栈的元素个数n
3.向顺序栈中压入n个元素
4.将链栈中的元素从栈顶到栈底依次输出（StackTraverse_Link）
5.销毁链栈栈（DestroyStack_Link）
例如：
5
1 2 3 4 5
5 4 3 2 1 //遍历输出时最后一个元素后有一个空格
/*1.定义链栈的入栈函数（Push_Link） 2.输入要入栈的元素个数n 3.向顺序栈中压入n个元素 4.将链栈中的元素从栈顶到栈底依次输出（StackTraverse_Link） 5.销毁链栈栈（DestroyStack_Link） 例如： 5 1 2 3 4 5 5 4 3 2 1 //遍历输出时最后一个元素后有一个空格*/ # include <stdio.h> # include <stdlib.h> #define MAXSIZE 100 typedef struct StackNode { int data; struct StackNode *next; }StackNode,*LinkStack; int Initstack(LinkStack S) { S=NULL; return 1; } LinkStack Push_Link(LinkStack S,int n) { int y; LinkStack p; for(int i=0;i<n;i++) { if(i==0) { p=(LinkStack)malloc(sizeof(StackNode)); scanf("%d",&y); p->data=y; p->next=NULL; S=p; } else{ p=(LinkStack)malloc(sizeof(StackNode)); scanf("%d",&y); p->data=y; p->next=S; S=p; } } return S; } void StackTraverse_Link(LinkStack S,int n) { LinkStack p=S; for(int i=0;i<n;i++) { printf("%d ",p->data); p=p->next; } } void DestroyStack_Link(LinkStack S) { LinkStack p=S; while(p){ S=S->next; free(p); p=S; }} int main() { LinkStack S; Initstack(S); int n; scanf("%d",&n); S=Push_Link(S,n); StackTraverse_Link(S,n); // DestroyStack_Link(S); return 0; }
7.链栈的出栈
1.定义求栈长函数（StackLength_Link）
2.定义出栈函数（Pop_Link）
3.输入要入栈的元素个数n
4.向顺序栈中压入n个元素（Push_Link）
5.将顺序栈中的元素从栈顶到栈底依次输出（StackTraverse_Link）
6.输出栈长
7.执行出栈操作
8.将顺序栈中的元素从栈顶到栈底依次输出
9.输出出栈元素
10.输出栈长
11.销毁链栈（DestroyStack_Link）
例如：
5
1 2 3 4 5
5 4 3 2 1 //遍历输出时最后一个元素后有一个空格
5
4 3 2 1 //遍历输出时最后一个元素后有一个空格
5
4
# include<stdio.h> # include <stdlib.h> typedef struct Lstack { int data; struct Lstack *next; }Lstack,*LinkStack; int Init_S(LinkStack S) { S=NULL; return 1; } int StackLength_Link(LinkStack S) { int i=0; LinkStack p = S; while (p){ if(p->next!=NULL) {i++; p = p->next; } else { i++; return i; } } } void StackTraverse_Link(LinkStack S) { //int i=0; LinkStack p=S; while(p) { // i++; printf("%d ",p->data); p=p->next; } } LinkStack Push_Link(LinkStack S,int n) { int y; LinkStack p; for(int i=0;i<n;i++) { if(i==0) { p=(LinkStack)malloc(sizeof(Lstack)); scanf("%d",&y); p->data=y; p->next=NULL; S=p; } else{ p=(LinkStack)malloc(sizeof(Lstack)); scanf("%d",&y); p->data=y; p->next=S; S=p; } } return S; } void DestroyStack_Link(LinkStack S) { LinkStack p=S; while(p){ S=S->next; free(p); p=S; } } LinkStack Pop_Link(LinkStack S,int * e) { LinkStack p=S; S=S->next; *e=p->data; return S; } int main() { LinkStack S; int n; scanf("%d",&n); S=Push_Link(S,n); StackTraverse_Link(S); printf("\n"); int y; y=StackLength_Link(S); printf("%d\n",y); int r; S=Pop_Link(S,&r); StackTraverse_Link(S); printf("\n"); printf("%d",r); printf("\n"); y=StackLength_Link(S); printf("%d\n",y); DestroyStack_Link(S); return 0; }
8.链栈栈顶元素的获取
1.定义获取栈顶元素函数（GetTop_Link）
2.输入要入栈的元素个数n
3.向顺序栈中压入n个元素（Push_Link）
4.将顺序栈中的元素从栈底到栈顶依次输出（StackTraverse_Link）
5.获取栈顶元素
6.输出栈顶元素
7.销毁链栈（DestroyStack_Link）
例如：
4
2 4 6 8
8 6 4 2 //遍历输出时最后一个元素后有一个空格
8
# include<stdio.h> # include <stdlib.h> typedef struct Lstack { int data; struct Lstack *next; }Lstack,*LinkStack; int Init_S(LinkStack S) { S=NULL; return 1; } void StackTraverse_Link(LinkStack S) { //int i=0; LinkStack p=S; while(p) { // i++; printf("%d ",p->data); p=p->next; } } LinkStack Push_Link(LinkStack S,int n) { int y; LinkStack p; for(int i=0;i<n;i++) { if(i==0) { p=(LinkStack)malloc(sizeof(Lstack)); scanf("%d",&y); p->data=y; p->next=NULL; S=p; } else{ p=(LinkStack)malloc(sizeof(Lstack)); scanf("%d",&y); p->data=y; p->next=S; S=p; } } return S; } void DestroyStack_Link(LinkStack S) { LinkStack p=S; while(p){ S=S->next; free(p); p=S; } } LinkStack GetTop_Link(LinkStack S,int * e) { LinkStack p=S; *e=p->data; return S; } int main() { LinkStack S; Init_S(S); int n; scanf("%d",&n); S=Push_Link(S,n); StackTraverse_Link(S); printf("\n"); int e; GetTop_Link(S,&e); printf("%d",e); DestroyStack_Link(S); return 0; }
二、队列系列基础8道题
1.循环队列的建立
1.定义循环队列的存储结构
2.初始化循环队列为空队列（InitQueue_Sq）
3.输入要入队的元素个数n
4.向循环队列中输入n个元素（EnQueue_Sq）
5.将循环队列中的元素从队头至队尾依次输出（StackQueue_Sq）
6.销毁循环队列（DestroyQueue_Sq）
例如：
5
1 2 3 4 5
1 2 3 4 5 //遍历输出时最后一个元素后有一个空格
/*1.定义循环队列的存储结构 2.初始化循环队列为空队列（InitQueue_Sq） 3.输入要入队的元素个数n 4.向循环队列中输入n个元素（EnQueue_Sq） 5.将循环队列中的元素从队头至队尾依次输出（StackQueue_Sq） 6.销毁循环队列（DestroyQueue_Sq） 例如： 5 1 2 3 4 5 1 2 3 4 5 //遍历输出时最后一个元素后有一个空格 */ # include <stdio.h> # include <stdlib.h> # define MAXSIZE 100 typedef struct Sq{ int *base; int tou; int wei; }Sq; int InitQueue_Sq(Sq *sq) { sq->base=(int *)malloc (sizeof(int)*MAXSIZE); sq->tou=sq->wei=0; return 1; } Sq* EnQueue_Sq(Sq *sq,int n) { if((sq->wei+1)%MAXSIZE==sq->tou) exit(0); // printf("ffff"); int e; for(int i=0;i<n;i++) { scanf("%d",&e); sq->base[sq->wei]=e; sq->wei=(sq->wei+1)%MAXSIZE; } return sq; } void StackQueue_Sq(Sq *sq) { while(sq->tou!=sq->wei) { printf("%d ",sq->base[sq->tou]); sq->tou=(sq->tou+1)%MAXSIZE; }} void DestroyQueue_Sq(Sq *sq) { if (sq->base) free(sq->base); sq->base = NULL; sq->tou = sq->wei = 0; //printf("ppp"); } int main() { Sq sq; InitQueue_Sq(&sq); int n; scanf("%d",&n); EnQueue_Sq(&sq,n); StackQueue_Sq(&sq); DestroyQueue_Sq(&sq); return 0; }
2.循环队列的入队
1.定义循环队列入队函数（EnQueue_Sq）
2.输入要入队的元素个数n
3.向循环队列中输入n个元素
4.将循环队列中的元素从队头至队尾依次输出（StackQueue_Sq）
5.销毁循环队列（DestroyQueue_Sq）
例如：
5
6 2 8 10 9
6 2 8 10 9 //遍历输出时最后一个元素后有一个空格
/*1.定义循环队列入队函数（EnQueue_Sq） 2.输入要入队的元素个数n 3.向循环队列中输入n个元素 4.将循环队列中的元素从队头至队尾依次输出（StackQueue_Sq） 5.销毁循环队列（DestroyQueue_Sq） 例如： 5 6 2 8 10 9 6 2 8 10 9 //遍历输出时最后一个元素后有一个空格 */ # include <stdio.h> # include <stdlib.h> # define MAXSIZE 100 typedef struct SQQ{ int *base; int tou; int wei; }SQQ; int Init_sqq(SQQ*sqq) { sqq->base=(int *)malloc (sizeof(int)*MAXSIZE); sqq->tou=sqq->wei=0; return 1; } SQQ* EnQueue_Sq(SQQ *sqq,int n) { int y; if((sqq->wei+1)%MAXSIZE==sqq->tou) exit(0); for(int i=0;i<n;i++) { scanf("%d",&y); sqq->base[sqq->wei]=y; sqq->wei=(sqq->wei+1)%MAXSIZE; } return sqq; } void StackQueue_Sq(SQQ *sqq) { while(sqq->tou!=sqq->wei) { printf("%d ",sqq->base[sqq->tou]); sqq->tou=(sqq->tou+1)%MAXSIZE; } } void DestroyQueue_Sq(SQQ *sqq) { if(sqq->base) free(sqq->base); sqq->base=NULL; sqq->tou=sqq->wei=0; } int main() { SQQ sqq; int n; scanf("%d",&n); Init_sqq(&sqq); EnQueue_Sq(&sqq,n); //printf("pppp"); StackQueue_Sq(&sqq); DestroyQueue_Sq(&sqq); return 0; }
3.循环队列的出队
1.定义顺序栈出栈函数（Pop_Sq）
2.定义求顺序栈栈长函数（StackLength_Sq）
3.输入要入栈的元素个数n
4.向顺序栈中压入n个元素
5.将顺序栈中的元素从栈顶到栈底依次输出（StackTraverse_Sq）
6.销毁顺序栈（DestroyStack_Sq）
例如：
4
2 4 6 8
8 6 4 2 //遍历输出时最后一个元素后有一个空格
4
6 4 2 //遍历输出时最后一个元素后有一个空格
8
3
#include <stdio.h> #include <stdlib.h> #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status; typedef int SElemType; #define MAXSIZE 100 typedef struct { SElemType *base; SElemType *top; int stacksize; }SqStack ; Status InitStack_Sq(SqStack *S) { S->base=(SElemType*) malloc (sizeof(int)*MAXSIZE); if(!S->base) exit(OVERFLOW); S->top=S->base; S->stacksize=MAXSIZE; return OK; } void DestroyStack_Sq(SqStack *S) { if(S->base) free (S->base); S->top=S->base=NULL; } //此处定义求栈长函数StackLength_Sq void StackLength_Sq(SqStack *S) { if(S->top==S->base) { exit(0); } int y=S->top-S->base; printf("%d ",y); } Status Push_Sq(SqStack *S,SElemType e) { if(S->top-S->base==S->stacksize) return ERROR; *S->top++=e; return OK; } //此处定义出栈函数 int Pop_Sq(SqStack* S) { int e; S->top--; e=*S->top; //printf("%d ",e); return e; } void StackTraverse_Sq(SqStack *S,int n) { int e; int *p=S->top; for(int i=0;i<n;i++) { S->top--; e=*S->top; printf("%d ",e); } S->top=p; } SqStack* yazhan(SqStack *S,int n) { int u; for(int i=0;i<n;i++) { scanf("%d",&u); *S->top++=u; } return S; } int main() { SqStack S; SElemType e; InitStack_Sq(&S); int n; //SElemType y; scanf("%d",&n); yazhan(&S,n); StackTraverse_Sq(&S,n); printf("\n"); StackLength_Sq(&S); printf("\n"); e=Pop_Sq(&S); StackTraverse_Sq(&S,S.top-S.base); printf("\n"); printf("%d",e); printf("\n"); StackLength_Sq(&S); return 0; }
4.循环队列队头元素的获取
1.定义获取循环队列队头元素函数（GetHead_Sq）
2.输入要入队的元素个数n
3.向循环队列中输入n个元素
4.将循环队列中的元素从队头至队尾依次输出
5.获取栈顶元素
6.将循环队列中的元素从队头至队尾依次输出
7.销毁循环队列
例如：
5
2 4 6 8 10
2 4 6 8 10 //遍历输出时最后一个元素后有一个空格
2
/*1.定义获取循环队列队头元素函数（GetHead_Sq） 2.输入要入队的元素个数n 3.向循环队列中输入n个元素 4.将循环队列中的元素从队头至队尾依次输出 5.获取栈顶元素 6.将循环队列中的元素从队头至队尾依次输出 7.销毁循环队列 例如： 5 2 4 6 8 10 2 4 6 8 10 //遍历输出时最后一个元素后有一个空格 2*/ # include <stdio.h> # include <stdlib.h> # define MAXSIZE 100 typedef struct SQQ{ int *base; int tou; int wei; }SQQ; int Init_sq(SQQ *sqq) { sqq->base=(int *)malloc (sizeof(int)*MAXSIZE); sqq->tou=sqq->wei=0; return 1; } SQQ*shuru(SQQ*sqq,int n) {int y; for(int i=0;i<n;i++) { scanf("%d",&y); sqq->base[sqq->wei]=y; sqq->wei=(sqq->wei+1)%MAXSIZE; } return sqq; } void shuchu(SQQ *sqq) { int q=sqq->tou; while(sqq->tou!=sqq->wei) { printf("%d ",sqq->base[sqq->tou]); sqq->tou=(sqq->tou+1)%MAXSIZE; } sqq->tou=q; } int GetHead_Sq(SQQ *sqq) { return sqq->base[sqq->tou]; } void DestroyQueue_Sq(SQQ *sqq) { if(sqq->base) free(sqq->base); sqq->base=NULL; sqq->tou=sqq->wei=0; } int main() { SQQ sqq; int n; scanf("%d",&n); Init_sq(&sqq); shuru(&sqq,n); shuchu(&sqq); int y; y=GetHead_Sq(&sqq); printf("\n"); printf("%d",y); DestroyQueue_Sq(&sqq); return 0; }
5.链队列的建立
1.定义链队列的存储结构
2.初始化链队列为空队列（InitQueue_Link）
3.输入要入队的元素个数n
4.向链队列中输入n个元素（EnQueue_Link）
5.将链队列中的元素从队头至队尾依次输出（StackQueue_Link）
6.销毁链队列（DestroyQueue_Link）
例如：
5
1 2 3 4 5
1 2 3 4 5 //遍历输出时最后一个元素后有一个空格
# include <stdio.h> # include <stdlib.h> typedef struct QNode { int data; struct QNode *next; }QNode,*QueuePtr; typedef struct { QueuePtr front; QueuePtr rear; }LinkQueue; int InitQueue_Link(LinkQueue*Q){ Q->front=Q->rear=(QueuePtr) malloc (sizeof(QNode)); Q->front->next=NULL; return 1; } LinkQueue * EnQueue_Link(LinkQueue*Q,int n) { QueuePtr p; int y; for(int i=0;i<n;i++) { if(i==0) { p=(QueuePtr)malloc(sizeof(QNode)); scanf("%d",&y); p->data=y; p->next=NULL; Q->front=Q->rear=p; } else{ p=(QueuePtr)malloc(sizeof(QNode)); scanf("%d",&y); p->data=y; p->next=NULL; Q->rear->next=p; // Q->rear=p; Q->rear=p; } } return Q; } void StackQueue_Link(LinkQueue Q) { QueuePtr q=Q.front;//结构体类型 //printf("iiiiiii"); while(Q.front!=NULL) { printf("%d ",Q.front->data); Q.front=Q.front->next; q=Q.front; } Q.front=q; } void DestroyQueue_Link(LinkQueue *sq) { QueuePtr q;// 节点指针类型 while(sq->front!=NULL) { q=sq->front; free(q); sq->front=sq->rear->next; } // printf("iii"); } //front rear 是单独开辟一个空间 指向 不在链表中 int main() { LinkQueue sq; int n; scanf("%d",&n); EnQueue_Link(&sq,n); //printf("ooo"); StackQueue_Link(sq); DestroyQueue_Link(&sq); return 0; }
6.链队列的入队
1.定义循环队列入队函数（EnQueue_Sq）
2.输入要入队的元素个数n
3.向循环队列中输入n个元素
4.将循环队列中的元素从队头至队尾依次输出（StackQueue_Sq）
5.销毁循环队列（DestroyQueue_Sq）
例如：
5
6 2 8 10 9
6 2 8 10 9 //遍历输出时最后一个元素后有一个空格
# include <stdio.h> # include <stdlib.h> # define MAXSIZE 100 typedef struct SQQ{ int *base; int tou; int wei; }SQQ; int Init_sqq(SQQ*sqq) { sqq->base=(int *)malloc (sizeof(int)*MAXSIZE); sqq->tou=sqq->wei=0; return 1; } SQQ* EnQueue_Sq(SQQ *sqq,int n) { int y; if((sqq->wei+1)%MAXSIZE==sqq->tou) exit(0); for(int i=0;i<n;i++) { scanf("%d",&y); sqq->base[sqq->wei]=y; sqq->wei=(sqq->wei+1)%MAXSIZE; } return sqq; } void StackQueue_Sq(SQQ *sqq) { while(sqq->tou!=sqq->wei) { printf("%d ",sqq->base[sqq->tou]); sqq->tou=(sqq->tou+1)%MAXSIZE; } } void DestroyQueue_Sq(SQQ *sqq) { if(sqq->base) free(sqq->base); sqq->base=NULL; sqq->tou=sqq->wei=0; } int main() { SQQ sqq; int n; scanf("%d",&n); Init_sqq(&sqq); EnQueue_Sq(&sqq,n); //printf("pppp"); StackQueue_Sq(&sqq); DestroyQueue_Sq(&sqq); return 0; }
7.链队列的出队
1.定义求链队列队长函数（QueueLength_Link）
2.定义链队列的出队函数（DeQueue_Link）
3.输入要入队的元素个数n
4.向链队列中输入n个元素
5.将链队列中的元素从队头至队尾依次输出（StackQueue_Link）
6.输出队长
7.执行出队操作
8.将链队列中的元素从队头至队尾依次输出
9.输出出队元素
10.输出队长
11.销毁链队列（DestroyQueue_Link）
例如：
5
1 2 3 4 5
1 2 3 4 5 //遍历输出时最后一个元素后有一个空格
5
2 3 4 5 //遍历输出时最后一个元素后有一个空格
1
4
# include <stdio.h> # include <stdlib.h> typedef struct QNode{ int data; struct QNode *next; }QNode,*QueuePtr; typedef struct LinkQueue { QueuePtr front; QueuePtr rear; }LinkQueue; int InitQueue_Link(LinkQueue *Q) { Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode)); Q->front=NULL; return 1; } LinkQueue* EnQueue_Link(LinkQueue *Q,int n) { QueuePtr p; for(int i=0;i<n;i++) { p=(QueuePtr) malloc(sizeof(QNode)); scanf("%d",&p->data); p->next=NULL; if(i==0) { Q->front=Q->rear=p; } else { Q->rear->next=p; Q->rear=p; } } return Q; } void StackQueue_Link(LinkQueue *Q) { QueuePtr p=Q->front; while(Q->front!=NULL) { printf("%d ",Q->front->data); Q->front=Q->front->next; } Q->front=p; } int QueueLength_Link(LinkQueue *Q) { int y=0; QueuePtr p=Q->front; while(Q->front!=NULL) { y++; Q->front=Q->front->next; } Q->front=p; return y; } int DeQueue_Link(LinkQueue *Q){ int y; y=Q->front->data; Q->front=Q->front->next; return y ; } void DestroyQueue_Link(LinkQueue *Q) { QueuePtr p; while(Q->front!=NULL){ p=Q->front; Q->front=Q->front->next; free(p); } } int main() { int n; scanf("%d",&n); int y; LinkQueue Q; InitQueue_Link(&Q); EnQueue_Link(&Q,n); StackQueue_Link(&Q); printf("\n"); int x; x=QueueLength_Link(&Q); printf("%d ",x); printf("\n"); y=DeQueue_Link(&Q); StackQueue_Link(&Q); printf("\n"); printf("%d",y); printf("\n"); x=QueueLength_Link(&Q); printf("%d",x); DestroyQueue_Link(&Q); return 0; }
8.链队列队头元素的获取
1.定义获取链队列队头元素函数（GetHead_Link）
2.输入要入队的元素个数n
3.向链队列中输入n个元素
4.将链队列中的元素从队头至队尾依次输出
5.获取栈顶元素
6.将链队列中的元素从队头至队尾依次输出
7.销毁链队列
例如：
5
2 4 6 8 10
2 4 6 8 10 //遍历输出时最后一个元素后有一个空格
2
# include <stdio.h> # include <stdlib.h> typedef struct QNode{ int data; struct QNode *next; }QNode,*QueuePtr; typedef struct { QueuePtr front; QueuePtr rear; }LinkQueue; int InitQueue_Link(LinkQueue *Q) { Q->front=Q->rear=(QueuePtr) malloc(sizeof(QNode)); Q->front=NULL; return 1; } LinkQueue* EnQueue_Link(LinkQueue *Q,int n) { QueuePtr p; for(int i=0;i<n;i++) { p=(QueuePtr) malloc(sizeof(QNode)); scanf("%d",&p->data); p->next=NULL; if(i==0) { Q->front=Q->rear=p; } else { Q->rear->next=p; Q->rear=p; } } return Q; } void StackQueue_Link(LinkQueue *Q) { QueuePtr p=Q->front; while(Q->front!=NULL) { printf("%d ",Q->front->data); Q->front=Q->front->next; } Q->front=p; } int GetHead_Link(LinkQueue *Q){ int y; y=Q->front->data; printf("%d ",y); return 1; } void DestroyQueue_Link(LinkQueue *Q) { QueuePtr p; while(Q->front!=NULL) { p=Q->front; Q->front=Q->front->next; free(p); } // printf("成功调用"); } int main() { int n; scanf("%d",&n); LinkQueue Q; InitQueue_Link(&Q); EnQueue_Link(&Q,n); StackQueue_Link(&Q); printf("\n"); GetHead_Link(&Q); DestroyQueue_Link(&Q); return 0; }
三、栈与队列的应用
1.栈的应用
将十进制数n，转换成八进制。
例如：
10
12
# include <stdio.h> # include <stdlib.h> # define MAXSIZE 100 typedef struct { int *base; int *top; int stacksize; }SqStack; int InitStack_Sq(SqStack *S) { S->base=(int*)malloc (sizeof(int)*MAXSIZE); if(!S->base) exit(-1); S->top=S->base; S->stacksize=MAXSIZE; return 1; } SqStack* Push_Sq(SqStack * S,int x) { *S->top=x; S->top++; return S; } void StackTraverse_Sq(SqStack *S) { while(S->top!=S->base) { S->top--; printf("%d",*S->top); } } int main() { SqStack S; InitStack_Sq(&S); int n; scanf("%d",&n); int m=1; while(m!=0) { //printf("进入while"); int x=0; x=n%8; Push_Sq(&S,x); //printf("push结束"); m=n/8; n=m; } StackTraverse_Sq(&S); return 0; }
2.队列的应用
有n个人围成一圈，从第1个人开始，1，2，…，m报数，报至m出局，余下的人继续从1，2，…，m报数，重复之前的流程，要求：求出被淘汰编号的序列，及最后剩下的一人是原来的第几号？
例如：
10
3
3 6 9 2 7 1 8 5 10
4
# include <stdio.h> # include <stdlib.h> # define MAXSIZE 100 typedef struct { int *base ; int front; int rear; } SqQueue; int InitQueue(SqQueue *Q){ Q->base=(int *)malloc (sizeof(int)*MAXSIZE); Q->front=Q->rear=0; return 1; } SqQueue * EnQueue(SqQueue *Q,int n) { //判断队满 if(Q->front==(Q->rear+1)%MAXSIZE) { exit(0); } for(int i=0;i<n;i++) { Q->base[Q->rear]=i+1; Q->rear=(Q->rear+1)%MAXSIZE; } return Q; } int taotai(SqQueue *Q,int n,int m) { int f=0; int a[n]; int i=0; for( i=0;i<n;i++) { a[i]=1; } int t=n; while(t!=1) { if(a[i]==1) { f++; } if(f==m) { f=0; a[i]=0; t--; printf("%d ",i+1); } if(i<n) { i++; } else { i=0; } } for(i=0;i<n;i++) { if(a[i]==1) { printf("\n"); printf("%d",i+1); } } return 1; } int main() { int n; SqQueue Q; scanf("%d",&n); InitQueue(&Q); int m; scanf("%d",&m); EnQueue(&Q,n); taotai(&Q,n,m); return 0; }
