栈和队列--数据结构初阶(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>typedef 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<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);
}

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