【数据结构】栈和队列

【数据结构】栈和队列（vs）

前言：

栈和队列是两种重要的线性结构。本章讨论栈和队列的定义、表示方法。这里栈和队列分别用数组实现和链表实现（这里所说是实现的底层逻辑分别是数组结构和链表结构）

一、栈

1.1概念与结构

栈是一种特殊的线性表，只允许在固定的一端进行插入和删除操作，进行数据插入和删除的一端称为栈顶和栈底。（可得出，栈是先进后出LIFO）

压栈：栈的插入操作，入数据在栈顶

出栈：栈的删除操作，出数据也在栈顶

1.2用数组的结构实现栈（vs）：

头文件：stack.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int STDatatype;
typedef struct Stack
{
	STDatatype* arr;
	int top;//元素个数
	int capacity;
}ST;

//初始化
void STInit(ST* ps);
//销毁
void STDestroy(ST* ps);

//判空
bool STEmpty(ST*ps);

//入栈&出栈
void STPush(ST* ps, STDatatype x);
void STpop(ST* ps);

//取栈顶元素
STDatatype StackTop(ST* ps);

//获取栈中有效元素个数
int STSize(ST* ps);

实现栈的基本功能：初始化栈、入栈和出栈、获取栈的元素、销毁栈等：

• 初始化：创建一个空栈，设置栈顶指针为初始化状态。

void STInit(ST* ps)
{
	assert(ps);
	ps-> arr = NULL;
	ps->top = ps->capacity = 0;
}

• 栈的销毁：将栈顶指针恢复到初始状态，释放栈中所有元素占用的空间。

void STDestroy(ST* ps)
{
	assert(ps);
	if (ps->arr)
	{
		free(ps->arr);
	}
	ps->arr = NULL;
	ps->top = ps->capacity = 0;
}

• 入栈和出栈：

void STPush(ST* ps, STDatatype x)
{
	assert(ps);
    //看空间是否足够，不够就申请
	if (ps->capacity == ps->top)
	{
		int newCapacity = ps->capacity = 0 ? 4 : 2 * ps->capacity;
		STDatatype* tmp = (STDatatype*)realloc(ps->arr, sizeof(STDatatype) * newCapacity);
		if (tmp == NULL)
		{
			perror("reallloc fail!");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
	ps->arr[ps->top++] = x;

}
//这里是判空操作
bool STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

void STPop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));

	--ps->top;
}

• 获取栈顶的元素：可在不删除栈顶元素的情况下，返回栈顶元素的值。获取元素个数，直接取ps->top。

//获取栈顶元素
STDatatype StackTop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));

	return ps->arr[ps->top - 1];
}
//获取元素个数
int STSize(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));
	return ps->top;
}

二、队列

2.1概念与结构

概念：只允许在一端进行插入数据操作，在另一端进行删除操作的特殊线性表，具有先进先出特点。

入队列：进行插入操作的一端称为队尾。

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

队列的底层结构

2.2用链表结构实现队列（vs）：

头文件：Queue.h

//定义队列节点的结构.
typedef int QDataType;
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QueueNode;

typedef struct Queue
{
	struct QueueNode* phead;
	struct QueueNode* ptail;
	int size;//保存队列有效数据个数..
}Queue;

//初始化.
void QueueInit(Queue* pq);

//入队列，从队尾
void QueuePush(Queue* pq, QDataType x);

//队列判空.
bool QueueEmpty(Queue* pq);

//出队列，从队头
void QueuePop(Queue* pq);

//取对头数据
QDataType QueueFront(Queue* pq);
//取队尾数据
QDataType QueueBack(Queue* pq);

//队列有效元素个数
int QueueSize(Queue* pq);

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

实现队列的基本操作：初始化、出入队列操作、获取队列的长度、销毁队列。

• 初始化队列，创建一个空的队列、设置队头指针和队尾指针为初始状态。

//初始化.
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

• 入队列：将元素插到队尾，若队列为空，则将插入的数据作为初始的队头队尾指针元素，若不为空，则将队尾指针更新指向新插入的元素。

//入队列，队尾.
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	//申请一个新节点
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);

	}
	newnode->data = x;
	newnode->next = NULL;

	if (pq->phead == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = pq->ptail->next;
	}
	pq->size++;
}

• 出队列：首先先判空，若队列为空，无法进行出队操作，通常会返回一个特定的错误值或进行错误处理；若队列中只有一个元素，删除该元素后，队头指针和队尾指针都恢复到初始状态；若有多个元素，删除队头元素后，队头指针指向下一个指针。

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->phead == NULL && pq->ptail == NULL;
}

//出队列，队头
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	if (pq->phead == pq->ptail)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		QueueNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}
	--pq->size;
}

• 取队头队尾数据：首先判空，若队列为空，则不再执行下面的代码。

//取队头数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->phead->data;
}

//取队尾元素
QDataType QUeueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->ptail->data;
}

• 获取队列有效元素个数：这里用的是链表结构实现队列，所以直接取元素个数就可以了。

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

• 销毁队列：将队头队尾指针恢复到初始状态，释放队列中所有元素占用的内存。

//销毁队列
void QueueDestroy(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	QueueNode* pcur = pq->phead;
	while (pcur)
	{
		QueueNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}