一篇文章带你了解——栈和队列

目录栈1、栈的基本概念2、栈的实现方式——数组存储结构初始化销毁入栈取出栈顶元素获取栈顶元素判空获取栈的长度3、实现方式——链表存储结构初始化销毁入栈出栈获取栈顶元素获取栈中有效元素个数判空队列基本概念队列的存储结构初始化销毁判空队列长获取头的元素入队列出队列栈1、栈的基本概念栈栈(stack)是限定仅在⼀端进⾏插⼊或删除操作的线性表。栈顶top能插入和删除的一端栈顶(bottom)不能插入和删除的一端出栈删除数据在栈顶入栈放入数据在栈顶——也叫压栈/入栈/进栈空栈没用任何元素栈也被称为后进先出的顺序表Last In First Out简称LIFO结构2、栈的实现方式——数组使用结构选择数组因为栈是“尾部操作”最频繁的数据结构后进先出而数组在尾部操作入栈/出栈的时间复杂度是 O(1)且内存连续、缓存利用率极高所以用数组是最自然、最高效的选择。基本操作void STInit(ST* st);//初始化void STDestroy(ST* st);//销毁void STPush(ST* st,STDataType x);//入栈void STPop(ST* st);//出栈STDataType STTop(ST* st);//获取栈顶元素bool STEmpty(ST* st);//判空int STSize(ST* st);//取长度存储结构typedef int STDataType; typedef struct Stack { STDataType* a;//存储数组 int top;//栈顶的下一位 int capacity;//容量 }ST;注意这里的top到底是指向栈顶元素还是栈顶的下一位如果指向栈顶元素那么top的初始化就要是-1如果是栈顶元素的下一位就是0。因为这里要思考一个问题 就是当top0的时候数组是否有元素如果top0的时候没用那么我们就要让top指向栈顶元素的下一位。下面的top指向的是栈顶元素的下一位。初始化void STInit(ST* st) { assert(st); st-a NULL; st-top 0; st-capacity 0; }销毁void STDestroy(ST* st) { assert(st); free(st-a); st-a NULL; st-capacity 0; st-top 0; }入栈void STPush(ST* st, STDataType x) { assert(st); if (st-top st-capacity) { int newcapacity st-capacity 0 ? 4 : st-capacity * 2; STDataType* tmp (STDataType*)realloc(st-a, newcapacity*sizeof(STDataType)); if (tmpNULL) { perror(realloc fail); return; } st-atmp; st-capacity newcapacity; } st-a[st-top] x; st-top; }取出栈顶元素void STPop(ST* st) { assert(st); assert(st-top0); st-top--; }获取栈顶元素STDataType STTop(ST* st) { assert(st); assert(st-top 0); return st-a[st-top-1]; }判空bool STEmpty(ST* st) { assert(st); return st-top 0; }获取栈的长度int STSize(ST* st) { assert(st); return st-top; }3、实现方式——链表链式栈的结构可以选择单链表也可以选择双向链表但是需要知道的是如果选择单链表要用头当作栈顶因为栈的特点就是在栈顶取数据和出数据单链表在头节点取出和放入数据的时间复杂度都是O1尾节点还要遍历找尾时间复杂度是O(N)。当然也可以使用双向链表而且无论是用头还是尾做栈顶时间复杂度都是O1但是建议还是选择单链表因为单链表相比双向链表节省空间因此使用单链表。在使用单链表的时候可以不使用哨兵位头结点也可用这里我不用因为哨兵位头结点并没有给头删和头插带来遍历所以不用也可以节省一个节点的空间。存储结构typedef int LSDataType; typedef struct LinkStackNode { struct LinkStackNode* Next; LSDataType data; }LSNode; typedef struct { LSNode* phead; int size; }LinkStack;这里定义了两个结构体对应了链表的节点和栈的管理结构他们的作用是不一样的可以把他们看作一个火车的车厢和火车头其中LinkStack是用来控制链表的起点和长度LSNode就是车厢的行李他们就构成了一个栈。初始化// 初始化链式栈s void LinkStackInit(LinkStack* s) { assert(s); s-phead NULL; s-size 0; }初始化的对象是LinkStack而不是LSNode因为要先有火车头LSNode等到入栈的时候才初始化因为入栈才开始创造节点。销毁// 销毁链式栈s void LinkStackDestroy(LinkStack* s) { assert(s); LSNode* cur s-phead; while (cur) { LSNode* nextNode cur-Next; free(cur); cur nextNode; } s-phead NULL; s-size 0; }入栈void LinkStackPush(LinkStack* s, LSDataType x) { assert(s); LSNode* newNode (LSNode*)malloc(sizeof(LSNode));//这里就要开始利用LSNode if (newNode NULL) { perror(malloc fail); return; } newNode-data x; newNode-Next s-phead; s-phead newNode; s-size; }出栈// 出栈并返回栈顶元素 LSDataType LinkStackPop(LinkStack* s) { assert(s); assert(s-size0); LSDataType ret s-phead-data; LSNode* nextNode s-phead-Next; free(s-phead); s-phead nextNode; s-size--; return ret; }获取栈顶元素// 获取栈顶元素 LSDataType LinkStackTop(LinkStack* s) { assert(s); assert(s-size 0); return s-phead-data; }获取栈中有效元素个数int LinkStackSize(LinkStack* s) { assert(s); return s-size; }判空bool LinkStackEmpty(LinkStack* s) { assert(s); return s-size 0; }队列基本概念队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出 FIFO(First In First Out)入队列进行插入操作的一端称为队尾出队列进行删除操作的一端称为队头队列的存储结构队列的链式存储我们可以选⽤单链表结构也可以选⽤双向链表结构。他们⼊队对应着在表尾插 ⼊出队对应着在表头删除。当然我们完全没必要选择双向链表因为单链表就可以⾼效实现还 省空间⼀些。双向链表没有优势每个结点还要多存储⼀个前驱指针使⽤它纯粹浪费了。typedef int QDataType; typedef struct QueueLinkNode { QDataType data; struct QueueLinkNode* Next; }QNode; typedef struct { QNode* Phead; QNode* Ptail; int size; }LinkQueue;//和上面所说是车厢不过要多一个Ptail方便尾插这里和上面的链式的栈实现类似定义两个结构体一个是节点的结构一个是栈的管理结构因为队列还要考虑队尾插入队尾插入记录的时候方便直接找到最后一个。初始化void QueueInit(LinkQueue* q) { assert(q); q-Phead q-Ptail (QNode*)malloc(sizeof(QNode)); if (q-Phead NULL) { perror(malloc fail); return; } q-Phead-Next NULL; q-size 0; }这里选择带头结点的链表。销毁void QueueDestroy(LinkQueue* q) { assert(q); QNode* cur q-Phead; while (cur) { QNode* nextNode cur-Next; free(cur); cur nextNode; } q-Phead NULL; q-Ptail NULL;//都要置为NULL q-size 0; }判空bool QueueEmpty(LinkQueue* q) { assert(q); return q-size 0; }队列长int QueueSize(LinkQueue* q) { assert(q); return q-size; }获取头的元素QDataType QueueFront(LinkQueue* q) { assert(q); assert(q-size0); return q-Phead-Next-data; }入队列void EnQueue(LinkQueue* q, QDataType x) { assert(q); QNode* newNode (QNode*)malloc(sizeof(QNode)); if (newNode NULL) { perror(malloc fail); return; } newNode-data x; newNode-Next NULL; q-Ptail-Next newNode; q-Ptail newNode; q-size; }出队列QDataType DeQueue(LinkQueue* q) { assert(q); assert(q-size0); QNode* delNode q-Phead-Next; QDataType x delNode-data; q-Phead-Next delNode-Next; free(delNode); delNode NULL; q-size--; if (q-size 0) { q-Ptail q-Phead; } return x; }这里有一个特殊的情况删除最后一个节点的时候Ptail和Phead都要置为NULL避免野指针。