《栈和队列》的模拟实现(顺序栈) (链队列)

前言：

栈和队列：

栈：

队列：

模拟实现《栈》：

1.typedef数据类型

2.初始化栈

3.销毁栈

4.入栈

5.出栈

6.取栈顶元素

7.判断栈是否为空

8.栈的大小

9.打印栈

模拟实现《队列》：

1.typedef数据类型

2.初始化队列

3.销毁队列

4.入队列

5.出队列

6.取队头

7.取队尾

8.判断队列是否为空

9.队列的元素个数

10.打印队列

总结：

前言：

我们在上几篇的blog中，对于顺序表和两种链表都进行了模拟实现，已经相关的Leecode的oj题目我们都已经见识过了，下面我们就来对我们所学习的顺序表和链表进行提高练习，那就不得动手来实现实现《栈和队列》了。

栈和队列：

栈：

栈（Stack）是一种数据结构，可以理解为“一摞书”，它的特点是只能在一端进行操作，也就是称为栈顶（top），另一端称为栈底（bottom）。栈的基本操作有两个：push（入栈）和pop（出栈）。push操作往栈顶添加元素，pop操作从栈顶删除元素。

栈的特点是先进后出（Last In First Out，LIFO），即后

加入的元素先被取出。这种特性使得栈常常被用来处理一些具有“后效性”的问题，比如递归的函数调用、表达式求值、括号匹配、浏览器的“前进”和“后退”功能等等。

示意图：

  +---+         <- 栈顶
  | 3 |
  +---+
  | 2 |
  +---+
  | 1 |
  +---+         <- 栈底

队列：

队列是一种具有特定操作的数据结构，遵循“先进先出”（First In, First Out，FIFO）的原则。

示意图：

  Front                          Rear
    |                             |
  +---+  +---+  +---+  +---+  +---+
  | 1 |  | 2 |  | 3 |  | 4 |  | 5 |
  +---+  +---+  +---+  +---+  +---+

在这个示意图中，队列的前端（Front）指向队列的第一个元素，队列的后端（Rear）指向队列的最后一个元素。元素1最先进队列，然后是2、3、4、5。如果要出队列，将首先出队列的是元素1，然后是2、3、4、5。

队列的基本操作包括：

enqueue：将元素加入队列的末尾。
dequeue：从队列的前端移除元素。
front：获取队列的前端元素，但不移除。
isEmpty：检查队列是否为空。

队列通常用于模拟实际情况，例如任务调度、广度优先搜索等场景。在编程中，队列是一种常见的数据结构。

模拟实现《栈》：

1.typedef数据类型

typedef int STDataType;

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

由于这部分与咱们上次将的顺序表的实现，也就是通讯录大为相似，所以在这里我也不过多赘述，有需要的同学可以访问顺序表的blog：

《动态顺序表》的实现-CSDN博客

2.初始化栈

void STInit(ST* pst)
{
	assert(pst);
	pst->a = NULL;
	pst->capacity = 0;
	pst->top = -1;
}

这里要注意的是，在之前的顺序表中我们是定义了size来表示数组的长度，但是在这里，我们是利用top来定义的栈顶元素，并将其初始化为-1。

其实初始化为0还是初始化为-1都可以，没有过多的讲究，如果初始化为0的话，我们在后续判断栈是否为空理解起来就显得十分麻烦。

如果是定义top = -1，就显得尤为轻松。

在此我们统一定义top = -1.

3.销毁栈

void STDestory(ST* pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->top = -1;
	pst->capacity = 0;
}

4.入栈

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

}

我们在此作出了与顺序表和通讯录不一样的地方，就是我们在此并没有再创建一个函数用来实现判断扩容，因为我们全部函数中有且只有入栈函数要进行判断是否需要扩容的操作。

因此我们直接在函数内部实现即可。

5.出栈

void STPop(ST* pst)
{
	assert(pst);
	if (pst->top != -1)
	{
		pst->top--;
	}
}

6.取栈顶元素

STDataType STTop(ST* pst)
{
	assert(pst);
	if (pst->top != -1)
	{
		return pst->a[pst->top];
	}
	return -1;
}

7.判断栈是否为空

bool STEmpty(ST* pst)
{
	assert(pst);
	if (pst->top == -1)
	{
		return true;
	}
	return false;
}

8.栈的大小

int STSize(ST* pst)
{
	assert(pst);
	return pst->top + 1;
}

9.打印栈

void STPrint(ST* pst)
{
	assert(pst);
	for (int i = 0; i <= pst->top; i++)
	{
		printf("%d  ", pst->a[i]);
	}
}

以上就是栈的全部模拟实现，因为我们用的是顺序表来模拟实现栈，所以大部分内容参考之前blog即可，接下来我们一起实现队列。

模拟实现《队列》：

1.typedef数据类型

typedef int QDataType;

typedef struct QueueNode
{
	QDataType val;
	struct QueueNode* next;
}QNode;

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int sz;
}Queue;

我们在本文实现的是链队列，但是不同于我们之前对单链表的实现，由于我们在此需要经常进行找尾操作，而且尾指针时不时会发生改变，因此我们可以再创建一个结构体，里面包含了我们所需要的两个指针，一个头指针和一个尾指针，这样我们在调试的时候也不必需要传二级指针了。

如图：

可能现在还不是很理解，接下来我们动手实现几个函数，就能迎刃而解了。

2.初始化队列

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

3.销毁队列

void QueueDestroy(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	QNode* cur = NULL;
	while (cur)
	{
		cur = pq->phead->next;
		free(pq->phead);
		pq->phead = cur;
	}
	pq->ptail = pq->phead = NULL;
}

4.入队列

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("QueuePush -> malloc");
		exit(-1);
	}
	newnode->val = x;
	newnode->next = NULL;

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

}

因为是链表，所以我们入队列的时候要动态开辟出一个新的节点来存放数据而此时链表是空的，而队列本质是尾插，头删，所以我们才采用的链表。如图：

继续入队时，注意仔细观察*phead和*ptail的变化。

后面当我想要加入数据的时候就以此类推。

5.出队列

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	if (pq->ptail == pq->phead)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		QNode* cur = pq->phead->next;
		free(pq->phead);
		pq->phead = cur;
		pq->sz--;
	}
}

由于队列是“先进先出”实际上是链表的头删操作。

这里要注意的是，存在两种情况

1.队列仅有一个节点

2.队列多个节点

当队列仅有一个节点时，随着对pq->phead释放，不仅要将pq->phead置为NULL，

同时也要对pq->ptail进行操作！！！

6.取队头

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	return pq->phead->val;
}

7.取队尾

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	return pq->ptail->val;
}

8.判断队列是否为空

bool QueueEmpty(Queue* pq)
{
	if (pq->phead != NULL)
	{
		return false;
	}
	return true;
}

9.队列的元素个数

int QueueSize(Queue* pq)
{
	return pq->sz;
}

10.打印队列

void QueuePrint(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->phead;
	while (cur)
	{
		printf("%d->", cur->val);
		cur = cur->next;
	}
	printf("NULL\n");
}