C语言分别实现栈和队列详解流程

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;  
	int top;       //栈顶
	int capacity;  //容量
}Stack;

void StackInit(Stack* ps)
{
	assert(ps);//检测传过来的ps是否为空
	ps->a = NULL;//把a标识的这块空间先置为空
	ps->top = ps->capacity = 0;
}

void StackPush(Stack* ps, STDataType x)
{
	assert(ps);//检测ps是否为空

	//如果空间满了，我们需要扩容
	if (ps->capacity == ps->top)//判断空间是否满了的条件
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//指定新空间的大小
		ps->a = (STDataType*)realloc(ps->a, newCapacity*sizeof(STDataType));//进行扩容
		if (ps->a == NULL)//扩容失败
		{
			printf("realloc fail\n");
			exit(-1);//终止程序
		}
		ps->capacity = newCapacity;//让其标识新的空间的大小
	}
	ps->a[ps->top] = x;//将数据放入栈
	ps->top++;//top向后走一步
}

void StackPop(Stack* ps)
{
	assert(ps);
	if (ps->top > 0)//避免栈里面数据已经删除完了，top依旧向下减为负数
	{
		--ps->top;
	}
}

STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->top > 0);//保证下标为正
	return ps->a[ps->top - 1];//返回栈顶元素
}

int StackSize(Stack* ps)
{
	assert(ps);
	return ps->top;
}

bool StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;//如果条件成立就返回真，否则就为假（不为空）
}

void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->a);//释放开辟的这一块空间
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

typedef int QDataType;
//链式结构：表示队列
typedef struct Queuenode
{
	QDataType data;           //存储数据
	struct QueueNode* next;   //指针域
}QNode;
//队列的结构
typedef struct Queue
{
	QNode* head;//标识队头的位置
	QNode* tail;//标识队尾的位置
}Queue;

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;//将两个指针置为空
}

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));//申请一个新的结点
	assert(newnode);//检测结点是否申请成功
	newnode->data = x;//
	newnode->next = NULL;
	if (pq->tail == NULL)//如果队列为空的情况
	{
		assert(pq->head==NULL);
		pq->tail = pq->head = newnode;
	}
	else//队列不为空的情况
	{
		pq->tail->next = newnode;//尾插一个新结点
		pq->tail = newnode;//更新尾的位置
	}
}

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head && pq->tail);//保证队列中有数据在往下走
	if (pq->head->next == NULL)//如果队列里面只有一个数据的情况
	{
		free(pq->head);//释放队头数据
		pq->head = pq->tail = NULL;//将队列的头指针和尾指针均置为空
	}
	else
	{
		QNode* next = pq->head->next;//让next指向队头结点的下一个结点
		free(pq->head);//释放队头结点
		pq->head = next;//让head指向next结点
	}
}

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);//检测队列是否为空
	return pq->head->data;//返回队列头部元素
}

//获取队列队尾元素
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->tail);//检测队列是否为空
	return pq->tail->data;//返回队列尾部元素
}

int QueueSize(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;//让cur指向队头的元素
	size_t size = 0;//定义一个无符号的size变量用来计数
	while (cur)//cur不为空则进入循环继续执行
	{
		size++;//size=size+1
		cur = cur->next;//继续向后遍历
	}
	return size;//返回有效元素个数
}

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

void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;//定义一个next指向cur的下一个结点
		free(cur);//释放cur
		cur = next;
	}
	pq->head = pq->tail = NULL;//将头尾指针均置为空
}