数据结构（四）----栈和队列

这一节我们要讨论的是栈和队列，它们总是成对出现，因为它们的存储方式正好相反。

栈

什么是栈

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

栈的实现

首先需要考虑，要实现一个栈需要怎样的存储方式，也就是用数组还是链表来实现。理论上来说，这两种都可以，但是我们选择数组，这是因为我们把数组尾部作为栈顶时经常要进行尾插（压栈），而这一操作用数组实现代价比较小。
当然，由于我们需要压栈和出栈，自然选择动态数组而不是静态的

栈的结构(头文件)

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>//返回bool类型需要包含的头文件
typedef int STDataType;

typedef struct Stack
{
	STDataType* Stack;//数组
	int top;//栈顶，同时也可表示数量
	int capacity;//栈的容量
}ST;

void Stackpush(ST* st, STDataType x);

void StackInit(ST* st);

void StackPop(ST* st);

STDataType GetStackTop(ST* st);

void StackPrt(ST* st);

void StackDestroy(ST* st);

bool IsStackEmpty(ST* st);

int StackNum(ST* st);

初始化

void StackInit(ST* st)
{
	assert(st);
	st->top = 0;//栈顶
	st->capacity = 0;
	st->Stack = NULL;
}

这里栈顶st->top也可以定义为-1，定义为-1时可以用st->Stack[st->top]找到栈顶，定义为0时表示栈顶下一个，也表示栈的数据

压栈

对于栈而言，没有头插和尾插，只有压栈，因为这个结构只允许从栈顶操作数据

void Stackpush(ST* st, STDataType x)
{
	assert(st);//不能是空栈
	if (st->capacity == st->top)//判断是否容量不足、扩容，注意top定义为0/1的不同
	{
		int newcapacity = st->capacity > 0 ? 2 * st->capacity : 4;
		STDataType* tmp = (STDataType*)realloc(st->Stack, sizeof(STDataType) * newcapacity);
		st->capacity = newcapacity;
		st->Stack = tmp;

	}
	st->top++;
	st->Stack[st->top - 1] = x;//如果把最后两行换位则不需要-1
}

这里压栈操作和顺序表尾插类似，不懂的可以移步顺序表

出栈

和顺序表尾删类似，

void StackPop(ST* st)
{
	assert(st);
	assert(st->top>0);//有数据才能删
	st->top--;
}

取栈顶数据

这个函数是前两个线性表没有的，因为对于栈这个接口最常用，比如在打印的时候

STDataType GetStackTop(ST* st)
{
	assert(st);
	assert(st->top > 0);//栈不空才能取
	return st->Stack[st->top - 1];//top-1才是栈顶
}

判断是否为空

前面好多操作都需要判断是否空栈，这里直接写成接口

bool IsStackEmpty(ST* st)
{
	assert(st);
	if (st->top > 0)
	{
		return false;
	}
	else return true;
}

这里用到了bool类型，bool类型只有true和false两个值，代表真/假，也是1/0

打印函数

void StackPrt(ST* st)
{
	assert(st);
	assert(st->top > 0);
	for (int i = st->top-1; i >=0 ; i--)//从栈顶开始打印，这里最好不要直接对top进行修改
	{
		printf("%d ", st->Stack[i]);
	}
	printf("\n");
}

销毁栈

void StackDestroy(ST* st)
{
	assert(st);
	free(st->Stack);
	st->Stack = NULL;
	st->capacity = 0;
	st->top = 0;
}

读者可以自行进行测试，检验自己写的栈有没有bug

队列

什么是队列

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

队列的实现

和栈一样，我们也要首先进行选择：使用数组还是链表。这里使用链表其实更优，因为队列要对队首和队尾进行操作，如果是数组，在队首操作需要移动大量数据，所以这里选择链表

定义

//Queue.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int STDataType;

//队列结点，同单链表结点
typedef struct Queue
{
	struct Queue* next;
	STDataType data;
}QN;

//队列
typedef struct Queue
{
	QN* head;//队头
	QN* tail;//队尾

}Queue;

void QueueInit(Queue * q);

void QueuePush(Queue * q, STDataType x);

void QueuePop(Queue * q);

void QueuePrt(Queue * q);

STDataType GetQueueHead(Queue * q);

STDataType GetQueueTail(Queue * q);

int GetQueueLen(Queue * q);

bool IsQueueEmpty(Queue * q);

这里和之前的数据结构有很大不同，首先是有队列和队列结点两个结构体，在链表中，一个头结点就可表示整个链表，但是在这里最好定义一个队列结构，其中包含队首和队尾两个结点，因为我们对这两个结点的操作比较频繁，所以有必要这样定义。具体结构如下图：

初始化

void QueueInit(Queue* q)
{
	assert(q);//对一个队列进行初始化
	q->head = NULL;
	q->tail = NULL;
}

出入队

//入队
void QueuePush(Queue* q, STDataType x)
{
	assert(q);
	QN* newnode = (QN*)malloc(sizeof(QN));
	newnode->data = x;
	newnode->next = NULL;
	if (q->head == NULL)
	{
		q->head = q->tail = newnode;
	}
	else
	{
		q->tail->next = newnode;//旧队尾后插newnode
		q->tail = newnode;//newnode新队尾
	}
}
//出队	
void QueuePop(Queue* q)
{
	assert(q);
	assert(q->head);
	
	QN* cur = q->head;
	q->head = q->head->next;
	free(cur);//先找到头的下一个再删除头

	if (q->head == NULL)//如果删除了最后一个数据，那么一起置空，否则队尾是野指针（被释放了）
	{
		q->tail == NULL;

	}

取队头和队尾

STDataType GetQueueHead(Queue* q)
{
	assert(q);
	assert(q->head);//保证有数据
	return q->head->data;
}

STDataType GetQueueTail(Queue* q)
{
	assert(q);
	assert(q->head);
	return q->tail->data;
}

其他函数

//队列长度
int GetQueueLen(Queue* q)
{
	assert(q);
	int count = 0;
	QN* cur = q->head;
	while (1)//队头到队尾遍历
	{
		count++;
		if (cur == q->tail) break;
		cur = cur->next;
	}
	return count;
}

//判空
bool IsQueueEmpty(Queue* q)
{
	assert(q);
	if (!q->head)
		return true;
	return false;
}

//打印队列
void QueuePrt(Queue* q)
{
	assert(q);
	QN* cur = q->head;
	while (1)//遍历打印
	{
		printf("%d ", cur->data);
		if (cur == q->tail) break;
		cur=cur->next;
	}
	printf("\n");
}

测试的时候记得包头文件Queue.h哦
栈和队列也要多加练习才能深刻掌握。