栈和队列的定义和实现

栈和队列

1.栈

1.1栈的概念及结构

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端

**称为栈顶，另一端称为栈底。**栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。

注意：

栈是一种特殊的线性表，逻辑结构是线性的，但是物理结构不一定是线性的。

因为栈的底层数据结构可以是数组，也可以是链表，没有规定。

用数组来表示栈

要让数组尾部来当栈顶，这样我们往里面添加数据不需要去移动数据，效率高，并且如果我们想让数据出栈就让尾部的数据删除就好，方便。

用链表来表示栈

用双向链表表示栈

用双向链表表示栈非常简单，栈顶的位置左右都行，入栈出栈，也就是插入节点，删除节点。

用单向链表表示栈

单链表来表示栈的话，让右边来当栈顶是不好的，虽然插入节点（入栈）很方便，但是你删除节点（出栈）不方便，因为单链表无法随机访问，每次都要通过遍历链表去找到最后一个节点的指针，才能删除节点（出栈）。

如果单链表很长，节点很多，效率就会非常低。

因此我们让左边去当栈顶

如图所示，我们让左边当栈顶，如果要插入节点（入栈），就头插，让其成为新的栈顶，要删除节点（出栈），就头删。非常方便。效率也高。

其实，推荐使用顺序表来实现栈

1.2栈的实现

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

代价比较小。

代码实现：

还是一样的我们分三个文件

Stack.h
Stack.c
test.c

Stack.h

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



// 这里的栈我们用动态顺序表实现 (也可以用静态顺序表实现[不好扩容和定义空间大小])

typedef int SLDataType;
typedef struct Stack
{
	SLDataType* _a;
	int _top; // 栈顶下标 [规定栈顶下标：最后一个有效数据的下一个位置]
	int _capacity; // 数组的有效空间大小 
}Stack;


// 栈的初始化
void StackInit(Stack* ps);

// 栈的销毁
void StackDestory(Stack* ps);

// 栈是能从栈顶  存数据或者取数据，因此不存在尾插头插之类的
// 入栈
void StackPush(Stack* ps, SLDataType x);

// 出栈
void StackPop(Stack* ps);

// 栈的数据个数获取
//int StackSize(Stack st); //其实理论上获取元素个数只需要传值调用就行 但是为了保持接口一致性，我们采用指针
int StackSize(Stack* ps);

// 获取栈顶元素
SLDataType StackTop(Stack* ps);

// 判断栈是否为空
int StackEmpty(Stack* ps); // 是空返回1  不是空的返回0

Stack.c

#include"Stack.h"

// 栈的初始化
void StackInit(Stack* ps)
{
	assert(ps); // ps不能为NULL

	// 栈的初始化
	/*ps->_a = NULL;
	ps->_top = 0;
	ps->_capacity = 0;*/

	// 除了上面这种初始化。也可以这样初始化
	SLDataType* tmp = (SLDataType*)malloc(sizeof(SLDataType) * 4); // 这样后面入栈时无需判断 空间是否为0 
	if (tmp == NULL)
	{
		perror("StackInit():malloc()");
		return;
	}

	ps->_a = tmp;
	ps->_top = 0;
	ps->_capacity = 4;
}

// 栈的销毁
void StackDestory(Stack* ps)
{
	assert(ps);

	free(ps->_a);
	ps->_a = NULL;

	ps->_top = ps->_capacity = 0;
}

// 入栈
void StackPush(Stack* ps, SLDataType x)
{
	assert(ps);

	// 插入之前 判断栈的空间是否足够新的数据插入
	if (ps->_top == ps->_capacity) // 判断空间是否足够 
	{
		int newcapacity = ps->_capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->_a, sizeof(SLDataType) * newcapacity); // 增容
		if (tmp == NULL) // 判断是否增容成功
		{
			perror("StackPush():realloc()");
			return;
		}

		// 更新栈
		ps->_a = tmp;
		ps->_capacity = newcapacity;
	}

	ps->_a[ps->_top] = x; // 入栈
	ps->_top++; // 让top记录的是栈顶 也就是最后一个数据的下一个位置
}

// 出栈
void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->_top > 0); // 栈里面要有数据才能出栈

	ps->_top--; // 让top--就行 最后一个数据的下标是 top - 1
}

// 栈的数据个数获取
int StackSize(Stack* ps)
{
	assert(ps);

	return ps->_top; // top代表栈顶下标，是最后的一个数据的下标 + 1  其实就是栈的数据个数
}

// 获取栈顶元素
SLDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->_top > 0); // 没有数据还怎么获取

	return ps->_a[ps->_top - 1]; // top是栈顶下标，top - 1才是最后一个数据的下标
}

// 判断栈是否为空
int StackEmpty(Stack* ps) // 是空返回1  不是空的返回0
{
	assert(ps);

	return ps->_top == 0 ? 1 : 0; // ps->pos只要为0就说明栈内没有数据了
	//return !ps->_top; // ps->top 为0 就返回1，为真就返回 0 ，除了0的数都是真
}

test.c

#include"Stack.h"

void TestStack()
{
	Stack st;
	StackInit(&st); // 测试初始化

	// 入栈
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);
	// 注意了栈不能像之前顺序表那样将其直接打印出来，想获得栈的数据，要从栈顶一个一个拿出来
	while (!StackEmpty(&st)) // 判断栈是否为空，不是空就可以打印
	{
		printf("%d ", StackTop(&st));// 取出栈顶数据 // 4 3 2 1
		StackPop(&st);// 想要拿到下一个数据就要把栈顶的数据弹出才能拿到
	}
	printf("\n");

	// 获取栈的数据个数
	int ret = StackSize(&st);
	printf("%d\n", ret);// 0 因为前面打印数据将数据都弹出栈了

	// 获取栈顶元素
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);
	SLDataType top = StackTop(&st);
	printf("%d\n", top); // 4

	//出栈
	StackPop(&st);
	StackPop(&st);
	while (!StackEmpty(&st)) // 判断栈是否为空，不是空就可以打印
	{
		printf("%d ", StackTop(&st));// 2 1
		StackPop(&st);// 想要拿到下一个数据就要把栈顶的数据弹出才能拿到
	}
	printf("\n");

	// 判断链表是否为空
	int back = StackEmpty(&st);
	if (back == 0)
		printf("不为空\n");
	else
		printf("空\n");

	// 栈的销毁
	StackDestory(&st);
}

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

栈的作用：
1.如果有后进先出的需求的地方，比如迷宫问题
2.递归改成非递归

2.队列

2.1队列的概念及结构

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

入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头

2.2 队列的实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。（因为每次出一个数据都要将数组后面整体往前移动）

代码实现：

我们分三个文件

Queue.h
Queue.c
test.c

Queue.h

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

// 这里的队列的底层数据结构是单链表
// 定义节点的结构体

typedef int QDataType;
typedef struct QueueNode
{
	QDataType _data;
	struct QueueNode* _next;
}QueueNode;

// 和单链表不一样的是队列最好要有指向第一个节点和尾节点的指针
typedef struct Queue
{
	QueueNode* _head;
	QueueNode* _tail;
}Queue;


// 队列的接口（也就是函数） 
// 为什么这里的接口和单链表的时候不一样，不需要传二级指针呢，因为我们把指针放到了结构体内部，传的是结构体指针
// 通过结构体指针找到结构体，再从结构体内部拿到节点的指针，再从这个节点指针找到节点，这里起到的作用就类似于二级指针

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

// 队列的销毁
void QueueDestory(Queue* pq);

// 入队
void QueuePush(Queue* pq, QDataType x);

// 出队
void QueuePop(Queue* pq);

// 获取队头的数据
QDataType QueueFront(Queue* pq);

// 获取队尾的数据
QDataType QueueBack(Queue* pq);

// 判断队列是否为空  [返回1就是空，返回0就是非空]
int QueueEmpty(Queue* pq);

// 获取队列的数据个数
int QueueSize(Queue* pq);

// 队列的打印
void QueuePrint(Queue* pq);

Queue.c

#include "Queue.h"

// 队列的初始化
void QueueInit(Queue* pq)
{
	assert(pq);//pq不能为NULL

	// 初始化
	pq->_head = NULL;
	pq->_tail = NULL;

}

// 队列的销毁
void QueueDestory(Queue* pq)
{
	assert(pq);

	// 遍历队列，删除每一个节点
	QueueNode* cur = pq->_head;
	while (cur) 
	{
		QueueNode* next = cur->_next;
		free(cur);
		cur = next;
	}

	pq->_head = pq->_tail = NULL;
}

// 入队
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);

	// 入队其实就是让新节点尾插到链表中
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("QueuePush():malloc()");
		exit(-1);
	}

	newnode->_data = x;
	newnode->_next = NULL;

	// 判断列队是否为空
	if (pq->_head == NULL)
	{
		pq->_head = pq->_tail = newnode;
	}
	else
	{
		// 尾插
		pq->_tail->_next = newnode;
		pq->_tail = newnode;
	}

}

// 出队
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->_head); // 队列是空的怎么出队

	// 头删
	QueueNode* next = pq->_head->_next; // 把第一个节点的下一个节点存储起来
	free(pq->_head);
	pq->_head = next;

	// 这里有个问题，当最后一个节点删除完之后，pq->_head = NULL
	// 但是pq->_tail 就变成野指针了
	if (pq->_head == NULL)
	{
		pq->_tail = NULL;
	}

}

// 获取队头的数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->_head);// 队列为空怎么获取队头数据

	return pq->_head->_data;
}

// 获取队尾的数据
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->_tail); // 等价于assert(pq->_head); 头为空，尾也肯定为空，

	return pq->_tail->_data;
}

// 判断队列是否为空 [返回1就是空，返回0就是非空]
int QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->_head == NULL ? 1 : 0;
}

// 获取队列的数据个数
int QueueSize(Queue* pq)
{
	assert(pq);

	// 遍历队列统计数据个数
	QueueNode* cur = pq->_head;
	int size = 0;
	while (cur)
	{
		size++;
	}

	return size;
}

// 队列的打印
void QueuePrint(Queue* pq)
{
	assert(pq);
	assert(pq->_head);

	while (!QueueEmpty(pq))
	{
		printf("%d ", QueueFront(pq));
		QueuePop(pq); // 从队头拿出一个数据要将其删除
	}
	printf("\n");
	
}

test.c

#include "Queue.h"

/*
队列的使用场景
1.先进先出的场景，比如保持序列公平，排队抽号机 
*/

void TestQueue()
{
	Queue q;
	// 队列的初始化
	QueueInit(&q);

	// 入队
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	//QueuePrint(&q);
	
	// 获取队头数据
	QDataType x = QueueFront(&q);
	printf("%d\n", x); // 1  队头的数据是1

	// 获取队尾数据
	QDataType y = QueueBack(&q);
	printf("%d\n", y); // 4 队尾的数据是4

	// 出队
	QueuePop(&q);
	QueuePop(&q);
	QueuePrint(&q);

	// 获取队列数据个数
	int size = QueueSize(&q);
	printf("%d\n", size); // 0 因为前面打印的时候调用数据删除完了

	// 队列的销毁
	QueueDestory(&q);
}



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