栈、队列-栈的概念及结构/栈的实现/栈的顺序存储结构-队列的概念及结构、队列的实现（链式存储结构））

一、栈的概念及结构

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO (Last In First Out)的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
空栈：不含任何元素的空表。
—后进先出(Last In First Out )原则

二、栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。

三、栈的顺序存储结构

#pragma once

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

typedef int STDataType;

typedef struct Stack
{
	STDataType* a; //
	int top;	  //相当于数组下标，注意栈为空时，top的值应该为？
	int capacity;//栈的容量
}ST;

void STInit(ST* pst);
void STDestroy(ST* pst);

//入栈
void STPush(ST* pst,STDataType x);

//出栈
void STPop(ST* pst);

//栈顶元素
STDataType STTop(ST* pst);

//判断栈是否为空
bool STEmpty(ST* pst);

//获取size
int STSize(ST* pst);

#include "stack.h"

void STInit(ST* pst)
{
	assert(pst);
	pst->a = NULL;
	pst->top = 0;//top指向-1，表示栈顶元素数据   0 栈顶数据下一位置
	pst->capacity = 0;
}

void STDestroy(ST* pst)
{
	assert(pst);

	free(pst->a);
	pst->a = NULL;
	pst->top = pst->capacity = 0;
}
//判断栈是否为空
bool STEmpty(ST* pst)
{
	assert(pst);
	return pst->top == 0;
}

//入栈
void STPush(ST* pst, STDataType x)
{
	if (pst->top == pst->capacity)
	{
		int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDataType* tmp = realloc(pst->a, newCapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		pst->a = tmp;
		pst->capacity = newCapacity;
	}
	pst->a[pst->top] = x;
	pst->top++;
}

//出栈
void STPop(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));
	pst->top--;
}

//栈顶元素
STDataType STTop(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));
	return pst->a[pst->top - 1];
}


//获取size
int STSize(ST* pst)
{
	assert(pst);
	return pst->top;
}

#include "stack.h"

void test1()
{
	ST st;
	STInit(&st);

	STPush(&st, 3);
	STPush(&st, 4);
	STPush(&st, 5); 
	printf("%d ", STTop(&st));
	STPop(&st);
	STPush(&st, 6);
	STPush(&st, 16);
	while (!STEmpty(&st))
	{
		printf("%d ", STTop(&st));
		STPop(&st);
	}

	STDestroy(&st);
}
int main()
{
	test1();
	return 0;
}

四、队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)原则。
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头

在这里插入图片描述

队列也可以数组和链表的结构实现，使用链表的结构实现更优，因为如果使用数组结构，每次元素出队列时都是从数组头出数据，再依次将数组上的元素往前移，效率会比较低。

五、队列的实现

在这里插入图片描述

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int QDataType;

 链式结构：表示队列
typedef struct QListNode
{
	QDataType data;
	struct QListNode* next;
}QNode;

// 队列的结构
typedef struct Queue
{
	QNode* front;//方便出数据
	QNode* rear;//方便入数据
	int size;
}Queue;

// 初始化队列
void QueueInit(Queue* q);

// 队尾入队列
void QueuePush(Queue* q, QDataType x);

// 队头出队列
void QueuePop(Queue* q);

// 获取队列头部元素
QDataType QueueFront(Queue* q);

// 获取队列队尾元素
QDataType QueueBack(Queue* q);

// 获取队列中有效元素个数
int QueueSize(Queue* q);

// 检测队列是否为空
bool QueueEmpty(Queue* q);

// 销毁队列
void QueueDestroy(Queue* q);

#include "queue.h"
// 初始化队列
void QueueInit(Queue* q)
{
	assert(q);
	q->front = NULL;
	q->rear = NULL;
	q->size = 0;
}

// 队尾入队列
void QueuePush(Queue* q, QDataType x)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;

	if (q->rear == NULL)
	{
		assert(q->front == NULL);
		q->front = q->rear = newnode;
	}
	else
	{
		q->rear->next = newnode;
		q->rear = newnode;
	}
	q->size++;
}

// 队头出队列
void QueuePop(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));//判断队列是否为空
	//1.一个结点
	//2.多个结点
	if(q->front->next == NULL)
	{
		free(q->front);
		q->front = q->rear = NULL;
	}
	else
	{
		//头删
		QNode* next = q->front->next;//next是局部变量，出作用域就销毁了
		free(q->front);
		q->front = next;
	}
	q->size--;
}

// 获取队列头部元素
QDataType QueueFront(Queue* q)
{
	assert(q);
	return q->front->data;
}

// 获取队列队尾元素
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->rear->data;
}

// 获取队列中有效元素个数
int QueueSize(Queue* q)
{
	assert(q);
	return q->size;
}

// 检测队列是否为空
bool QueueEmpty(Queue* q)
{
	assert(q);

	return q->front == NULL && q->rear == NULL;
	//return q->size == 0;
}

// 销毁队列
void QueueDestroy(Queue* q) {
	assert(q);

	QNode* cur = q->front;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	q->front = q->rear = NULL;
	q->size = 0;
}

#include "queue.h"

void test()
{
	QNode* phead = NULL;
	QNode* ptail = NULL;
	Queue q;
	QueueInit(&q);

	QueuePush(&q, 1);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	QueuePush(&q, 6);
	QueuePush(&q, 7);

	int ret = QueueSize(&q);
	printf("%d\n", ret);

	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	printf("\n");

	ret = QueueSize(&q);
	printf("%d", ret);

	QueueDestroy(&q);
}

int main()
{
	test();
	return 0;
}