（数据结构）栈与队列

学习完顺序表与链表，在线性表的大家庭中，还有两位特殊的成员——栈与队列。

（数据结构）栈与队列

🐸一、栈

栈是一种特殊的线性表，像堆衣服的箱子，只能先拿出来上面的。

后进先出 LIFO(Last in first out)

入栈：在栈中放入元素的操作，也叫进栈or压栈。
出栈：取出栈顶元素的操作。

了解完栈的简单功能，接下来就是进行栈的实现了。作为线性表，它的构造也是离不开线性结构的，在线性结构中，最经典的就是顺序表与链表。因此我们可以从它们开始考虑。
链表实现栈的思路：

从1~3依次入栈，每次进行头插。

那么该栈的结构如上图3->2->1，对于出栈的操作就是头删。

当然如果每次进行尾插入栈，那结构就如下图1->2->3

对应的出栈操作，需要额外记录尾或者每次进行遍历来进行尾删。

当然链表不止有单链表，基本上每一种链表都可以来实现栈，只不过难易不同，效率也不同。
顺序表（数组）实现栈的思路：【推荐】

从1~3依次入栈，结构如下图1-2-3。

? 值得一提的是，数组可以进行随机访问（用下标），因此实现起来较容易。

用动态顺序表实现栈的示范。

//用int来示范存储的类型
typedef int STDataType;
typedef struct Stack
{
	STDataType* a;//栈
	int top;//记录栈顶的位置(下标)
	int capacity;//栈容量
}ST;

🦉5.1 栈初始化

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

🦆5.2入栈

void StackPush(ST* ps, STDataType x)
{
	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 fail\n");
			exit(-1);
		}

		ps->a = tmp;
		ps->capacity = newCapacity;
	}
	//在栈顶位置存入x
	ps->a[ps->top] = x;
    //栈顶上移
	ps->top++;
}

🦔5.3 出栈

//取出栈顶元素
STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
    
	return ps->a[ps->top - 1];
}

//移除栈顶元素
void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}

🐻二、队列

队列也是一种特殊的线性表，和现实生活中的排队常见类似，先来的先走。

先进先出 FIFO(First in first out)
根据上图，队列也是有它特殊的逻辑，只能先进先出。关于队列的实现，我们也可以用顺序表或链表来实现。
顺序表实现队列思路：

用顺序表的形式来达到队列的存储模式其实代码实现也很容易，依次入队1~3，此时队列结构如下图。

但是我们发现每次出队的操作相当于对顺序表进行头删，还需要挪动其他数据，时间复杂度为O(n)，效率较低。
单链表实现队列思路：【推荐】

用单链表依次入队1~3，则该队列结构如下图

每次入队进行尾插，出队进行头删，如果再记录下对列的对头与队尾，此时操作的时间复杂度都是O(1)，操作也便利。

单链表实现队列的示范

//用int来示范存储的类型
typedef int QDataType;
//队列元素结点
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;
//队列
typedef struct Queue
{
	QNode* head;//队列头
	QNode* tail;//队列尾
}Queue;

🐘5.1队列初始化

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

🐿?5.2 入队

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
    //创建节点
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	//入队
	if (pq->tail == NULL)
	{//第一次
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}

🐧5.3出队

//删除队首元素
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
    
	if (pq->head->next == NULL)
	{//最后一个元素删除
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}

//取出队首元素
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->head->data;
}

🐼三、总结

关于栈与队列的初步认识也是清晰易懂的，它们只不过是一种特殊顺序表或者链表，对应自己特殊的逻辑。
关于它们的实现，有许多种，但是不管用什么办法进行实现，也无非是完成相同功能的函数，当然喜欢尝试的朋友可以换不同方法进行实现，然后根据时间复杂度甚至空间复杂度来判断优劣。
另一篇文章希望能帮助你理解：顺序表和链表的区别
本篇文章主要还是简单的介绍，进行入门，栈与队列都应该还有判断是否为空、销毁、计算元素个数等函数功能，文章也够冗余了就不再贴代码了。

🦀🦀观看！

待续~~