栈和队列都是一种数据结构其区别在于进出顺序。栈的进出顺序是后进先出(LIFO)队列的进出顺序是先进先出(FIFO)。1.栈1.1 栈的基本概念栈是仅限在一端插入删除的线性表。对于插入删除的那一端我们称之为栈顶(top)而另一端则成为栈底(bottom)。若栈中没有元素则称为空栈。栈中插入数据一般称为入栈/进栈删除数据一般称为出栈。1.2 出栈入栈顺序假设入栈顺序是a,b,c,d,e。出栈顺序可以是edcba也可以是a,b,c,d,e还可以是b,a,d,c,e。总共有 C(2n,n)/(n1) 种顺序。1.3 栈的实现我们用顺序结构来实现栈。因为尾插尾删对于顺序存储来说很简单且对于链式存储而言尾删还是比较麻烦的。首先我们要创建一个栈的数据类型// 支持动态增长的栈typedefintSTDataType;typedefstructStack{STDataType*_a;int_top;// 栈顶int_capacity;// 容量}Stack;STDataType是栈的元素的类型。_a通常为在堆上的指针相当于数组。1.3.1 栈的初始化// 初始化栈voidStackInit(Stack*ps){assert(ps);ps-_a(STDataType*)malloc(sizeof(STDataType)*4);if(ps-_aNULL){printf(申请内存失败\n);exit(-1);}ps-_top0;ps-_capacity4;}在初始化栈这个函数里我们给指针_a在堆上申请4个元素的空间作为初始容量。接着把_top初始化为0_capacity初始化为4。【注意】若_top要指向栈顶元素则空栈时_top应为-1。1.3.2 判断是否为空栈// 检测栈是否为空如果为空返回非零结果如果不为空返回0intStackEmpty(Stack*ps){assert(ps);returnps-_top0;}判断栈是否为空只需要判断_top是否为0。1.3.3 入栈// 入栈voidStackPush(Stack*ps,STDataType data){assert(ps);if(ps-_capacityps-_top){ps-_a(STDataType*)malloc(sizeof(STDataType)*ps-_capacity*2);if(ps-_aNULL){printf(申请内存失败\n);exit(-1);}ps-_capacity*2;}ps-_a[ps-_top]data;}入栈前应判断空间是否已满如果满了得先扩容。一般地扩容的空间应为原空间的1.5到2倍。入栈操作很简单只需要在当前_top位置放入数据再让_top即可。1.3.4 出栈// 出栈voidStackPop(Stack*ps){assert(ps);assert(!StackEmpty(ps));ps-_top--;}出栈前应先判断是否为空栈如果已经是空栈了那就没必要出栈了强行出栈也会把_top变成-1下次入栈可就越界了。出栈操作也很简单就是让_top–即可。1.3.5 销毁栈// 销毁栈voidStackDestroy(Stack*ps){assert(ps);free(ps-_a);ps-_aNULL;ps-_capacity0;ps-_top0;}销毁栈即free掉从堆上申请来的空间把_a指针置空并把0赋值给_capacity和_top。2.队列2.1 队列的基本概念队列是在一端插入另一端删除的线性表。通常插入数据那一端我们称之为队头删除数据那一端我们称之为队尾。插入叫入队删除叫出队。而队列的出队顺序和入队顺序一样有且只有一种。2.2 队列的实现队列我们通常使用链式存储的结构。静态的顺序存储结构可能会导致空间不够或者浪费空间而若使用动态的顺序存储结构扩容是有代价的。无论静态或动态出队也会浪费一些空间。下面我们先创建结点数据类型typedefintQDataType;typedefstructQListNode{structQListNode*_next;QDataType _data;}QNode;QDataType是队列元素的数据类型_next指针记录下一个结点_data记录该节点的数据。接着我们创建队列数据类型:// 队列的结构typedefstructQueue{QNode*_front;QNode*_rear;intsize;}Queue;在这个结构体里_front为头指针_rear为尾指针size则表示链表长度。2.2.1 创建结点函数//创建结点QNode*creatQNode(QDataType x){QNode*Node(QNode*)malloc(sizeof(QNode));if(NodeNULL){printf(创建结点失败\n);exit(-1);}Node-_datax;Node-_nextNULL;returnNode;}该函数用于创建新结点。2.2.2 队列的初始化// 初始化队列voidQueueInit(Queue*q){assert(q);QNode*guardcreatQNode(-1);q-_frontguard;q-_rearguard;q-_front-_nextNULL;q-size0;}在这里我们选择带哨兵位的链表。先创建一个值为-1的哨兵位结点_front指向哨兵位_rear也指向哨兵位。接着把哨兵位的下一个结点置空size初始化为0。2.2.3 入队// 队尾入队列voidQueuePush(Queue*q,QDataType data){assert(q);QNode*newNodecreatQNode(data);;newNode-_nextNULL;q-_rear-_nextnewNode;q-_rearnewNode;q-size;}通常我们会在队尾入队。入队函数大概思路为先创建结点把这个新结点尾插到链表接着把尾指针指向插入的新结点size。2.2.4 出队// 队头出队列voidQueuePop(Queue*q){assert(q);QNode*delNodeq-_front-_next;if(delNode-_nextNULL){q-_rearq-_front;}q-_front-_nextdelNode-_next;free(delNode);q-size--;}出队这里我们要注意当队列只剩一个元素时出队结束之后我们要把rear指向哨兵位这么做一是为了防止野指针二是保持空状态一致frontrear。在出队操作中我们只需要把要出队的结点存起来然后改连接关系最后free要出队的结点。2.2.5 获取队头元素// 获取队列头部元素QDataTypeQueueFront(Queue*q){assert(q);assert(q-_front-_next);returnq-_front-_next-_data;}2.2.6 获取队尾元素// 获取队列队尾元素QDataTypeQueueBack(Queue*q){assert(q);assert(q-_rear!q-_front);returnq-_rear-_data;}2.2.7 获取队列有效元素个数// 获取队列中有效元素个数intQueueSize(Queue*q){assert(q);returnq-size;}2.2.8 检测队列是否为空// 检测队列是否为空如果为空返回非零结果如果非空返回0intQueueEmpty(Queue*q){assert(q);returnq-size0;}2.2.9 销毁队列// 销毁队列voidQueueDestroy(Queue*q){assert(q);QNode*curq-_front-_next;while(cur){QNode*tmpcur;free(tmp);curcur-_next;}free(q-_front);q-_frontNULL;q-_rearNULL;}销毁队列和销毁链表没啥区别就是依次释放结点。2.3 循环队列的实现一般的队列不用顺序存储主要还是因为出队会浪费空间。这时候我们可以想到循环利用空间这样不仅每次插入删除效率高CPU缓存命中率也高。2.3.1 循环队列的大概实现思路实现循环队列无非就是入队到数组的最后一位重新回到数组的第一位。可是如果front指针指向队头rear指针指向下次入队的位置我们会发现有一个问题——队列空和队列满时的判断条件是一致的——frontrear。那当然不行这时我们可以创建一个计数器入队size出队size–或者我们可以多创建一个空间来改变队空和队满的状态。下面我们用后者来示范循环队列的实现。2.3.1 循环队列的实现#includestdlib.htypedefstruct{int*arr;intfront;intrear;intN;}MyCircularQueue;MyCircularQueue*myCircularQueueCreate(intk){MyCircularQueue*q(MyCircularQueue*)malloc(sizeof(MyCircularQueue));q-arr(int*)malloc(sizeof(int)*(k1));q-front0;q-rear0;q-Nk1;returnq;}boolmyCircularQueueEnQueue(MyCircularQueue*obj,intvalue){if((obj-rear1)%obj-Nobj-front)returnfalse;obj-arr[obj-rear]value;obj-rear%obj-N;returntrue;}boolmyCircularQueueIsEmpty(MyCircularQueue*obj){returnobj-frontobj-rear;}boolmyCircularQueueDeQueue(MyCircularQueue*obj){if(myCircularQueueIsEmpty(obj))returnfalse;obj-front;obj-front%obj-N;returntrue;}intmyCircularQueueFront(MyCircularQueue*obj){if(obj-frontobj-rear)return-1;returnobj-arr[obj-front];}intmyCircularQueueRear(MyCircularQueue*obj){if(obj-frontobj-rear)return-1;intindex(obj-rear-1obj-N)%obj-N;returnobj-arr[index];}boolmyCircularQueueIsFull(MyCircularQueue*obj){return(obj-rear1)%obj-Nobj-front;}voidmyCircularQueueFree(MyCircularQueue*obj){free(obj-arr);free(obj);}从上面可以看出这么实现循环队列队空时frontrear队满时rear1 front当然我们要注意取模这样才能保证队列可以“绕回去”。上面的示例代码是leetcode的原题大家感兴趣可以做一下:循环队列实现