这篇文章来讲数据结构中的栈和队列，栈和队列都是用顺序表来实现的是两种特殊的顺序表。
文章目录
一、栈
1.栈的概念及结构
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
先进后出
这里可以联想弹夹。
在影视剧中，我们常常看到弹夹就是先进后出的结构。
2.栈的实现
我们在实现栈的时候可以使用数组或者链表实现，但是相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
还是使用头文件Stack.h源文件Stack.c测试文件test.c。
在Strack.h文件中我们要先创建动态栈的结构体。
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}ST;
2.1 初始化栈
头文件中声明
void STInit(ST* pst);
源文件中实现
void STInit(ST* pst)
{
assert(pst);
pst->a = NULL;
pst->top = 0;
pst->capacity = 0;
}
这时需要考虑，栈顶top初始值是什么。我们要注意，当top初始值为-1时此刻栈顶top就是最后一个元素。当top初始值为0，此刻栈顶top元素是栈顶数据的下一个位置，所以不同的初始化代表的意义不同。
2.2 销毁栈
头文件中声明
void STDestroy(ST* pst);
源文件中实现
void STDestroy(ST* pst)
{
assert(pst);
free(pst->a);
pst->a = NULL;
pst->capacity = pst->top = 0;
}
2.3 入栈
头文件中声明
void STPush(ST* pst, STDataType x);
源文件中实现
void STPush(ST* pst, STDataType x)
{
if (pst->top == pst->capacity)
{
assert(pst);
int newcapacity = pst->capacity == 0 ? 4 : 2 * (pst->capacity);
STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType));;
if (tmp == NULL)
{
perror(malloc);
}
pst->a = tmp;
pst->capacity = newcapacity;
}
pst->a[pst->top] = x;
pst->top++;
}
入栈直接把要入栈的值放到栈顶top元素中，简而言之把要放入的值放到下标为top的位置，然后让top往下走。但是这里要注意扩容，让容量capacity与top进行比较容量不够时要扩容。
2.4 出栈
头文件中声明
void STPop(ST* pst);
源文件中实现
void STPop(ST* pst)
{
assert(pst);
assert(pst->top > 0);
pst->top--;
}
置空就是让栈顶下标减减，想想栈是从上往下出的，也就是说先让后入的元素先出去。
2.5 取栈顶元素
头文件中声明
STDataType STTop(ST* pst);
源文件中实现
STDataType STTop(ST* pst)
{
assert(pst);
assert(pst->top > 0);
return pst->a[pst->top - 1];
}
下标top是在放入的元素下一个位置的，所以取栈顶值的时候返回数组中top下标减一位置的值就是栈顶的值。
2.6 判空
头文件中声明
bool STEmpty(ST* pst);
源文件中实现
bool STEmpty(ST* pst)
{
assert(pst);
return pst->top == 0;
}
看top是否变回初始化的值
2.7 获取数据个数
头文件中声明
int STSize(ST* pst);
源文件中实现
int STSize(ST* pst)
{
assert(pst);
return pst->top;
}
返回下标的值。下标的值是从0开始的，数组存储的值是从下标为0的位置开始的。top在数组中的位置是数组中存储的值的下一个位置。所以top的下标的值正好和存储的值相等。
stack.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}ST;
// 初始化和销毁
void STInit(ST* pst);
void STDestroy(ST* pst);
// 入栈 出栈
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);
// 取栈顶数据
STDataType STTop(ST* pst);
// 判空
bool STEmpty(ST* pst);
// 获取数据个数
int STSize(ST* pst);
stack.c
#include"Stack.h"
// 初始化和销毁
void STInit(ST* pst)
{
assert(pst);
pst->a = NULL;
pst->top = 0;
pst->capacity = 0;
}
void STDestroy(ST* pst)
{
assert(pst);
free(pst->a);
pst->a = NULL;
pst->capacity = pst->top = 0;
}
// 入栈 出栈
void STPush(ST* pst, STDataType x)
{
if (pst->top == pst->capacity)
{
assert(pst);
int newcapacity = pst->capacity == 0 ? 4 : 2 * (pst->capacity);
STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType));;
if (tmp == NULL)
{
perror(malloc);
}
pst->a = tmp;
pst->capacity = newcapacity;
}
pst->a[pst->top] = x;
pst->top++;
}
//置空
void STPop(ST* pst)
{
assert(pst);
assert(pst->top > 0);
pst->top--;
}
// 取栈顶数据
STDataType STTop(ST* pst)
{
assert(pst);
assert(pst->top > 0);
return pst->a[pst->top - 1];
}
// 判空
bool STEmpty(ST* pst)
{
assert(pst);
return pst->top == 0;
}
// 获取数据个数
int STSize(ST* pst)
{
assert(pst);
return pst->top;
}
test.c
#include"Stack.h"
#include <stdio.h>
int main()
{
ST s;
STInit(&s);
STPush(&s, 1);
STPush(&s, 2);
STPush(&s, 3);
STPush(&s, 4);
while (!STEmpty(&s))
{
printf("%d", STTop(&s));
STPop(&s);
}
STDestroy(&s);
}
二、队列
1.队列的概念及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头
2.队列的实现
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低
还是三个文件，一个头文件，一个检测文件，一个函数定义的源文件
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType val;
}QNode;
typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;
}Queue;
我们在写链表结构的时候，可以在定义一个结构体，用来管理头指针和尾指针还有长度。
2.1 队列的初始化
头文件中声明
void QueueInit(Queue* pq);
源文件中实现
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = NULL;
pq->ptail = NULL;
pq->size = 0;
}
队列的头指针和尾指针都为空，长度为0。
2.2 队列的销毁
头文件中声明
void QueueDestroy(Queue* pq);
源文件中实现
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->phead;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
从头到尾依次销毁。
2.3 队尾入队
头文件中声明
void QueuePush(Queue* pq, QDataType x);
源文件中实现
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc");
return;
}
newnode->next = NULL;
newnode->val = x;
//Ϊ
if (pq->ptail == NULL)
{
pq->phead = pq->ptail = newnode;
}
else
{
pq->ptail->next = newnode;
pq->ptail = newnode;
}
pq->size++;
}
创建新节点newnode，如果尾节点为空，也就是说这个链表为空，把新节点插入到新节点中。如果有尾节点就在尾节点之后插入新节点。注意要让长度增加。
2.4 队头出队列
头文件中声明
void QueuePop(Queue* pq);
源文件中实现
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->size!=0);
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--;
}
如果这个链表就一个节点，释放头节点让头节点和尾节点都为空，避免出现空指针。不是一个节点的话，就先把头节点的下一个节点用临时变量存起来，释放头尾点让下一个节点为头节点。注意减小长度。
2.5 获取队列头部元素
头文件中声明
QDataType QueueFront(Queue* pq);
源文件中实现
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->size);
return pq->phead->val;
}
直接返回队列头节点的值
2.5 获取队列尾部元素
头文件中声明
QDataType QueueBack(Queue* pq);
源文件中实现
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->size);
return pq->ptail->val;
}
直接返回队列尾节点的值
2.6 获取队列中有效元素个数
头文件中声明
int QueueSize(Queue* pq);
源文件中实现
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
返回size的值就是有效元素的个数。
2.7 判空
头文件中声明
bool QueueEmpty(Queue* pq);
源文件中实现
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->size==0;
}
这里用到了bool函数，如果size为0为真就返回。
Queue.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType val;
}QNode;
typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;
}Queue;
//初始化
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
// 队尾插入
void QueuePush(Queue* pq, QDataType x);
// 队头删除
void QueuePop(Queue* pq);
// 取队头和队尾的数据
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
//队中有多少数据
int QueueSize(Queue* pq);
//判空
bool QueueEmpty(Queue* pq);
Queue.c
#include "Queue.h"
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = NULL;
pq->ptail = NULL;
pq->size = 0;
}
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->phead;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc");
return;
}
newnode->next = NULL;
newnode->val = x;
//Ϊ
if (pq->ptail == NULL)
{
pq->phead = pq->ptail = newnode;
}
else
{
pq->ptail->next = newnode;
pq->ptail = newnode;
}
pq->size++;
}
test.c
#include"Queue.h"
int main()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
while(!QueueEmpty(&q));
{
printf("%d", QueueFront(&q));
QueuePop(&q);
}
printf("\n");
QueueDestroy(&q);
return 0;
}