数据结构-栈和队列

一.栈

1.1栈的定义

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

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

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

这张图简洁明了的显示了栈的特点。入的时候是以ABCD的顺序，出的时候是以DCBA的顺序。大家可以把栈想象成水桶，先倒进去的水后喝到，后倒进去的水先喝到。

取决于栈的底层结构，我们需要用前面学的数组或者链表来实现，而选择什么样的方式来实现的参考标准之一是时间复杂度，下面我们用图表来解释。

当我们用数组来实现时，入栈和出栈的时间复杂度都为O(1)，也就是我们前面学的尾插和尾删。但是如果此时的栈顶和栈底位置发生了交换，入栈和出栈的时间复杂度就为O(n),也就是头插和头删。注意栈顶和栈底的位置不同，也会影响时间复杂度。当然我们要取最优的时间复杂度。

当我们用链表来实现时，此时栈顶和栈底的位置，时间复杂度为O(1)，相当于头插和头删。而如果栈顶和栈底的位置相反，入栈的时间复杂度为O(1)，出栈的时间复杂度为O(n)，相当于尾插和尾删。

如果我们都取最优的时间复杂度，这时候发现数组和链表都可以，这时我们可以从内存的角度去考虑，数组的话一个空间只需要用4个字节就可以了，而链表则需要8个字节，这里是拿数据为int类型来举例。故我用数组来实现，不过用链表实现也可以。

1.2代码示例

typedef int STDateType;
typedef struct Stack
{
	STDateType* arr;
	int top;
	int capacity;
}ST;

栈的结构

说是数组，其实就是用我们之前学的线性表来实现，只不过功能不一样而已。

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

栈的初始化

跟线性表一样，唯一的区别是把线性表里面的size改成了top，用来表示栈顶，也表示数组中有效数据的个数。

void STDestory(ST* ps)
{
	if (ps->arr != NULL)
	{
		free(ps->arr);
		ps->arr = NULL;
		ps->capacity = ps->top = 0;
	}
}

栈的销毁

先判断数组是否为空，如果不为空，就将数组置为NULL，top和capacity置为0。

void STPush(ST* ps, STDateType x)
{
	assert(ps);
	//空间不够
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDateType* tmp = (STDateType*)realloc(ps->arr, newcapacity * sizeof(STDateType));
 		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}
	//空间足够
	ps->arr[ps->top++] = x;
}

入栈

1.判断传入的ps是否为假

2.分情况讨论。空间足够的情况下，直接把下标为top位置的数据传入即可。空间不够的情况下，跟线性表一样，需要扩容，这里我用的是realloc来扩容，用malloc扩容也可。

注意：扩容时的条件时有效数据的个数和容量相等时，此时数组已满，就需要扩容。

STDateType STTop(ST* ps)
{
	assert(ps);
	return ps->arr[ps->top - 1];
}

取出栈顶元素

1.判断传入的ps是否为假

2.因为top是栈顶，记录的是有效数据个数，所以我们在返回栈顶元素时下标为top-1

bool STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

判断栈是否为空

1.判断传入的ps是否为假

2.判断此时的top是否为0，为0则表示栈为空，非0则表示链表非空

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

出栈

1.判断数组是否为空

2.和线性表一样，出栈只需要让top--就可以

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

返回栈有效数据的个数

1.判断传入的ps是否为假

2.因为top就表示有效数据的个数，所以直接返回top即可

二.队列

2.1队列定义

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

入队列：进行插入操作的一端称为队尾

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

这张图表示的就是队列的逻辑结构，入队的顺序是654321，出队的顺序也是654321。大家可以把队列想象成饮水机，饮水机先抽的水先喝到，后抽到的水后喝到。

取决于栈的底层结构，我们需要用前面学的数组或者链表来实现，而选择什么样的方式来实现的参考标准之一是时间复杂度，下面我们用图表来解释。

这是数组来实现，入队的时间复杂度为O(1)，相当于尾插，出队的时间复杂度为O(n)，相当于头删。而交换二者的位置，时间复杂度是不变的，还是O(1)和O(n)这两个答案。

如果用链表来实现，入队的时间复杂度为O(n)，相当于尾插，出队的时间复杂度为O(1)，相当于头删。交换两者的位置，时间复杂度也是O(n)和O(1)两个答案。

跟栈的问题一样，用数组和链表实现都可以。但是介于队列的特殊结构，我们找到了一个新的方法，因为队列我们只需要看队头和队尾，故可以对链表作出一定的修改，比如：

typedef int QDateType;
typedef struct QueueNode
{
	QDateType date;
	struct QueueNode* next;
}QueueNode;

//队列的结构
typedef struct Queue
{
	struct QueueNode* pHead;//队头
	struct QueueNode* pTail;//队尾
}QE;

如上述代码所示，我们把队头和队尾单独拿出来，这样在用链表实现时，入队和出队的时间复杂度就都为O(1)，这样的话选择链表实现队列就会更方便一些。

有些人可能会问：那么数组可以怎么改变呢？答案小编也不知道，如果有知道的大佬可以在评论区演示一下。

2.2代码示例

void QInit(QE* pq)
{
	assert(pq);
	pq->pHead = pq->pTail = NULL;
}

队列的初始化

1.判断传入的pq是否为假

2.将队头和队尾初始化置为NULL；

注意：我们在测试的时候，要创建的是存放队头和队尾的结构体变量，如果创建的是结点的结构体变量，还是会找不到队尾。

void QPush(QE* pq, QDateType x)
{
	assert(pq);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->date = x;
	newnode->next = NULL;

	//入队
	//判断队列是否为空
	if (pq->pHead == NULL)
	{
		pq->pHead = pq->pTail = newnode;
	}
	else//队列非空
	{
		pq->pTail->next = newnode;
		pq->pTail = pq->pTail->next;
	}
}

入队

1.判断传入的pq是否为假

2.创建结点

3.分情况讨论。如果链表非空，那么就让队尾的next指向新结点，队尾再转到新节点的位置。如果链表为空，就让队头和队尾都指向新结点即可。

bool QEmpty(QE* pq)
{
	assert(pq);
	return pq->pHead == NULL;
}

判断队列是否为空

1.判断传入的pq是否为假

2.判断队头是否为NULL，如果为NULL，表示队列为空，反之则不为空

void QPop(QE* pq)
{
	assert(!QEmpty(pq));
	//特殊情况：当只有一个结点时，如果直接free，pTail会变成野指针
	if (pq->pHead == pq->pTail)
	{
		free(pq->pHead);
		pq->pHead = pq->pTail = NULL;
	}
	else
	{
		QueueNode* next = pq->pHead->next;
		free(pq->pHead);
		pq->pHead = next;
	}
}

出队

1.判断队列是否为空

2.分情况讨论。如果队列只有一个结点，我们如果直接把pHead给free掉，那么pTail就变为野指针，所以我们在出队后要将pTail置为NULL。而有多个结点时，我们需要一个临时变量来记录队头的下一个结点，然后进行出队操作，最后将pHead转移到新的队头

QDateType QFront(QE* pq)
{
	assert(!QEmpty(pq));
	return pq->pHead->date;
}

取出队头的数据

1.判断队列是否为空

2.直接返回pHead中存储的数据即可

QDateType QBack(QE* pq)
{
	assert(!QEmpty(pq));
	return pq->pTail->date;
}

取出队尾的数据

1.判断队列是否为空

2.直接返回pTail中存储的数据即可

int QCheck(QE* pq)
{
	assert(pq);
	int size = 0;
	QueueNode* pcur = pq->pHead;
	while (pcur)
	{
		size++;
		pcur = pcur->next;
	}
	return size;
}

返回队列中有效数据的个数

1.判断传入的pq是否为假

2.定义一个变量size来记录有效数据的个数，之后再遍历数组，就得到了队列有效数据的个数

void QDestory(QE* pq)
{
	assert(pq);
	QueueNode* pcur = pq->pHead;
	while (pcur)
	{
		QueueNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	pq->pHead = pq->pTail = NULL;
}

销毁队列

1.判断传入的pq是否为假

2.创建临时变量pcur和next来记录当前结点和当前结点的下个结点，然后遍历数组一个个销毁，最后将pHead和pTail置为NULL即可

三.总结

栈和队列其实就是之前所学的线性表和链表的变式，只不过因结构不同而有不同的功能。这节知识涉及到先前讲的线性表和链表，如果有不懂的可以看我之前的文章。记得写一个功能，就检测一个功能。