数据结构之栈和队列
栈和队列
1.栈的概念及结构
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
通常，栈的开口端被称为栈顶；相应地，封口端被称为栈底。因此，栈顶元素指的就是距离栈顶最近的元素。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
2.栈的实现
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。下面我们一起来实现动态开辟存储空间栈的以下操作。
//栈初始化
void InitStack(S* ps);
//入栈
void PushStack(S* ps, StackData x);
//出栈
void PopStack(S* ps);
//清空
void ClearStack(S* ps);
2.1栈的结构
typedef int StackData;
typedef struct Stack
{
StackData* a;
int size;//已压栈的数据个数
int capacity;//容量
}S;
2.2栈的初始化和清空
栈的初始化和清空操作相对而言比较简单，因为初始化时没有压入数据，可将size和capacity都置为0且a指向NULL；清空的时候释放掉指针栈的头指针并指向空即可，同时再将size和capacity置0。
//栈初始化
void InitStack(S* ps)
{
ps->a = NULL;
ps->size = ps->capacity = 0;
printf("初始化成功。\n");
}
//清空
void ClearStack(S* ps)
{
free(ps->a);
ps->a = NULL;
ps->size = ps->capacity = 0;
printf("该栈已清空。\n");
}
2.3入栈和出栈
例如，将元素 1、2、3、4 依次入栈，等价于将各元素采用头插法依次添加到链表中。
对于出栈操作，若要将元素 3 出栈，根据"先进后出"的原则，要先将元素 4 出栈，也就是从链表中摘除，然后元素 3 才能出栈：
下面用代码来实现以上操作：
//入栈
void PushStack(S* ps, StackData x)
{
StackCheakCapacity(ps);
ps->a[ps->size] = x;
ps->size++;
printf("入栈成功。\n");
}
//出栈
void PopStack(S* ps)
{
if (ps->size == 0)
{
printf("空栈无法弹出。\n");
return;
}
printf("弹出元素为：%d\n", ps->a[--ps->size]);
}
需要注意的时，我们初始化是capacity和size都是0，后面也可能会出现size=capacity导致已经栈满的情况，这里我们不妨在每次插入时进行一次容量检查的操作，如果栈满我们就进行扩容，一般我们都将其扩大一倍：
//检查容量够不够,不够就扩容至两倍。
void StackCheakCapacity(S* ps)
{
if (ps->size == ps->capacity)//满了就要扩容
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
StackData* tmp = (StackData*)realloc(ps->a, newcapacity * sizeof(StackData));
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
else
{
ps->a = tmp;
ps->capacity = newcapacity;
}
}
}
这段代码中还有一个小细节，就是newcapacity的定义，当capacity的值不为0时，可以直接开始realloc操作开辟2倍的capacity空间，但如果capacity等于0的话，他的两倍还是0相当于没有开辟空间，所以如果capacity为0我们就给初始值为4。
3.队列的概念及结构
队列，和栈一样，也是一种对数据的"存"和"取"有严格要求的线性存储结构，与栈结构不同的是，队列的两端都"开口"，要求数据只能从一端进，从另一端出，队列具有先进先出 FIFO(First In First Out) 的性质。
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头。
4.队列的实现
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。下面我们一起来实现动态开辟存储空间队列的以下操作。
//队列初始化
void QueueInit(Queue* pq);
//队列销毁
void QueueDestroy(Queue* pq);
//入队
void QueuePush(Queue* pq, QDataType x);
//出队
void QueuePop(Queue* pq);
4.1队列的结构
typedef struct Queue
{
QueueNode* head;
QueueNode* tail;
}Queue;
4.2队列的初始化和销毁
和栈的初始化销毁类似，因为还没有进行入队操作，不妨将head和tail都指向NULL；销毁时释放掉指针并指向空即可。
//初始化
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = NULL;
pq->tail = NULL;
}
//销毁
void QueueDestroy(Queue* pq)
{
assert(pq);
QueueNode* cur = pq->head;
while (cur != NULL)
{
QueueNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
}
4.3入队和出队
//入队
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
newnode->data = x;
newnode->next = NULL;
if (pq->head == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
}
//出队
void QueuePop(Queue* pq)
{
assert(pq);
//if (pq->head == NULL)
// return;
assert(!QueueEmpty(pq));
QueueNode* next = pq->head->next;
free(pq->head);
pq->head = next;
if (pq->head == NULL)
{
pq->tail = NULL;
}
}
好了今天的分享就到这里啦，点波订阅加关注，下次找我不迷路，关注我带你学习更多有用的小知识哟。