【数据结构】栈和队列详解

//定义一个栈  底层使用数组实现
typedef int STDataType;
typedef struct stack
{
	STDataType* arr;
	int top;//栈顶 也是有效的数据个数
	int capacity;//栈的容量
}ST;

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

//初始化
void StackInit(ST* ps)
{
	assert(ps);
	ps->arr = NULL;//一开始指针先初始化为NULL空指针
	ps->top = ps->capacity = 0;
}

//入栈---栈顶
void StackPush(ST* ps, STDataType x);

//入栈——栈顶
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->capacity == ps->top)//有效数据等于容量大小时 说明栈满了
	{
		//增容
		STDataType newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//前面那个4是默认给的大小
		STDataType* tmp = (STDataType*)realloc(ps->arr, newcapacity * (sizeof(STDataType)));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		//到这说明开辟成功了
		//更新容量和地址
		ps->arr = tmp;//将新开辟空间的地址给arr
		ps->capacity = newcapacity;
	}
	ps->arr[ps->top++] = x;
}

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

//判断栈是否为空
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top==0;//返回栈顶就知道是否为空了

}

//出栈——栈顶
void StackPop(ST* ps);

//出栈——栈顶 相当于删除元素
void StackPop(ST* ps)
{
	assert(ps);
	//判断是否为空
	if (!StackEmpty(ps))
	{
		//跟顺序表一样减少有效数据个数(栈顶)即可
		--ps->top;
	}
}

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

//取栈顶元素
STDataType StackTop(ST* ps)//返回值是元素的类型
{
	//判断是否为空
	assert(!StackEmpty(ps));
	//每次取完 有效数据个数减减 栈顶减减
	return ps->arr[ps->top-1];//下标减一才能取得对应的元素
}

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

//获取栈中有效元素个数
int StackSize(ST* ps)
{
	return ps->top;//有效的元素个数 即栈顶
}

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

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

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

//定义队列 实际上就是定义两个指针 头指针 尾指针
typedef struct Queue
{
	QueueNode* phead;                    //两个指针指向头结点和尾结点
	QueueNode* ptail;
	//int size;
}Queue;

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

//初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	//给队列中的两个指针都初始化为空
	pq->phead = pq->ptail = NULL;
}

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

//队列判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->phead == pq->ptail;

}

//入队——队尾  再尾部插入数据
void QueuePush(Queue* pq, QDataType x)

//入队——队尾  再尾部插入数据
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 = newnode;//或pq->ptail=pq->ptail->next
		
	}
	//pq->size++;

}

//出队——队头
void QueuePop(Queue* pq);

//出队——队头
void QueuePop(Queue* pq)
{
	assert(!QueueEmpty(pq));
	//单个结点的情况
	if (pq->phead = pq->ptail)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
		
	}
	else//多个结点的情况
	{
		QueueNode* next = pq->phead->next;//这里创建next指针要用QueueNode来创建 因为使用的是结点
		free(pq->phead);
		pq->phead = next;
		
	}
	//pq->size--;
}

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

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


//取队尾数据
QDataType QueueBack(Queue* pq)
{
	//判空
	assert(!QueueEmpty(pq));
	return pq->ptail->data;
}

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

//队列有效元素个数
int QueueSize(Queue* pq)
{
	assert(pq);
	//方法一：遍历链表——适用于不会频繁调用队列有效数据个数的场景
	QueueNode* pcur = pq->phead;
	int size = 0;
	while (pcur != NULL)
	{
		size++;
		pcur = pcur->next;
	}
	return size;
	
	//方法二：初始时创建一个记录有效数据的变量——适用于频繁调用队列有效数据个数的场景
	//return pq->size;
}

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

//销毁队列
void QueueDestroy(Queue* pq)
{
	assert(pq);
	//队列底层是链表 链表的销毁要循环销毁
	QueueNode* pcur = pq->phead;
	while (pcur != NULL)
	{
		QueueNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	//走到这所有的结点都已经被释放了 此时队列的两个指针要置空
	pq->phead = pq->ptail = NULL;
	//将队列有效数据个数归零
	//pq->size = 0;
}