【数据结构】——栈|队列（基本功能）

栈

基本概念

栈的常见基本操作

栈的存储

✌栈的基本操作实现

栈的构建

栈的初始化

入栈

打印栈

出栈

获取栈顶元素

获取栈的有效元素个数

判断栈是否为空

销毁栈

队列

基本概念

队列的常见基本操作

✌队列的基本操作实现

队列的构建

初始化

入队列

出队列

获取头部元素

获取队尾元素

获取有效元素个数

判断是否为空

销毁队列

栈

基本概念

定义： 是只允许在一端进行插入或删除的线性表；

栈顶：线性表允许进行插入删除的那一端。
空栈：不含任何元素的空表。

栈是先进后出的的线性表

栈的常见基本操作

InitStack(&S)： 初始化一个空栈S。
StackEmpty(S)：        判断一个栈是否为空，若栈为空则返回true，否则返回false。
Push(&S, x)：             进栈（栈的插入操作），若栈S未满，则将x加入使之成为新栈顶。
Pop(&S, &x)：   出栈（栈的删除操作），若栈S非空，则弹出栈顶元素，并用x返回。
GetTop(S, &x)： 读栈顶元素，若栈S非空，则用x返回栈顶元素。
DestroyStack(&S)：    栈销毁，并释放S占用的存储空间（“&”表示引用调用）。

栈的存储

栈的存储方式有两种：顺序栈和链栈，即栈的顺序存储和链式存储。

采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的元素，同时附设一个指针（top）指示当前栈顶的位置。

✌栈的基本操作实现

栈的构建

因为使用的是顺序栈，所以可以定义动态增长的数组，既然是数组了，自然有空间是否足够的问题，所以要定义个容量 capacity，栈顶top

// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
	STDataType* arr;	
	int top;		// 栈顶
	int capacity;  // 容量 
}Stack;

栈的初始化

这里的top可以定义成0或者-1，不过后面的操作需要稍微变化；

// 初始化栈 
void StackInit(Stack* ps)
{
	assert(ps);
	assert(ps);
	ps->arr = NULL;
	ps->capacity = 0;
	ps->top = -1;	//表示栈顶元素
}

入栈

这里注意top的不同，因为是顺序栈，所以要检查容量是否足够

// 入栈 
void StackPush(Stack* ps, STDataType data)
{
	//检查容量
	if (ps->top + 1 == ps->capacity)	//top表示的是栈顶元素，先++top,再插入的，所以检查+1位置是否可用
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* newnode = (STDataType*)realloc(ps->arr,sizeof(STDataType) * newcapacity);
		assert(newnode);	//七匹狼式检查是否开辟成功
		ps->arr = newnode;
		ps->capacity = newcapacity;
	}
	ps->top++;
	ps->arr[ps->top] = data;
}

打印栈

//打印
void StackPrint(Stack* ps)
{
	assert(ps);
	int i = ps->top;
	while (i>=0)
	{
		printf("%d ", ps->arr[i]);
		i--;
	}
	printf("\n");
}

出栈

// 出栈 
void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->top >= 0);
	ps->top--;
}

获取栈顶元素

// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->top >= 0);
	return ps->arr[ps->top];
}

获取栈的有效元素个数

// 获取栈中有效元素个数 
int StackSize(Stack* ps)
{
	assert(ps);
	assert(ps->top >= 0);
	return ps->top + 1;
}

判断栈是否为空

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
bool StackEmpty(Stack* ps)
{
	assert(ps);
	if (ps->top < 0)	//为空
	{
		return true;
	}
	else
	{
		return false;
	}
}

销毁栈

// 销毁栈 
void StackDestroy(Stack* ps)
{
	assert(ps);
	ps->capacity = 0;
	ps->top = -1;
	free(ps->arr);
	ps->arr = NULL;
}

队列

基本概念

定义：队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

队列是一种先进先出（First In First Out）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。

队列的常见基本操作

InitQueue(&Q)： 初始化队列，构造一个空队列Q。
QueueEmpty(Q)：        判队列空，若队列Q为空返回true，否则返回false。
EnQueue(&Q, x)： 入队，若队列Q未满，将x加入，使之成为新的队尾。
DeQueue(&Q, &x)：     出队，若队列Q非空，删除队头元素，并用x返回。
GetHead(Q, &x)：        读队头元素，若队列Q非空，则将队头元素赋值给x。

✌队列的基本操作实现

队列的构建

typedef int QueueDataType;
// 链式结构：表示队列 
typedef struct QueueNode
{
	QueueDataType val;
	struct QueueNode* next;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;	//队列的长度大小
}Queue;

初始化

// 初始化队列 
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
	pq->size = 0;
}

入队列

// 队尾入队列 
void QueuePush(Queue* pq, QueueDataType data)
{
	assert(pq);
	//开辟空间
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)	//检查是否开辟成功
	{
		perror("malloc fail");
		return;
	}
	newnode->val = data;
	newnode->next = NULL;

	if (pq->tail == NULL)	//空队列情况
	{
		pq->tail = pq->head = newnode;	
	}
	else
	{
		pq->tail->next = newnode;	//链接新结点
		pq->tail = newnode;		//队尾 更新位置
	}
	pq->size++;		//长度+
}

出队列

// 队头出队列 
void QueuePop(Queue* pq)
{
	assert(pq);
	QNode* tmp = pq->head;
	pq->head = pq->head->next;

	free(tmp);
	tmp = NULL;

	if (pq->head == NULL) //此时链表已经为空，队尾tail是野指针
	{
		pq->tail = NULL;
	}
	pq->size--;
}

获取头部元素

// 获取队列头部元素 
QueueDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);	//检查队头，不为空说明有数据存放
	return pq->head->val;
}

获取队尾元素

// 获取队列队尾元素 
QueueDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->tail);	//检查队尾，不为空说明有数据存放
	return pq->tail->val;
}

获取有效元素个数

// 获取队列中有效元素个数 
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

判断是否为空

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}

销毁队列

// 销毁队列 
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* tmp = pq->head;
	while (tmp)
	{
		QNode* next = tmp->next;
		free(tmp);
		tmp = NULL;
		tmp = next;
	}
	pq->head = pq->tail = NULL;
	pq->size = 0;
}