C语言数据结构——栈和队列-创新互联
目录
前言
一、栈
1.1 栈的概念和结构
1.2 栈的实现
1.2.1 栈的创建及其初始化
1.2.2 入栈/出栈
1.2.3 获取栈顶元素
1.2.4 检查栈是否为空
1.2.5 销毁栈
二、队列
2.1 队列的概念及结构
2.2 队列的实现
2.2.1 队列结构的创建及初始化
2.2.2 插入删除数据
2.2.3 读取头尾数据
2.2.4 判断是否为空
2.2.5 判断存储数据的数量
2.2.6 销毁队列
总结
前言
本篇文章主要带领大家深入了解栈和队列以及相关实现。
一、栈 1.1 栈的概念和结构
栈：栈是一种特殊的线性表，其只允许在一端进行插入和删除的操作，而进行插入删除操作的一端叫栈顶，另一端叫栈底。所以栈中的数据也遵从后进先出原则。
压栈：从栈顶压入数据的操作叫做压栈，也称为进栈或者出栈
出栈：从栈顶删除数据的操作叫做出栈
栈的实现一般使用数组或者是链表，相对而言，使用数组的优势更大，因为数组尾插尾删的效率高，相当契合栈的要求，而链表尾删需要遍历链表效率相比数组就低了许多。
1.2.1 栈的创建及其初始化接下来我们就用数组实现动态栈
栈的创建：栈的结构体成员有三个，分别代表数组，栈顶，栈容
// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
STDataType* _a;
int _top; // 栈顶
int _capacity; // 容量
}Stack;栈的初始化：我们先开辟4个空间的数组，然后给栈顶，容量赋值
// 初始化栈
void StackInit(Stack* ps)
{
assert(ps);
STDataType* ptr = (STDataType*)malloc(4 * sizeof(STDataType));
if (ptr == NULL)//检查开辟是否成功
{
perror("malloc");
exit(-1);
}
ps->_a = ptr;
ps->_top = 0;
ps->_capacity = 4;
}入栈：入栈需要先检查容量，如果容量满了，就用realloc进行扩容，然后在插入数据即可
// 入栈
void StackPush(Stack* ps, STDataType data)
{
assert(ps);
if (ps->_top == ps->_capacity)
{
STDataType* ptr =realloc(ps->_a,ps->_capacity*2*sizeof(STDataType));
if (ptr == NULL)//检查开辟是否成功
{
perror("malloc");
exit(-1);
}
ps->_a = ptr;
ps->_capacity = ps->_capacity * 2;
}
ps->_a[ps->_top] = data;
ps->_top++;
}出栈：出栈就很简单了，只需检查栈里是否有数据，无数据则无法删除，然栈顶--即可。
// 出栈
void StackPop(Stack* ps)
{
assert(ps);
assert(StackEmpty(ps));
ps->_top--;
}这个需要注意的是，top指向的是栈顶元素的下一个位置，所以想要获取栈顶元素，需要的下标是top-1
// 获取栈顶元素
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(StackEmpty(ps));
return ps->_a[ps->_top - 1];
}只需返回top即可，如果top为0则为空
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->_top;
}释放数组即可
// 销毁栈
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->_a);
ps->_a = NULL;
ps->_capacity = 0;
ps->_top = 0;
}队列：只允许在一端进行插入，在另一端进行删除的特殊线性表，插入的一端叫队尾，删除的一端叫队头，遵从先进先出原则。
队列一般可以用数组或者链表实现，使用链表的结构更优一些，因为队列需要用到尾插头删，链表的头删和尾插都比数组要优秀。
2.2.1 队列结构的创建及初始化下面就用链表实现队列
结构的创建：首先是创建链表的节点空间，然后在创建两个指针分别指向链表头和尾，再创建一个size记录队列的有效数据
typedef int QDataType;
typedef struct QueueNode
{
QDataType data;
struct QueueNode* next;
}QNode;
typedef struct Queue
{
QNode* head;
QNode* tail;
int size;
}Queue;初始化：头尾指针置空，size置为0
//初始化
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
pq->size = 0;
}插入数据：先给要插入的数据开辟一个新节点，然后只需要考虑一些第一次插入的特殊情况，其他按照链表的尾插即可
//插入数据
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newcode = (QNode*)malloc(sizeof(QNode));
if (newcode == NULL)
{
perror("malloc");
exit(-1);
}
if (pq->head == NULL)
{
newcode->data = x;
newcode->next = NULL;
pq->head = pq->tail = newcode;
pq->size++;
}
else
{
newcode->data = x;
newcode->next = NULL;
pq->tail->next = newcode;
pq->tail = pq->tail->next;
pq->size++;
}
}删除数据：需要检查是否为空，为空则无法删除，和链表头删类似
//删除数据
void QueuePop(Queue* pq)
{
assert(pq);
assert(QueueEmpty(pq));
QNode* cur = pq->head->next;
free(pq->head);
pq->head = cur;
pq->size--;
}读取头数据：直接读取head指向的数据即可
//读取头个数据
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(QueueEmpty(pq));
return pq->head->data;
}读取尾数据：读取tail指向的数据即可
//读取最后一个数据
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(QueueEmpty(pq));
return pq->tail->data;
}head和tail为空则为空
//判断是否为空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head && pq->tail;
}返回size即可
//判断数据的数量
int QueueSize(Queue* pq)
{
assert(pq);
assert(QueueEmpty(pq));
return pq->size;
}一个空间一个空间释放即可
//释放空间
void QueueDestroy(Queue* pq)
{
assert(pq);
while (pq->head)//一个节点一个节点释放
{
QNode* cur = pq->head->next;
free(pq->head);
pq->head = cur;
}
pq->head = NULL;
pq->tail = NULL;
pq->size = 0;
}总结
以上就是今天要讲的内容，希望铁子们可以有所收货。
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
名称栏目：C语言数据结构——栈和队列-创新互联
本文URL：http://cdiso.cn/article/dchpdh.html
