数据结构 栈与队列详解！！

一.栈

 关于内存中的栈和数据结构中的栈是不同的，本章着重讲的是数据结构的栈。

 这是一张关于栈的表达图。从图中可以看出栈很像是一副卡牌，发牌时只能从上取出，即出栈。

而入栈则是像你出牌后，要把你出的牌压在上一张出的牌上面。这是入栈。

栈可以用链表或者顺序表实现，这里采用的是顺序表的结构。

1.栈的头文件 

#pragma once
#include
#include
#include
#include
typedef int StackDatatype;
typedef struct Stack
{
	StackDatatype* data;
	int capacity;
	int Top;
}ST;
void STPush(ST* pst, StackDatatype x);
void StackInit(ST* pst);
void StackDestroy(ST* pst);
void Push(ST* pst, StackDatatype x);
void Pop(ST* pst);
StackDatatype StackTop(ST* pst);
int StackSize(ST* pst);
bool StackEmpty(ST* pst);

 2.栈的初始化

void StackInit(ST* pst)
{
	assert(pst);
	pst->capacity = 0;
	pst->data = NULL;
	pst->Top = -1;
}

这里的pst->Top可以用-1，或者0.用-1的话后续你的pst->Top 所代表的下标就是栈顶元素。

如果用0 那pst-Top 之后的下标就是栈顶元素的下一个位置。这里可以自己考虑，代码的多样性。 （本章采用的是-1 的写法）

3.栈的插入

void Push(ST* pst, StackDatatype x)
{
	assert(pst);
	pst->Top++;
	JudgeCapacity(pst);
	pst->data[pst->Top] = x;
}

栈的插入就是入栈，top++ 是pst->top 指向当前即将插入元素的位置（栈顶的位置）。

后面在判断pst中的容量，不够需要扩容。把x 插入栈顶位置。 

4.栈的取出

void Pop(ST* pst)
{
	assert(pst);
	assert(pst->Top > -1);
	pst->Top--;
}

和顺序表一样只要 top--即可，不用删除，因为top -- 以后，你下次在使用该位置的时候，其实就是把原来这个位置的元素更改就可以了，不需要删除。

5.栈的栈顶元素

StackDatatype StackTop(ST* pst)
{
	assert(pst);
	return pst->data[pst->Top];
}

 这个函数的存在意义就是取当前的栈顶元素的值。

6.栈的元素个数

int StackSize(ST* pst)
{
	assert(pst);
	return pst->Top+1;
}

因为我们的Top 用的是-1开头，所以,当它指向第一个元素的时候，这时候Top == 0， 所以加一。

7.栈的判空

bool StackEmpty(ST* pst)
{
	assert(pst);
	return pst->Top == -1;
}

判断栈此时是否为空，用pst- top == -1 的判断表达式返回即可。 

8.栈的销毁

void StackDestroy(ST* pst)
{
	assert(pst);
	free(pst->data);
	pst->data = NULL;
	pst->capacity = 0;
    pst->Top = -1;
}

因为栈是创建出来的一个空间。所以最后要将这段空间free，并将所有数据都置空 

栈的容量判断

void JudgeCapacity(ST* pst)
{
	assert(pst);
	if (pst->capacity == pst->Top)
	{
		int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
		StackDatatype* tmp = (StackDatatype*)realloc(pst->data, sizeof(StackDatatype) * newcapacity);
		if (tmp == NULL)
		{
			perror("malloc failed!");
			return;
		}
		pst->data = tmp;
		pst->capacity = newcapacity;
	}
}

 和顺序表的容量判断一样，有兴趣的可以直接去看我的顺序表详解，这里给大家简单的说一下，用三目表达式判断并赋值newcapacity，然后扩容pst->data这一段空间。

最后把扩容好的空间地址给到tmp，newcapacity给到原来的capacity。

二.队列

 上图是队列的表达图，队列如字意就像是排队一样，先进入的人，就先获得服务。

所以 队列和 栈的不同点就是出栈和出队，队列出的是头元素，而栈出的是尾元素（栈顶）

对比入队和 入栈两者相似都是尾插。

，还有队列用的是链表，栈用的是顺序表。

1.队列的头文件

#pragma once
#include
#include
#include
#include
 
typedef int QeDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QeDataType data;
}Qnode;
typedef struct Queue
{
	Qnode* head;
	Qnode* back;
}Qe;
void QueueInit(Qe* q);
void QueueDestroy(Qe* q);
void Queuepush(Qe* q, QeDataType x);
void QueuePop(Qe* q);
QeDataType QueueFront(Qe* q);
QeDataType QueueBack(Qe* q);
int QueueSize(Qe* q);
bool QueueEmpty(Qe* q);

 相比栈 队列多用了一个typedef 原因是，队列要记录头元素和尾元素。因为入队入的在尾部，出队出的是头部

2.队列的初始化

void QueueInit(Qe* q)
{
	assert(q);
	Qnode* newnode = CreateNode(-1);
	q->head = newnode;
	q->back = newnode;
}

 这里采用的是有头结点的队列，当然没有头结点（哨兵位）也是可以的，根据个人喜好选择。

初始化创立一个头结点（哨兵位）后，头指针和尾指针都指向头结点（哨兵位）

3.队列的插入

void Queuepush(Qe* q, QeDataType x)
{
	assert(q);
	Qnode* newnode = CreateNode(x);
	q->back->next = newnode;
	q->back = newnode;
}

 关于队列的插入，就是链表的尾插，如果链表还没明白的朋友，可以去看我之前关于单链表的博客。

4.队列的取出

void QueuePop(Qe* q)
{
	assert(q);
	assert(q->head->next);
 
	Qnode* next = q->head->next;
	q->head->next = next->next;
	free(next);
	next = NULL;
	if (q->head->next == NULL)
	{
		q->back = q->head;
		q->back->next = NULL;
	}
}

关于队列的取出，实质上就是链表的头删。 

5.队列的头元素

QeDataType QueueFront(Qe* q)
{
	assert(q);
	assert(q->head->next);
	return q->head->next->data;
}

 队列的头元素返回就是返回哨兵位后的第一个节点的数据。因为要返回数值，所以这个第一个节点不能为空，用assert断言。

6.队列的尾元素

QeDataType QueueBack(Qe* q)
{
	assert(q);
	assert(q->head->next);
	return q->back->data;
}

 既然要返回尾元素的数据，那就是用到尾指针，当然链表第一个节点不能为空。

7.队列的元素个数

int QueueSize(Qe* q)
{
	Qnode* size = q->head->next;
	int num = 0;
	while (size)
	{
		size = size->next;
		num++;
	}
	return num;
}

队列的元素个数，就把链表遍历一遍，用num记录遍历次数，就是元素个数。 

8.队列的判空

bool QueueEmpty(Qe* q)
{
	return q->head->next == NULL;
}

 队列的判空就是判断第一个节点是否为空，return 一个 表达式即可，也可以用if else 语句。因人而异。

创造一个节点

Qnode* CreateNode(QeDataType x)
{
	Qnode* newnode = (Qnode*)malloc(sizeof(Qnode));
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

 创造一个节点在链表的初始化和插入都会用到，在之前链表的那篇博客有讲到，偏简单。