一、栈

1、概念

栈是一种特殊的线性表，只允许在固定的一端进行插入和删除元素的操作，进行数据插入与删除的一端叫做栈顶，另一端叫做栈底，栈中的元素遵循后进先出的原则
这里给的是一个抽象的概念，我们可以把栈看做一个装满大米的米缸，我们想要吃米的时候，后放入米缸的米肯定要先吃，此时缸底就是栈底，缸顶就是栈顶，我们在不破坏缸的情况下只能从缸顶来取用大米
压栈/进栈/入栈：栈在栈顶的插入操作
出栈：栈在栈顶的删除操作

2、栈的实现

栈一般可以由数组和链表实现，相对来说数组来实现更好一些，因为在尾插数据的时候，单链表每次插入都需要malloc一块新的空间，如果插入的数据比较多，那么效率就会大大降低，但数组来实现的话，数据越多，数组的效率相较于链表就会越高，因为数组每一次扩容都是两倍两倍的扩，越到后边需要扩容的次数就越少
栈分为静态栈与动态栈两种，顾名思义，静态就是固定的，没法改变的，动态就可以自己调节增长与减小，在实际使用中，我们肯定都是选择动态栈

Stack.h

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top; // 栈顶
	int capacity; // 容量
}Stack;
// 初始化栈
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);

Stack.c

#define _CRT_SECURE_NO_WARNINGS

#include "Stack.h"

void StackInit(Stack* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	if (ps->capacity == ps->top)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		//新的容量：如果原容量为0，那么给它赋值为4字节，如果不为0，则赋值为原来的两倍
		STDataType* tmp = (STDataType*)realloc(ps->a,sizeof(STDataType)*newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = data;//将栈顶的数据赋值为为data
	ps->top++;//将栈顶下标+1
}

void StackPop(Stack* ps)
{
	assert(ps);
	ps->top--;
}

STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->a);
	return ps->a[ps->top - 1];//assert防为空后直接返回栈顶数据
}

int StackSize(Stack* ps)
{
	assert(ps);
	assert(ps->a);
	return ps->top - 1;//防为空后直接返回top-1
}

int StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;//判断句，真则返回非零数，假则返回0
}

void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

test.c

#define _CRT_SECURE_NO_WARNINGS

#include "Stack.h"

int main()
{
	Stack s1;
	StackInit(&s1);//初始化
	printf("%d\n", StackEmpty(&s1));//判空
	
	StackPush(&s1, 1);
	StackPush(&s1, 2);
	StackPush(&s1, 3);
	StackPush(&s1, 4);
	//插入
	printf("%d\n", StackSize(&s1));//大小
	printf("%d\n", StackTop(&s1));//栈顶数据
	
	StackPop(&s1);//删除
	
	printf("%d\n", StackTop(&s1));
	printf("%d\n", StackSize(&s1));
	
	StackDestroy(&s1);//销毁
	return 0;
}

二、队列

1、概念

队列是只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，特性是先进先出，先进入的先出来
入队列：从插入的一端进入，这一端叫做队尾
出队列：从删除的一端删除，这一端叫做队头
当我们排队打饭的时候，这就是一个队列，在窗口前有一条长队，这就是一个队列，我们要排队，只能排到最后面，我们就插入到了队列中，当最前面的人打完饭时，他就从队列中删除了，在这个队伍中，先来的总是先打完饭，然后离开队伍，后来的总是后打完饭，然后离开队伍，就是先进先出的原则

2、队列的实现

因为涉及到两边同时工作，一边出数据一边入数据，这里更加推荐使用链表，因为数组在进行出数据的时候，需要进行覆盖操作，所以效率在数据比较多的时候会非常低，而链表的删除插入很方便，所以实现队列我们用链表

Queue.h

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define QDataType int

// 链式结构：表示队列
typedef struct QListNode
{
	struct QListNode* pNext;
	QDataType data;
}QNode;
// 队列的结构
typedef struct Queue
{
	QNode* front;
	QNode* rear;
}Queue;
// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QDataType QueueFront(Queue* q);
// 获取队列队尾元素
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);

Queue.c

#include "Queue.h"

void QueueInit(Queue* q)
{
	assert(q);
	q->front = q->rear = (Queue*)malloc(sizeof(Queue));
	//为队列在堆上开辟一块空间，队头队尾都指向这块空间
	if (q->front == NULL)
	{
		perror("malloc fail");
		return;
	}
	q->front->pNext = q->rear->pNext = NULL;//置空队头队尾指针

}

void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->data = data;
	newnode->pNext = NULL;
	q->rear->pNext = newnode;
	q->rear = newnode;
	//在队尾插入新节点，让新节点成为队尾
}

void QueuePop(Queue* q)
{
	assert(q);

	QNode* del = q->front;
	q->front = q->front->pNext;
	free(del);
	del = NULL;//记录节点，释放空间，置空指针
}

QDataType QueueFront(Queue* q)
{
	assert(q);
	return q->front->pNext->data;
}

QDataType QueueBack(Queue* q)
{
	assert(q);
	return q->rear->data;
}

int QueueSize(Queue* q)
{
	assert(q);
	int count = 0;
	QNode* pur = q->front->pNext;
	while (pur)
	{
		pur = pur->pNext;
		count++;
	}
	return count;
	//遍历一遍，count记录
}

int QueueEmpty(Queue* q)
{
	assert(q);
	return q->front == q->rear;
	//判断，当队头队尾位置相同时返回非零，不同返回0
}

void QueueDestroy(Queue* q)
{
	assert(q);
	while (q->front != q->rear)
	{
		QNode* del = q->front;
		q->front = q->front->pNext;
		free(del);
		del = NULL;
	}
}

test.c

#include "Queue.h"

void test()
{
	Queue q;
	QueueInit(&q);//初始化
	printf("%d\n", QueueEmpty(&q));//判空

	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
//测试插入
	printf("%d\n", QueueEmpty(&q));//判空

	printf("%d\n", QueueFront(&q));//队头数据

	printf("%d\n", QueueBack(&q));//队尾数据

	printf("%d\n", QueueSize(&q));//队伍大小
	QueuePop(&q);//删除
	printf("%d\n", QueueFront(&q));

	printf("%d\n", QueueSize(&q));
	QueueDestroy(&q);//销毁
}
int main()
{
	test();
	return 0;
}

三、深入了解栈和队列的特性

当我们了解了队列和栈的基本概念之后，我们可以通过它们的互相实现来进一步加深理解，这种问题在实际生产生活中上没有什么意义，但可以帮助我们更好地掌握栈和队列

1、用队列实现栈

leetcode-用队列实现栈

//这里插入队列的定义，在上方有，这里需要定义了才能使用，因为已经写过了我就不再复制上增加篇幅了

typedef struct {
    Queue q1;
    Queue q2;
} MyStack;
//两个栈实现队列
MyStack* myStackCreate() {
    MyStack* new = (MyStack*)malloc(sizeof(MyStack));
    if(new == NULL)
    {
        perror("malloc fail");
        exit(1);
    }
    QueueInit(&new->q1);
    QueueInit(&new->q2);
    return new;
}

void myStackPush(MyStack* obj, int x) {
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);
    }
    //两个队列，当两者都为空时，1 2 3 4存入，q1没有数据，q2为1 2 3 4，当出数据时，
    //q2将除了尾节点以外的节点放到q1里边，q2剩下4，把4出掉，再出数据时，
    //q1把除了尾节点以外的节点放到q2里边，出掉3
}

int myStackPop(MyStack* obj) {
    Queue* pEmptyQ = &obj->q1;
    Queue* pNonEmptyQ = &obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        pEmptyQ = &obj->q2;
        pNonEmptyQ = &obj->q1;
    }
//这里可以灵活地将在出数据时的由谁存数据和由谁出数据整理清楚，
//当q1不为空时， pEmptyQ = &obj->q2，pNonEmptyQ = &obj->q1;
//当q1为空时，pEmptyQ = &obj->q1，pNonEmptyQ = &obj->q2;
//pEmptyQ用来存数据，pNonEmptyQ用来出数据
    while(QueueSize(pNonEmptyQ)>1)
    {
        QueuePush(pEmptyQ,QueueFront(pNonEmptyQ));
        QueuePop(pNonEmptyQ);
    }
    int top = QueueFront(pNonEmptyQ);
    QueuePop(pNonEmptyQ);
    return top;
    //访问到出数据队列的数据，将其保存然后pop掉，然后返回值
}

int myStackTop(MyStack* obj) {
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else
    {
        return QueueBack(&obj->q2);
    }
    //看哪个队列不为空，不为空的那个队列的尾节点数据就是栈顶数据
}

bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}//两个都成立则为真，一方不成立则为假，当两个都为空时才为空

void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);

    free(obj);
}

2、用栈实现队列

leetcode-用栈实现队列

//这里插入栈的定义，在上方有，这里需要定义了才能使用，因为已经写过了我就不再复制上增加篇幅了

typedef struct {
    Stack s1;
    Stack s2;
} MyQueue;
//用两个栈来实现队列
//一个栈用来存数据，另一个用来出数据，将数据在两个栈中来回倒一下，再出的数据就会是先进先出的队列型
//1 2 3 4存入栈当中，再从这个栈存到另一个栈中，那么另一个栈就是 4 3 2 1，再出数据就是1 2 3 4
//这里s1负责出，s2负责入
MyQueue* myQueueCreate() {
    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
    if(obj == NULL)
    {
        perror("malloc fail");
        return NULL;
    }
    StackInit(&obj->s1);
    StackInit(&obj->s2);

    return obj;
}

void myQueuePush(MyQueue* obj, int x) {
    StackPush(&obj->s1,x);
    //因为我们的出数据和入数据的栈在之前就明确好了，那么直接找到一个栈出数据就可以了
}

int myQueuePop(MyQueue* obj) {
    int front = myQueuePeek(obj);//嵌套使用
    StackPop(&obj->s2);
    return front;
}

int myQueuePeek(MyQueue* obj) {
    if(StackEmpty(&obj->s2))
    {
        while(!StackEmpty(&obj->s1))
        {
            StackPush(&obj->s2,StackTop(&obj->s1));
            StackPop(&obj->s1);
        }
    }//当s1不为空时，将s1的数据全部放到s2中
    return StackTop(&obj->s2);//返回s2的栈顶数据
}

bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->s1) && StackEmpty(&obj->s2);
}//两者都为空则为空，否则则不是空

void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->s1);
    StackDestroy(&obj->s2);
    free(obj);
}

3、循环队列

leetcode-循环队列

typedef struct {
    int front;//队头
    int rear;//队尾
    int k;//数据个数，实际开的空间个数是k+1
    int* a;//节点指针
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->a = (int*)malloc(sizeof(int)*(k+1));
    obj->front = obj->rear = 0;
    obj->k = k;
    return obj;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front == obj->rear;
}//当队头队尾相同时，为空

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->rear+1)%(obj->k+1) == obj->front;
}//就是当队尾为队头的前一个节点的前一个节点时，就是满的

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+obj->k)%(obj->k+1)];
    //这里同上同下，都是怕队头\尾的排号大于存储最大数据个数的情况
}//队尾数据

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}