编程杂谈

栈相关概念什么是栈是限定仅在表尾(栈顶)进行插入和删除操作的线性表栈又称为后进先出(LastInFirstOut)的线性表,简称LIFO结构栈顶(top)我们把允许插入和删除的一端称为栈顶栈底(bottom)另一端称为栈底空栈不含任何任何数据元素的栈称为==空栈==栈的操作入栈入栈又称压栈,就是向栈中放数据,每次放入一个top指针就+1出栈取出栈中数据的操作,每取出一个top指针就-1清空栈清空栈,是把top指针直接指向bottom指针,原本物理空间上数据还存在栈的实现创建队列结构体#include<stdio.h>#include<stdlib.h>#defineSTACK_INIT_SIZE20//栈大小#defineSTACK_INCREMENT10//申请空间大小typedefcharElemType;//定义栈typedefstruct{ElemType*base;//栈低ElemType*top;//栈顶intstackSize;//当前栈容纳的大小}sqStack;初始化队列//初始化栈voidinitStack(sqStack*s){s->base=(ElemType*)malloc(STACK_INCREMENT*sizeof(ElemType));if(s->base==NULL)exit(-1);//空间申请失败s->top=s->base;s->stackSize=STACK_INIT_SIZE;printf("s->top:%p\n",s->top);printf("s->base:%p\n",s->base);}入栈(压栈)//压栈voidpush(sqStack*s,ElemTypee){//判断是否满栈,满栈则扩容if(s->top-s->base>=s->stackSize){s->base=(ElemType*)realloc(s->base,(s->stackSize+STACK_INCREMENT)*sizeof(ElemType));if(!s->base)exit(-1);}*(s->top)=e;//栈顶的值赋值es->top++;//栈顶地址向前推进}出栈//出栈voidpop(sqStack*s,ElemType*e){//判断下溢出if(s->top==s->base){return;}*e=*--s->top;//减之后赋值,*为取值,不是指针}当前栈长度//当前栈长度intsqStackLen(sqStack*s){returns->top-s->base;}主函数使用用户输入值,进行压栈,#号结束,输出栈内数据intmain(){sqStacks;initStack(&s);//初始化栈ElemTypec;printf("输入栈:");while((c=getchar())!='#'){getchar();push(&s,c);//压栈}getchar();//把\n从缓冲区去掉ElemTypee;while(sqStackLen(&s)){pop(&s,&e);//出栈printf("%c",e);}return0;}扩展(栈链)就是把栈和单链表结合,如下图一样栈链内元素是指针相连,而栈是顺序的地址队列概念什么是队列队列(queue)是只允许在一端进行插入的操作,而在另一端进行删除操作的线性表。队列主要特征是先进先出(FirstInFirstOut)队列操作队列的结构体#include<stdio.h>#include<stdlib.h>#defineElemTypechar//队列元素结构体(链表)typedefstructQNode{ElemTypedata;//队列节点数据structQNode*next;//队列指针}QNode,*QueuePrt;//队列头尾typedefstruct{QueuePrtfront,rear;//队头指针,队尾指针}LinkQueue;创建队列/*创建结构体在内存中创建一个头结点,将队列的头尾指针指向头结点,此时队列为空*/voidinitQueue(LinkQueue*q){q->front=q->rear=(QueuePrt)malloc(sizeof(QNode));if(!q->front)exit(-1);q->front->next=NULL;}入队列//入队列(下面是在从尾部入)voidinertQueue(LinkQueue*q,ElemTypee){QueuePrtnode=(QueuePrt)malloc(sizeof(QNode));if(!node)exit(-1);node->data=e;node->next=q->rear->next;q->rear->next=node;q->rear=node;}出队操作(取出队列的数据)//出队操作(下面是从队列头部取值)voidgetQueue(LinkQueue*q,ElemType*e){if(q->front==q->rear)return;//队列为空QueuePrtnode=q->front->next;*e=node->data;q->front->next=node->next;//队列头部向移动一位if(q->rear==node)q->rear=q->front;//队列最后数据被取出是,初始化为空free(node);};销毁队列//销毁队列voiddeleteQueue(LinkQueue*q){while(q->front){q->rear=q->front->next;free(q->front);q->front=q->rear;}}主函数使用intmain(){LinkQueueq;initQueue(&q);ElemTypee=0;printf("输入队列数据:");scanf("%c",&e);while(e!='#'){inertQueue(&q,e);scanf("%c",&e);}printf("队列中的数据:\n");while(q.rear!=q.front){getQueue(&q,&e);printf("%c",e);}return0;}