栈和队列的那些“恩怨情仇”，被我抓个正着

欢迎来到数据结构专栏~栈和队列

(꒪ꇴ꒪(꒪ꇴ꒪ ),我是Scort
博客主页：张小姐的猫~江湖背景
快上车，握好方向盘跟我有一起打天下嘞！
送给你们一句罗翔老师的话樂：

作者水平很有限，如果发现错误，可在评论区指正，感谢
欢迎持续关注！

栈和队列的实现

欢迎来到数据结构专栏~栈和队列
栈
- 栈的概念及结构
一.栈的的实现
- 准备工作
- 1.栈的初始化
- 2.入栈
- 3.出栈
- 4.获取栈顶元素
- 5.判断栈是否为空
- 6.获取栈中元素个数
- 7.销毁栈
队列
二.队列的实现
- 准备工作
- 1.初始化队列
- 2.队尾入队列
- 3.队头出队列
- 4.获取队列头部元素
- 5.获取队列队尾元素
- 6.检测队列是否为空
- 7.获取队列中有效元素个数
- 8.销毁队列
三.栈和队列的区别
写在最后

栈 栈的概念及结构

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

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

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

一.栈的的实现 准备工作

为了简明扼要的分清楚栈和队列的作用，各部分代码分在以下三个不同的项中

Queue.h ---------➡️函数功能的说明
Queue.c ---------➡️函数功能的实现
test.c ---------➡️调用函数功能

我们用数组还是链表去实现栈呢？

答案是都可以，但是用数组是更好的

插入数据，基本上只有尾插尾删，而顺序表的尾插尾删效率很高
唯一的缺点：扩容

那么问题又来了：数组是定义静态的还是动态的呢？

答案肯定是：动态静态的还要定义数组的大小什么的，麻烦！

//静态
#define N 10
typedef int STDataType;
typedef struct Stack
{
	STDataType a[N];
	int top;
}ST;
//动态
typedef int STDataType;
typedef struct Stack
{
	STDataType *a;
	int top;//栈顶
	int capacity;//容量
}ST;

1.栈的初始化

➡️思路实现：把栈的栈顶、容量等全部置为0，栈的指针置NULL

这个简单，就不多说了上代码

代码实现：

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

❗特别注意：这里我们设置的top为0，所以top是栈顶元素的下一个

2.入栈

➡️思路实现：从栈尾插入一个元素，要注意判断空间是否足够

❗注意事项：

注意空间大小的问题：空间不够就扩容

✨动图解析：

代码实现：

// 入栈 
void StackPush(ST* ps, STDataType data)
{
	assert(ps);
	if (ps->top == ps->capacity) 
	{
		//满了就扩容
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc failn");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newCapacity;
	}
	ps->a[ps->top] = data;
	ps->top++;
}

3.出栈

➡️思路实现：即删除栈顶元素，把top - -

✨动图解析：

代码实现：

void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));//防止堆顶为空
	ps->top--;
}

4.获取栈顶元素

➡️思路实现： top是栈顶，那么top-1就是栈顶元素

❗注意事项：

要注意判断栈是否为空
ps是指向栈结构的指针，结构里有数组a和栈顶的下标top，top不是已有栈顶元素的下标，而是待入栈的一个位置，所以栈顶的下标是top-1，数组名加下标获取数组元素

代码实现：

STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));//防止栈顶为空
	 
	return ps->a[ps->top-1];
}

5.判断栈是否为空

➡️思路实现：判断top等不等于0，等于0就是就空，不等则相反

❗注意事项：

除了常规的if else判断，还有一种较为简单的方法，看下面

代码实现：

int StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

6.获取栈中元素个数

❗注意事项：

top就是size，再数组里top是最后元素的下一个，也是元素的个数，从数组下标的角度看

代码实现：

int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;//top就是size个数，看下标
}

7.销毁栈

没啥说的直接上代码

代码实现：

// 销毁栈 
void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

队列

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)

入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头

二.队列的实现 准备工作

同理，为了简明扼要的分清楚队列的作用，各部分代码分在以下三个不同的项中：Queue.h
Queue.c test.c

这里部分比较帅的读者会问：我们还是用数组去实现队列？

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

这里我们要使用带头双向链表吗？

答案：小题大做了，带头双向循环链表的优势是在任意位置上插入删除，我们队列只在队尾插入、队头删除，所以可以定义head、tail两个指针

// 链式结构：表示队列
typedef int QDataType;
typedef struct SListNode
{
	QDataType data;
	struct SListNode* next;
}QNode;
// 队列的结构
typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;

1.初始化队列

➡️思路实现：把head、tail指针置为空

代码实现：

// 初始化队列
void QueueInit(Queue* q)
{
	assert(q);
	q->head = q->tail = NULL;//不带哨兵位，哨兵位意义不大
}

2.队尾入队列

➡️思路实现：从队尾插入数据，要注意极端情况

❗注意事项：（两种情况）

当队列为空时，一个数据都没有，这时候的head和tail都是指向NULL;
队列不为空的时候，入队列一个一个的插入

✨动图解析：

情况2：

代码实现：

// 队尾入队列
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		printf("malloc failedn");
		exit(-1);
	}
	newnode->data = data;
	newnode->next = NULL;

	if (q->tail == NULL)
	{
		q->head = q->tail = newnode;
	}
	else
	{
		q->tail->next = newnode;
		q->tail = newnode;
	}
}

3.队头出队列

➡️思路实现：从队头出数据，相当于头删，也有极端情况

❗注意事项：

保存head的下一个next，释放head，然后next赋值给head
极端情况：当只剩下一个节点了，如下图的tail就变成野指针了

✨动图解析：

极端情况：

代码实现：

// 队头出队列
void QueuePop(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(&q));

	//1.一个节点
	//2.多个节点
	if (q->head->next == NULL)
	{
		free(q->head);
		q->head = q->tail = NULL;//避免野指针
	}
	else
	{
		QNode* next = q->head->next;
		free(q->head);
		q->head = next;
	}
}

4.获取队列头部元素

这个很简单，先判空，然后直接取就行
代码实现：

QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(&q));

	return q->head->data;
}

5.获取队列队尾元素

同理，取队尾数据
代码实现：

QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(&q));

	return q->tail->data;
}

6.检测队列是否为空

❗注意事项：按理来说，head和tail为空，都是一起为空的，所以任选一个
代码实现：

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q)
{
	assert(q);
	return q->head == NULL;
}

7.获取队列中有效元素个数

❗注意事项：

高效的方法：可以在队列里定义一个Size，插入数据的时候++，删除数据的时候--
不在乎效率的方法：现场计数，遍历一遍链表，算出元素个数

代码实现：

// 获取队列中有效元素个数
int QueueSize(Queue* q)
{
	assert(q);
	QNode* cur = q->head;
	int Size = 0;
	while (cur)
	{
		Size++;
		cur = cur->next;
	}
	return Size;
}

8.销毁队列

❗注意事项：

同样也是遍历链表，先定义一个next，为cur的下一个，防止找不到下一个，遍历完把head、tail都置空

代码实现：

void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* cur = q->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	q->head = q->tail = NULL;
}

三.栈和队列的区别

void TestQueue()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	QueuePush(&q, 5);

	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	printf("n");
}

void TestQueue2()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	printf("%d ", QueueFront(&q));
	QueuePop(&q);
	printf("%d ", QueueFront(&q));
	QueuePop(&q);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	QueuePush(&q, 5);

	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	printf("n");
}

可以知道，在队列里，无论我们以什么方法去出队列，输出的结果都不会变。简单来说：只要入的顺序是12345，不管咋样出，运行结果永远是12345，这才符合先进先出

队列的应用

排队，保持决定的公平性
广度优先遍历

举个例子：
栈是死胡同，队列是活胡同
队列就好像是医院的排队：先到的先拿号，先看病。
栈就好比一排车开进了死胡同，那是不是只能后来进的车先出去

写在最后

能看到这里的都是棒棒哒！
如果认真看完以上部分，肯定有所收获。
接下来我还会继续写关于《栈和队列oj》等…
如有错误可以尽管指出
磊想学吗？我教你啊磊
觉得博主写的还不错的可以一键三连撒

栈和队列的那些“恩怨情仇”，被我抓个正着

Java相关栏目本月热门文章