文章目录

• 1、栈
• • • 1.1栈的概念
    • 1.2栈的实现
    • • • Stack.c
        • Stack.h
        • test.c
• 2、队列
• • • 2.1队列的概念
    • 2.2队列的实现
    • • • Queue.c
        • Queue.h
        • test.c

1、栈

1.1栈的概念

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

1.2栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
栈的实现还是分为三部分：
1️⃣Stack.c 栈功能的实现。
2️⃣Stack.h 结构体的创建，头文件的包含，函数的声明。
3️⃣test.c 进行测试栈的各项功能。

Stack.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"Stack.h"

void StackInit(ST* ps)
{//对栈进行初始化
	assert(ps);
	ps->a = (STDatatype*)malloc(sizeof(STDatatype) * 4);
	//开始先创建四个整型的空间
	if (ps->a == NULL)
	{//必须要进行是否开辟成功的判断！
		perror("malloc");
		exit(-1);
	}

	ps->top = 0;//初始化为零
	ps->capacity = 4;//开辟空间时开了四个整型空间，所以初始化时的容量为四。
}

void StackPush(ST* ps, STDatatype x)
{//将数据进行入栈
	assert(ps);
	if (ps->top == ps->capacity)
	{//判断是否需要扩容
		STDatatype* prev = (STDatatype*)realloc(ps->a, sizeof(STDatatype) * ps->capacity * 2);
		//这里扩容就直接扩容为原来的二倍
		if (prev == NULL)
		{//必须判断时候开辟成功
			perror("relloc");
			exit(-1);
		}
		ps->a = prev;
		ps->capacity *= 2;
	}
	ps->a[ps->top] = x;把数据进行入栈
	ps->top++;
}

void StackPop(ST* ps)
{//出栈
	assert(ps);
	assert(!StackEmpty(ps));
	//当top为零时，也就是该函数true时，不能在进行出栈的操作
	ps->top--;
}
void StackDestroy(ST* ps)
{//销毁栈，并释放空间
	assert(ps);

	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

STDatatype StackTop(ST* ps)
{//找到栈顶
	assert(ps);
	assert(!StackEmpty(ps));
	当top为零时，也就是该函数true时，不能在进行出栈的操作
	return ps->a[ps->top - 1];
	因为top指向的是栈顶的下一个位置，所以，在查找栈顶是需要进行减一
}

bool StackEmpty(ST* ps)
{//判断栈中是否为空
	assert(ps);

	/*if (ps->top == 0)
	{
		return true;
	}
	else
	{
		return false;
	}*/

	return ps->top == 0;
	//和上面注释的代码作用是一样的，下面的更简洁，上面的可读性更强
}

int StackSize(ST* ps)
{//用来计算一共有多少数据的
	assert(ps);
	return ps->top;
}

Stack.h

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

typedef int STDatatype;
typedef struct Stack
{
	STDatatype* a;
	int capacity;
	int top;   // 初始为0，表示栈顶位置下一个位置下标
}ST;

void StackInit(ST* ps);//初始化栈
void StackDestroy(ST* ps);//销毁栈
void StackPush(ST* ps, STDatatype x);//入栈
void StackPop(ST* ps);//出栈
STDatatype StackTop(ST* ps);//栈顶数据

bool StackEmpty(ST* ps);//栈是否为空
int StackSize(ST* ps);//栈中数据的个数

test.c

#include"Stack.h"

void TestStack1()
{
	ST st;
	StackInit(&st);
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);
	StackPush(&st, 5);

	printf("size:%d\n", StackSize(&st));

	StackPop(&st);
	StackPop(&st);
	StackPop(&st);
	StackPop(&st);
	StackPop(&st);
	StackDestroy(&st);
}

int main()
{
	TestStack1();

	return 0;
}

2、队列

2.1队列的概念

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

2.2队列的实现

队列用链表进行实现，不使用数组的原因是：在删除数据的时候需要将数据整体移动，而使用链表就不会。由两个结构体来实现，其中一个使用来创建结点用的，而另一个则是用来表示队头，队尾的，通多队头和队尾来控制数据的进出。

Queue.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"Queue.h"
//初始化队列。
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
	pq->size = 0;
}
//销毁数据，在这里需要一个一个的释放
//因为当时在开辟的时候也是一个一个的开辟的
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* prev = cur;
		cur = cur->next;
		free(prev);
	}
	pq->head = NULL;
	pq->tail = NULL;
	pq->size = 0;
}
//在队尾插入数据
//这里的size是用来记录在队列当中数据的个数的。
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	if (pq->head == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	pq->size++;
	newnode->data = x;
	newnode->next = NULL;
}
//在队头删除数据
void QueuePop(Queue* pq)
{
	assert(pq);
	//这里需要判断一下队列是否为空
	//当为空时并不能在删除数据
	assert(!QueueEmpty(pq));
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* prev = pq->head;
		pq->head = pq->head->next;
		free(prev);
	}
	pq->size--;
}

//用来判断队列是否为空。
//通过下面的两种方法是都可以的，一种是通过size
//另一种是对队头队尾进行判断
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	if (pq->size == 0)
	{
		return true;
	}
	return false;
	//return pq->head == NULL && pq->tail == NULL;
}
//返回队头数据
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;
}
//返回队列中数据的个数。
int QueueSize(Queue* pq)
{
	return pq->size;
}

Queue.h

#define _CRT_SECURE_NO_WARNINGS 1

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

typedef int QDataType;
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}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);
//返回队头数据
QDataType QueueFront(Queue* pq);
//返回队尾数据
QDataType QueueBack(Queue* pq);
//判断队列是否为空
bool QueueEmpty(Queue* pq);
//计算队列中有多少数据
int QueueSize(Queue* pq);

test.c

对队列的各项功能进行测试。

#define _CRT_SECURE_NO_WARNINGS 1

#include"Queue.h"
int main()
{
	Queue pq;
	QueueInit(&pq);
	QueuePush(&pq, 1);
	QueuePush(&pq, 2);
	QueuePush(&pq, 3);
	QueuePush(&pq, 4);
	QueuePush(&pq, 5);
	QueuePush(&pq, 6);
	/*QNode* cur = pq.head;
	while (cur)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}*/
	QueuePop(&pq);
	QueuePop(&pq);
	QueuePop(&pq);
	QueuePop(&pq);
	QueuePop(&pq);
	//QueuePop(&pq);
	printf("\n%d", QueueSize(&pq));
	QNode* cur = pq.head;
	while (cur)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("%d", QueueFront(&pq));
	printf("%d", QueueBack(&pq));
	QueueDestroy(&pq);
	return 0;
}