数据结构----栈和队列

栈，线性表的一种特殊的存储结构。与学习过的线性表的不同之处在于栈只能从表的固定一端对数据进行插入和删除操作，另一端是封死的。由于栈只有一边开口存取数据，称开口的那一端为“栈顶”，封死的那一端为“栈底”（类似于盛水的木桶，从哪进去的最后还得从哪出来）。

1. 数据元素用栈的数据结构存储起来，称为“入栈”，也叫“压栈”。
2. 数据元素由于某种原因需要从栈结构中提取出来，称为“出栈”，也叫“弹栈”。

注意：栈遵循先进后出原则

1.3.栈的表示方式

既然栈也是线性表，那么它就同样有线性表的两种表示形式： 顺序（数组）和 链式栈。

接下来就来实现这几大功能

#pragma once
#include
#include
#include
#include
#include

typedef int SLDateType;
typedef struct Stack
{
	SLDateType* a;
	int top;     //栈顶
	int capacity;   //内存
}ST;

//初始化
void StackInit(ST* ps);

//销毁
void StackDestroy(ST* ps);

//插入
void StackPush(ST* ps, SLDateType x);

//删除
void StackPop(ST* ps);

//返回栈顶值
void StackTop(ST* ps);

//判断是否为空
bool StackEmpty(ST* ps);

//计算栈长
int StackSize(ST* ps);

注意，我们通过数组栈实现，所以在结构体中定义一个top(栈顶），一个动态内存。

//初始化
void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

//销毁
void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

初始化和销毁就这两步啊给指针a赋值NULL，给剩下俩赋值为0，

 销毁就是释放指针，给那俩赋值为0。

//插入
void StackPush(ST* ps, SLDateType x)
{
	assert(ps);
	if (ps->top == ps->capacity)//判断容量
	{
		int newcapacity = (ps->capacity == 0 ? 4 : 2 * ps->capacity);//扩容后的容量
		SLDateType* tmp = realloc(ps->a, sizeof(SLDateType) * newcapacity);//扩容
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->capacity = newcapacity;
		ps->a = tmp;
	}
	ps->a[ps->top] = x ;//压入数据
	ps->top++;
}

最后一步压入数据是往结构体的a中压入的，又因为a是结构体指针，所以a中有top，所以把要插入的值存在top中，然后top++。

至于那个ps->a=tmp是把开辟好的地址给ps->a。 

//删除
void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}

//判断是否为空
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

注意bool的头文件

//返回栈顶值
SLDateType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];
 }

//计算栈长
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

注意:队列是先进先出。

 一般我们用链来实现队列。

//初始化
void QueueInit(Queue* pd)
{
	assert(pd);
	pd->head = pd->tail = NULL;
}

//销毁
void QueueDestroy(Queue* pd)
{
	assert(pd);
	QNode* cur = pd->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pd->head = pd->tail = NULL;
}

//判空
int QueueEmpty(Queue* pd)
{
	if (pd->head == NULL)
	{
		return 1;
	}
	else
		return 0;
}

//入列
void QueuePush(Queue* pd, QDateType x)//入列
{
	assert(pd);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		printf("malloc:falue");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;

	//一个没有就进行插入
	if (pd->tail == NULL)
	{
		pd->head = pd->tail = newnode;
	}

	else
	{
		pd->tail->next = newnode;
		pd->tail = newnode;
	}
	
}

//出列
void QueuePop(Queue* pd)
{
	assert(pd);
	assert(!QueueEmpty(pd));
	if (pd->head->next == NULL)
	{
		free(pd->head);
		pd->head = pd->tail = NULL;
	}
	else
	{
		QNode* next = pd->head->next;   //保存下一个节点地址，防止找不到
		free(pd->head);
		pd->head = next;
	}
}

//返回队首
void QueueFront(Queue* pd)
{
	assert(pd);
	assert(!QueueEmpty(pd));
	return pd->head->data;
}

//返回队尾
void QueueBack(Queue* pd)
{
	assert(pd);
	assert(!QueueEmpty(pd));
	return pd->tail->data;
}

这个返回首尾是看一位大佬的代码的临时启发，希望对各位有用。

一些代码没加备注，我认为各位都学到了这了，这些代码随便就来，就没写来凑字了。

总结：栈和队列都能用顺序表（数组）和链表来表示。再想想，这俩不就是链表的特殊情况吗，栈是后进先出，队列是先进先出，而链表（单，循环）是啥时候进出都可以，这不就是长方形里的正方形吗。