栈和队列--数据结构初阶(2)(C/C++)_c++栈和队列的经典例题

文章目录

• 前言
• 理论部分
• • 栈的模拟实现
  • STL中的栈容器
  • 队列的模拟实现
  • STL中的队列容器
• 作业部分

前言

这期的话会给大家讲解栈和队列的模拟实现和在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->capacitytop那里是还没存元素的开空间完记得检查是否开辟成功尽量不要用while(st.top!=0去代替while(!STEmpty（&st）)),数据结构最好封装起来注意STTop最后那里是ps->a[ps->top-1]这个代码有个问题:封装时一般要typedef类型，这里搞了但是没去用  (让以后要改类型时只用改一次)

STL中的栈容器

stack容器（栈）头文件：#include创建:stackst;//st是变量名，可以改；T是任意类型的数据size empty push:进栈pop:出栈top:返回栈顶元素，但是不会删除栈顶元素(先进后出)

队列的模拟实现

#include#include#include#includetypedef char QDatatype;typedef struct QueueNode{struct QueueNode* next;QDatatype data;}QNode;typedef struct Queue{QNode* head;QNode* tail;int size;}Queue;void QueueInit(Queue* pq);void QueueDestroy(Queue* pq);void QueuePush(Queue* pq, QDatatype x);void QueuePop(Queue* pq);int QueueSize(Queue* pq);bool QueueEmpty(Queue* pq);QDatatype QueueFront(Queue* pq);QDatatype QueueBack(Queue* pq);void QueueInit(Queue* pq){assert(pq);pq->head = pq->tail = NULL;pq->size = 0;}void QueueDestroy(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;}void QueuePush(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++;}void QueuePop(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--;}int QueueSize(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创建:queueq;//q是变量名，T是任意类型的数据size empty push popfront:返回队头元素，但不会删除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:  stackq1; stackq2; 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);}

队列和栈都属于线性数据结构 循环队列也是线性数据结构