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

什么是栈

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素的操作。进行数据插入和删除的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守先进后出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

栈的结构图示

栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。

创建栈的结构体

我们用栈来存储数据，首先需要实现一个动态增长的栈。所以我们先创建一个栈的结构体。

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;
}

入栈

一开始top为0标识栈顶的位置，所以我们要先将数据放入栈顶，在让top向后走一位。

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;
}

检测栈是否为空

检测栈是否为空，如果为空返回非零结果，如果不为空则返回0.

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;
}

什么是队列？

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO（First In First Out）入队列：进行插入操作的一端称为队尾出队列：进行删除操作的一端称为对头。

队列的实现

队列也可以用数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

创建队列结构体

我们使用链表来实现队列，我们需要创建一个存储队列信息的结构体。

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;//返回队列尾部元素
}

获取队列中元素个数

可以对队列进行遍历，统计元素个数，如果队列比较长那么这个方法效率就比较低。如果想要效率比较高，那么我们可以在定义队列结构体的时候加上一个size变量，每往队列里面入一个数据就统计一下，那么我们需要队列中元素个数的时候就可以直接返回。

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;//返回有效元素个数
}

检测队列是否为空

检测队列是否为空，如果为空返回非零结果，如果非空返回0

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;//将头尾指针均置为空
}

频道导航