数据结构51题之栈和队列18题
创作不易,点个关注加个收藏再走,防止找不到
目录
一、栈系列基础8道题
1.顺序栈的建立
2.顺序栈的入栈
3.顺序栈的出栈
4.顺序栈栈顶元素的获取
5.链栈的建立
6.链栈的入栈
7.链栈的出栈
8.链栈栈顶元素的获取
二、队列系列基础8道题
1.循环队列的建立
2.循环队列的入队
3.循环队列的出队
4.循环队列队头元素的获取
5.链队列的建立
6.链队列的入队
7.链队列的出队
8.链队列队头元素的获取
三、栈与队列的应用
1.栈的应用
2.队列的应用
一、栈系列基础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 #include #define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int SElemType;#define MAXSIZE 100typedef 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_Sqint Push_Sq(SqStack *S,int n){ for(int i=0;itop=e; S->top++; } }void StackTraverse_Sq(SqStack *S,int n){ for(int i=0;itop--; 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 #include #define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int SElemType;#define MAXSIZE 100typedef 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_Sqint Push_Sq(SqStack *S,int n){ for(int i=0;itop=e; S->top++; } }void StackTraverse_Sq(SqStack *S,int n){ for(int i=0;itop--; 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 #include #define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int SElemType;#define MAXSIZE 100typedef 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_Sqvoid 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;itop--;e=*S->top;printf("%d ",e);}S->top=p;}SqStack* yazhan(SqStack *S,int n){int u;for(int i=0;itop++=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.输入要入栈的元素个数n3.向顺序栈中压入n个元素4.将顺序栈中的元素从栈顶到栈底依次输出(StackTraverse_Sq)5.获取栈顶元素6.输出栈顶元素7.销毁顺序栈(DestroyStack_Sq)例如:42 4 6 88 6 4 2 //遍历输出时最后一个元素后有一个空格8*/#include # include #define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int SElemType;#define MAXSIZE 100typedef 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;itop--;w=*S->top;printf("%d ",w);}S->top=p;printf("\n");}SqStack * shuru(SqStack *S,int n) { int y; for(int i=0;itop++=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# include 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;idata=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.输入要入栈的元素个数n3.向顺序栈中压入n个元素4.将链栈中的元素从栈顶到栈底依次输出(StackTraverse_Link)5.销毁链栈栈(DestroyStack_Link)例如:51 2 3 4 55 4 3 2 1 //遍历输出时最后一个元素后有一个空格*/# include # include #define MAXSIZE 100typedef 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;idata=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;idata);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# include 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;idata=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# include 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;idata=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.输入要入队的元素个数n4.向循环队列中输入n个元素(EnQueue_Sq)5.将循环队列中的元素从队头至队尾依次输出(StackQueue_Sq)6.销毁循环队列(DestroyQueue_Sq)例如:51 2 3 4 51 2 3 4 5 //遍历输出时最后一个元素后有一个空格*/# include # include # 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;ibase[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.输入要入队的元素个数n3.向循环队列中输入n个元素4.将循环队列中的元素从队头至队尾依次输出(StackQueue_Sq)5.销毁循环队列(DestroyQueue_Sq)例如:56 2 8 10 96 2 8 10 9 //遍历输出时最后一个元素后有一个空格*/# include # include # define MAXSIZE 100typedef 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;ibase[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 #include #define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int SElemType;#define MAXSIZE 100typedef 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_Sqvoid 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;itop--;e=*S->top;printf("%d ",e);}S->top=p;}SqStack* yazhan(SqStack *S,int n){int u;for(int i=0;itop++=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.输入要入队的元素个数n3.向循环队列中输入n个元素4.将循环队列中的元素从队头至队尾依次输出5.获取栈顶元素6.将循环队列中的元素从队头至队尾依次输出7.销毁循环队列例如:52 4 6 8 102 4 6 8 10 //遍历输出时最后一个元素后有一个空格2*/# include # include # 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;ibase[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 # include 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;idata=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 # include # define MAXSIZE 100typedef 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;ibase[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 # include 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;idata);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 # include 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;idata);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 # include # define MAXSIZE 100typedef 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 # include # define MAXSIZE 100typedef 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;ibase[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;}