数据结构-栈和队列

一、栈

1.概念与结构

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

压栈: 栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈: 栈的删除操作叫做出栈。出数据也在栈顶。

栈底层结构选型
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。

2.数组栈的实现

2.1 栈的结构定义

typedef int STDataType;
typedef struct Stack
{STDataType* arr;int top; int capacity; //空间容量
}ST;

arr就是待开辟空间的指针。top可以有两种选择：一种是指向栈顶元素，另一种就是指向栈顶元素的下一个位置。现在我们定义一个栈的变量：

ST st;

2.2 栈的初始化

void STInit(ST* pst)
{assert(pst != NULL);pst->arr = NULL;//pst->top = -1; //top指向栈顶元素pst->top = 0; //top指向栈顶元素的下一个位置pst->capacity = 0;
}

由于定义的是一个结构体变量st，要改变该结构体，就要传st的指针。所以要断言pst不能为空，开始先初始化数组的指针为空。对于top我们说过有两种定义方式：

当top初始化为-1时，说明top指向的是栈顶元素，top==-1时说明栈顶还没有存储元素。top==-1是数组第一个元素的前一个位置，是非法的：

当top初始化为0时，说明top指向的是栈顶元素的下一个位置，top==0时说明栈顶还没有数据：

capacity就是数组能存储的元素个数。

2.3 栈的销毁

void STDestroy(ST* pst)
{assert(pst != NULL);free(pst->arr);pst->arr = NULL;pst->top = pst->capacity = 0;
}

由于动态开辟的是一块连续的空间，所以释放空间很简单，直接free掉arr，再把arr置空，top和capacity赋值为0即可。pst仍然要断言不能为空。

2.4 栈的判空

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

判空就是判断栈顶是否有数据，初始化的top是为0的，说明top指向的是栈顶元素的下一个位置。所以如果表达式top==0为真，则返回true，否则返回false。

2.5 栈的入栈

void STPush(ST* pst,STDataType x)
{assert(pst != NULL);if (pst->top == pst->capacity){int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;STDataType* tmp = (STDataType*)realloc(pst->arr, newCapacity*sizeof(STDataType));if (tmp == NULL){perror("realloc fail!");return NULL;}pst->arr = tmp;pst->capacity = newCapacity;}pst->arr[pst->top++] = x;
}

由于top是指向栈顶元素的下一个位置，所以在压栈之前，要先判断数组是否满了，也就是当top==capacity时，要么是数组里还没有元素，要么就是数组存储满了。realloc就能实现空间的扩容。如果还没有开辟空间，那realloc的功能就相当于malloc。在压栈后，记得要把top往后挪一位，指向栈顶元素的下一个位置。

2.6 栈的出栈

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

由于栈的特点是后进先出，所以栈里元素的出栈，要从栈顶出元素才行。直接让top往前挪一位即可。但在删除栈顶元素之前要先判空。因为如果栈里没有元素，则不能进行出栈操作。

2.7 查看栈顶元素

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

在返回栈顶元素之前要先判断栈是否为空，不为空再返回栈顶的元素。注意：top是指向栈顶元素的下一个位置的，所以栈顶元素的位置是top-1。

2.8 栈的大小

int STSize(ST* pst)
{assert(pst != NULL);return pst->top;
}

栈的大小即数组中的有效元素个数。由于top是指向栈顶元素的下一个位置的，所以top刚好就可以表示数组中的有效元素个数。注意：如果一开始top是初始化为-1的话，那数组的有效元素个数就要返回top+1。

3.两种栈的图示结构

记住：栈的特点是后进先出(Last In First Out)，所以链式栈的进栈出栈要在头结点处进行。
🧳🧳栈就像箱子一样：往箱子里放东西会从箱底放起，直到放满；然后从箱子里取东西就要从箱顶开始取，否则你取不到箱底的东西。 这就是后进先出的意思。

代码仓库：Stack

二、队列

1.概念与结构

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

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

队列底层结构选型
队列也可以使用数组或链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列要在数组头出数据，效率会比较低。

2.链式队列的实现

2.1 队列的结构定义

//1.节点结构
typedef int QDataType;
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QNode;

//2.队列结构
typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;

队列的结构中只有三个成员，phead是用来指向链表的头的，ptail是用来指向链表的尾的。因为队列是先进先出的特点，所以链式队列是在队头出数据，在队尾进数据。有了phead和ptail指针就方便我们管理链表。size是链表的元素个数(节点个数)。

若现在创建了一个结构体变量：

Queue q;

2.2 队列的初始化

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

注意：我们创建的是一个结构体变量q，所以要改变该变量，就要传该变量的地址才行。所以要对pq进行断言不能为空。

2.3 队列的销毁

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

队列的销毁就是释放链表中的所有节点，然后要记得把phead和ptail置为空，size赋值为0。链式队列的销毁就跟单链表的销毁是一样的。

2.4 队列的判空

bool QEmpty(Queue* pq)
{assert(pq != NULL);return pq->phead == NULL&& pq->ptail == NULL;
}

理论上如果链表为空，那phead和ptail都为空，但是两个一起判断更好，以免出啥bug。当然也可以通过判断size是否等于0来判断队列是否为空。

2.5 队列的入队

void QueuePush(Queue* pq, QDataType x)
{assert(pq != NULL);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail!");return;}newnode->data = x;newnode->next = NULL;if (pq->ptail == NULL){assert(pq->phead == NULL);pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}

先创建一个新节点，然后需要判断此时队列是否为空，为空是一种情况，不为空也是一种情况。为空就让phead和ptail都指向newnode；不为空就要在尾结点ptail处进行尾插。数据入队后，记得要让size+1。

2.6 队列的出队

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

元素出队也是需要分类讨论的，如果队列为空就不能进行出队操作，所以要先判空。如果是队列中只有一个节点，那phead和ptail此时都指向这个节点，所以直接释放掉phead即可，但是要记得把两个指针都置空，否则会出现野指针。如果队列中不止一个节点，那直接在头结点phead处进行头删。出队一个元素，记得要让size-1。

2.7 查看队头元素

QDataType QueueFront(Queue* pq)
{assert(pq != NULL);assert(!QEmpty(pq));return pq->phead->data;
}

如果队列为空，则链表为空，没有队头数据。所以要判先空。

2.8 查看队尾元素

QDataType QueueBack(Queue* pq)
{assert(pq != NULL);assert(!QEmpty(pq));return pq->ptail->data;
}

查看队尾元素也是要先判断队列是否为空，队列为空就没有队尾元素。

2.9 队列的大小

int QueueSize(Queue* pq)
{assert(pq != NULL);return pq->size;
}

队列的大小就是队列中的元素个数(节点个数)size，返回size即可。

3.链式队列的图示结构

记住：队列的特点是先进先出(First In Fitst Out)，所以链式队列的入队要在链表的尾结点处尾插，而出队要在链表的头节点处头删。
⬅️🚶🚶‍♂️🚶‍♀️⬅️队列就像排队打饭一样：先来的同学会排在队伍的前面，而后来的同学会排在队伍的后面。排在最前面的同学会先打到饭离开队伍，而排在队伍后面的同学需要等待前面的同学离开了才能打到饭。这就是先进先出的意思。

代码仓库：Queue