数据结构—栈和队列

用户11367247

发布于 2024-11-20 14:53:02

8000

代码可运行

文章被收录于专栏：CodeCode

运行总次数：0

代码可运行

1.栈底层结构的选择

栈是一种数据结构

具有“后进先出的”的特点

现在面临的两种选择，一种是顺序表，另一种是链表。选择顺序表应该是优于链表的，链表的出栈和入栈时过于复杂，可以选用顺序表，仅需改变数组的下标即可实现。

2.栈的实现

栈首先要有栈顶，容量，和数据。

存入栈的数据只能出栈顶的数据，不能修改栈底的数据以及其他的数据，栈顶我们用top来表示，顺序表是arr,capacity来表示栈的容量大小。

typedef struct Stack
{
    STDataType*arr;
    int top;
    int capacity;
};

这样栈的结构实现好了，接着实现栈的功能。

3.栈

3.1入栈

入栈之前我们要确保栈还有多余的空间可以留给新的数据，所以要对栈进行检查容量大小。

if (ps->top == ps->capacity)
{
	int tmp = ps->capacity == 0 ? 4 : 2 * ps->capacity;
	STDataType* p = (STDataType*)realloc(ps->arr, sizeof(STDataType) * tmp);
	if (p == NULL)
	{
		perror("realloc Fail");
		exit(1);
	}
	else
	{
		ps->arr = p;
		ps->capacity = tmp;
	}
}

如果top和capacity相等的话，就要进行扩容。

3.2出栈

STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));

	return ps->arr[ps->top - 1];
}

值得注意的是出栈之情要检查是否为空指针，是否为空栈。

3.3栈顶删除

栈顶删除就是将top减一即可，这里不做过多解释。

void STPop(ST* ps)
{
    assert(!StackEmpty(ps));
    assert(ps);
    ps->top--;


}

4.队列

4.1队列介绍

队列是使用链表实现的，包含队头队尾，队列节点等。

4.2队列初始化

void QueueInit(Queue* pq)
{
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

4.3入队列

void QueuePush(Queue* pq, QDataType x)
{
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc faild");
		exit(1);
	}
	else
	{

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

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

入队列需要先创建一个队列节点，然后将需要插入的数据x赋给新节点。

值得注意的是要先确定pq和pq是非空的。

4.4队头删除

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	if (pq->phead == pq->ptail)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		QueueNode* tmp = pq->phead->next;
		free(pq->phead);
		pq->phead = tmp;
	}
	pq->size--;

}

如果对头和队尾相等，此时是只有一个节点，直接将头节点释放就行，然后将头尾节点置为空指针。

如果头尾不相等，那先创建一个临时指针保存phead，然后释放头节点，最后将头节点置为tmp即可，最后要将size--，这样一个删除的接口就实现好了。

队列主要的难实现的函数就是这些，其他的简单的这里就不解释了。

我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=3ci0lkbm1nk08

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-11-17，如有侵权请联系 cloudcommunity@tencent.com 删除

链表