【C】栈和队列的实现

发布于:2022-11-09 ⋅ 阅读:(9) ⋅ 点赞:(0) ⋅ 评论:(0)

我们在学习完顺序表和链表之后,进一步学习其他更复杂的数据结构。这一章我们来学习栈和队列以及他们的实现,因为结构上的相似,我们会用到上一章讲到的顺序表和链表的部分思想。

目录

一、栈

1、栈的概念和结构

2、C语言实现栈

二、队列

1、队列的概念和结构

 2、C语言实现队列


一、栈

1、栈的概念和结构

栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。
进行数据插入和删除操作的一端 称为栈顶,另一端称为栈底。
栈中的数据元素遵守后进先出 LIFO Last In First Out )的原则。
压栈:栈的插入操作叫做进栈 / 压栈 / 入栈, 入数据在栈顶
出栈:栈的删除操作叫做出栈。 出数据也在栈顶
入栈演示图:

出栈演示图:

                        

 栈严格符合先进后出的原则。

2、C语言实现栈

我们可以使用顺序表实现栈,也可以使用链表实现栈。对比两种结构,我们发现顺序表尾插尾删所付出的代价更小。

第一步我们要创建一个栈的结构,这里我们创建一个可以动态增长的栈:

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

如果我们需要改变数据类型,改STDataType所再定义的类型即可capacity代表容量以便我们后面动态增长容量

第二步我们站在大局观上考虑我们要实现什么功能:

//初始化
void StackInit(ST* ps);
//销毁
void StackDestory(ST* ps);
//数据入栈
void StackPush(ST* ps, STDataType x);
//数据出栈
void StackPop(ST* ps);
//栈顶的数据
STDataType StackTop(ST* ps);
//栈的大小
int StackSize(ST* ps);
//判断栈是否为空
bool StackEmpty(ST* ps);

第三步我们根据上面为依据,来一一实现:


栈的初始化

void StackInit(ST* ps)
{
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

栈的销毁:

void StackDestory(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

上面是最基本的栈的创建和销毁。

数据入栈:

void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 :ps->capacity*2;
		STDataType* tmp = realloc(ps->a,sizeof(STDataType) * newcapacity);
		if(tmp==NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
		
	}
	ps->a[ps->top] = x;
		ps->top++;
}

入栈我们先要判断栈的容量是否够,用if语句判断,如果不够就开辟空间,然后新的数据存放在顺序表尾。

数据出栈:

void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));

	ps->top--;

}

出栈我们只需要删除顺序表最后一个元素,也就是数组下标减去1,这样数组的容量大小减1,这样原本的最后一个元素所占有的空间自然就还给内存了。

返回栈顶的数据:

STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top-1];
}

由于我们初始化的top的值为0,每存放一个top就加1.比如我们此时只存放一个数据,这是顺序表中最后一个数据就是a[0],而top从0加到1了,所以我们要找最后一个元素所在的下标就是top-1.

栈的大小:

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

大小比最后顺序表的下标要大1,所以直接返回top就行。

判断栈是否为空:

bool StackEmpty(ST* ps)
{
	assert(ps);

	/*if (ps->top == 0)
	{
		return true;
	}
	else
	{
		return false;
	}*/
	return ps->top == 0;
}

我们可以用if语句判断,也可以直接用ps->top==0这个表达式返回的值进行判断。

二、队列

1、队列的概念和结构

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

队列演示图: 

从队尾进,队头出,先进先出。

 2、C语言实现队列

同样我们可以使用顺序表和链表来实现队列。对比之后,我们发现出队列要头删,顺序表不适用头删,而链表实现头删付出的代价很小,所以我们利用链表的结构来实现队列。

第一步我们也是创建队列的结构:

typedef int QDataType;

typedef struct QueueNode
{
	QDataType data;
	struct Queue* next;
}QueueNode;

typedef struct Queue
{
	QueueNode* head;
	QueueNode* tail;
}Queue;

队列的结点我们创建一个data存放数据,next存放下一个结点的地址。我们再创建Queue结构体存放这个链表的头和尾,这样便于我们找到队列的头数据和尾数据。

第二步我们也整体来看我们需要实现什么标准:

//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestroy(Queue* pq);
//入队
void QueuePush(Queue* pq, QDataType x);
//出队
void QueuePop(Queue* pq);
//返回队头数据
QDataType QueueFront(Queue* pq);
//返回队尾数据
QDataType QueueBack(Queue* pq);
//返回队列长度
int QueueSize(Queue* pq);
//判断队列是否为空
bool QueueEmpty(Queue* pq);

第三步我们根据上述的总体规划来一一实现:

队列的初始化:

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
}

队列的初始化我们只需要将头尾结点初始化为NULL。

队列的销毁:

void QueueDestroy(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->head;
	while (cur)
	{
		QueueNode* next = pq->head->next;
		free(cur);
		cur = next;


	}
	pq->head = pq->tail = NULL;
}

我们用next存放cur下一个结点的位置,然后free掉cur结点,然后把next赋给cur,next再往下找下一个结点,以此类推,释放掉整个链表。

数据入队:

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	newnode->data = x;
	newnode->next = NULL;
	if(pq->head==NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}

数据入队我们按照链表结构我们首先要找到队尾,但是我们对队列初始化时设置了tail来存放队尾的位置,所以直接开辟空间把新结点尾插到链表尾就可以了。

数据出队:

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	QueueNode* next = pq->head->next;
	free(pq->head);
	pq->head = next;

	if (pq->head == NULL)
	{
		pq->tail = NULL;
	}
}

出队只需要头删即可,注意考虑一些特殊情况。

返回队头和队尾数据:

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->head->data;
}


QDataType QueueBack(Queue* pq)
{

	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->tail->data;
}

返回队列长度:

int QueueSize(Queue* pq)
{
	assert(pq);
	int n = 0;
	QueueNode* cur = pq->head;
	while (cur)
	{
		n++;
		cur = cur->next;
	}
	return n;
}

判断队列是否为空:

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

}

只需要判断pq->head==NULL这个式子的返回值即可。

本篇文章就介绍到这,下篇我们会详解栈和队列的OJ题。