栈和队列--数据结构初阶(2)(C/C++)
文章目录
前言
这期的话会给大家讲解栈和队列的模拟实现和在STL中栈和队列怎么用的一些知识和习题部分(这部分侧重于理论知识，习题倒还是不难)
理论部分
栈的模拟实现
typedef int STDataType; typedef struct Stack { STDataType* a;//这里的a想表示的是数组 int top;//表示数组a当前的容量 int capacity; }ST; void STInit(ST* ps) { assert(ps); ps->a = (STDataType*)malloc(sizeof(STDataType) * 4); if (ps->a == NULL) { perror("malloc fail"); return; } ps->capacity = 4; ps->top = 0; } void STDestroy(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->top = 0; ps->capacity = 0; } void STPush(ST* ps, STDataType x) { assert(ps); if (ps->top == ps->capacity) { STDataType* tmp = (STDataType*)realloc(ps->a,sizeof(STDataType) * ps->capacity*2); if (tmp == NULL) { perror("realloc fail"); return; } ps->a = tmp; ps->capacity *= 2; } ps->a[ps->top] = x; ps->top++; } void STPop(ST* ps) { assert(ps); assert(!STEmpty(ps)); ps->top--; } int STSize(ST* ps) { assert(ps); return ps->top; } bool STEmpty(ST* ps) { assert(ps); return ps->top == 0; }//拓展:bool里面如果return的是数字的话，会隐式转换 STDataType STTop(ST* ps) { assert(ps); assert(!STEmpty(ps)); return ps->a[ps->top - 1]; } 注意:这样写的话，此时的栈顶的下标是top-1 stPush那里一般用ps->top == ps->capacity top那里是还没存元素的 开空间完记得检查是否开辟成功 尽量不要用while(st.top!=0去代替while(!STEmpty（&st）)),数据结构最好封装起来 注意STTop最后那里是ps->a[ps->top-1] 这个代码有个问题:封装时一般要typedef类型，这里搞了但是没去用 (让以后要改类型时只用改一次) STL中的栈容器
stack容器（栈） 头文件：#include<stack> 创建:stack<T>st;//st是变量名，可以改；T是任意类型的数据 size empty push:进栈 pop:出栈 top:返回栈顶元素，但是不会删除栈顶元素 (先进后出) 队列的模拟实现
#include<stdio.h>#include<stdlib.h>#include<stdbool.h>#include<assert.h>typedefchar QDatatype;typedefstructQueueNode{structQueueNode* next; QDatatype data;}QNode;typedefstructQueue{ QNode* head; QNode* tail;int size;}Queue;voidQueueInit(Queue* pq);voidQueueDestroy(Queue* pq);voidQueuePush(Queue* pq, QDatatype x);voidQueuePop(Queue* pq);intQueueSize(Queue* pq); bool QueueEmpty(Queue* pq); QDatatype QueueFront(Queue* pq); QDatatype QueueBack(Queue* pq);voidQueueInit(Queue* pq){assert(pq); pq->head = pq->tail =NULL; pq->size =0;}voidQueueDestroy(Queue* pq){assert(pq); QNode* cur = pq->head;while(cur){ QNode* next = cur->next;free(cur); cur = next;} pq->head = pq->tail =NULL; pq->size =0;}voidQueuePush(Queue* pq, QDatatype x){ QNode* newnode =(QNode*)malloc(sizeof(QNode));if(newnode ==NULL){perror("malloc fail");return;} newnode->data = x; newnode->next =NULL;if(pq->head ==NULL){assert(pq->tail ==NULL); pq->head = pq->tail = newnode;}else{ pq->tail->next = newnode; pq->tail = newnode;} pq->size++;}voidQueuePop(Queue* pq){assert(pq);assert(pq->head !=NULL);if(pq->head->next ==NULL){free(pq->head); pq->head = pq->tail =NULL;}else{ QNode* next = pq->head->next;free(pq->head); pq->head = next;} pq->size--;}intQueueSize(Queue* pq){assert(pq);return pq->size;} bool QueueEmpty(Queue* pq){assert(pq);return pq->size ==0;} QDatatype QueueFront(Queue* pq){assert(pq);assert(!QueueEmpty(pq));return pq->head->data;} QDatatype QueueBack(Queue* pq){assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;}结构体定义那里可以像这样在结构体里面用自己的指针 结构体1里面套结构体2的话，定义结构体1后不用单独手动再为结构体1中的结构体2开辟 跟定义int指针，想变成数组需要malloc区分 注意:assert检查的是结果为0，就会报错 STL中的队列容器
queue(队列)： 头文件:#include<queue> 创建:queue<T>q;//q是变量名，T是任意类型的数据 size empty push pop front:返回队头元素，但不会删除 back:返回队尾元素，但不会删除 不可以用clear来直接清除队列 pop删除的是队头 作业部分
力扣 有效的括号 注意点:右括号数量不等于左括号这个特殊情况不要忘了 感悟:像这种如果匹配的话要继续走，不匹配的话要干啥的if里面写不匹配的条件会好些 代码实现: typedef struct Stack { char*a; int top; int capacity; } void STInit() { a = (char*)malloc(sizeof(char)*4); capacity = 4; top = 0; } void STPush(char*ps,char x) { assert(ps); if(ps->top == ps->capacity) { a = (char*)malloc(sizeof(char)*ps->capacity*2); capacity*=2; } ps->a[ps->top] = x; ps->top++; } void STPop(char*ps,char x) { assert(ps); ps->top--; } bool isValid(char* s) { struct Stack; &a = &s; } if如果判断条件多的话可以像下面这样写，这样写不用续行符 而且if后面只跟一个语句的话，一般跟if写同一行上 
企业中的话，能初始化的尽量还是要初始化一下，竞赛一般不用 题目： 力扣 用栈实现队列 相比用队列实现栈可以优化的地方是:可以有个栈专门入栈，一个栈专门出栈，出栈的空了再把另一个栈倒过来 代码实现: class MyQueue { public: stack<int>q1; stack<int>q2; int count1 = 0; //用q1来存入栈，q2来搞出栈 void push(int x) { q1.push(x); } int pop() { if(!q2.empty()) { int m = q2.top(); q2.pop(); return m; } else{ while(q1.size()) { int k = q1.top(); q2.push(k); q1.pop(); } int n = q2.top(); q2.pop(); return n; } } int peek() { if(!q2.empty()) { return q2.top(); } else { while(q1.size()) { q2.push(q1.top()); q1.pop(); } return q2.top(); } } bool empty() { if(q1.empty()&&q2.empty()) return true; else{ return false; } } }; 题目:力扣 设计循环队列 这里用链表模拟队列不好(因为要找尾)所以用数组来模拟 想让数组也能循环的话，就要时不时让他对k取模(插入，删除过程中也要) 由这个题引申出来的知识有: 1.malloc了几次，后续也要free几次，虽然说不free也可以通过，但是要是在面试中就是减分项,比如下面这种malloc的方式 
代码实现: typedef struct { int*a; int front; int rear; int k; } MyCircularQueue; MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue*obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); obj->front = obj->rear = 0; obj->k = k; obj->a = (int*)malloc(sizeof(int)*(k+1)); return obj; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->front == obj->rear; } bool myCircularQueueIsFull(MyCircularQueue* obj) { return (obj->rear+1)%(obj->k+1) == obj->front; //这里的作用是让rear在数组末时可以返回到0那去以及防止是空 } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if(myCircularQueueIsFull(obj)) return false; obj->a[obj->rear] = value; obj->rear = ((++obj->rear))%(obj->k+1); return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return false; obj->front = (++obj->front)%(obj->k+1); return true; } int myCircularQueueFront(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) { return -1; } return obj->a[obj->front]; } int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) { return -1; } return obj->a[(obj->rear-1+obj->k+1)%(obj->k+1)]; } void myCircularQueueFree(MyCircularQueue* obj) { free(obj->a); free(obj); } 队列和栈都属于线性数据结构 循环队列也是线性数据结构 
