栈和队列详解
一、什么是栈和队列
（1）栈：
栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素————百度百科
由此可见栈是一种先进后出（First In Last Out）即FILO结构。
（2）队列
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头————百度百科
队列是一种先进先出（First In First Out）的结构即FIFO结构。
二、线性栈的操作实现
栈可分为线性栈和链式栈，不同的实现方法匹配于不同的场景。
（1）栈的结构定义：
typedef int STDataType;
typedef struct Stack {
STDataType* a;//线性栈需要数组
int top;//栈顶指针记录元素个数
int capacity;//栈的容量
}ST;（2）栈的初始化：
ST* InitNewStack(STDataType n)
{
ST* p = (ST*)malloc(sizeof(ST));//初始化生成栈
p->a = (STDataType*)malloc(sizeof(STDataType) * n);//对栈的数组进行开辟
if (p->a == NULL)//开辟检查
{
perror("malloc");
exit(-1);
}
p->top = -1;//将指针置为-1，也可以为0，只不过后续实现有稍微不同
p->capacity = n;//将容量设置好
return p;//返回新的栈
}（3）入栈操作：
void StackPush(ST* st, STDataType x)
{
assert(st);
if (st->top == st->capacity)//检查栈是否满了
{
STDataType* tmp = (STDataType*)realloc(st->a, sizeof(st->capacity) * 2 * sizeof(STDataType));//栈满了进行扩容操作
if (tmp == NULL)//扩容检查
{
perror("realloc");
exit(-1);
}
st->a = tmp;
st->capacity *= 2;//将容量记录扩大
}
st->a[++st->top] = x;//对元素进行入栈，栈顶元素+1
}（4）出栈操作：
void StackPop(ST* st)
{
assert(st);//断言是否为空栈
if (st->top >= 0)
st->top -= 1;//只要不为空栈，仅仅将栈顶指针-1即可
return;
}（5）栈判空：
bool StackEmpty(ST* st)
{
assert(st);
return st->top == -1;//当top为-1表示空栈
}（6）取栈顶元素：
STDataType StackFront(ST* st)
{
assert(st);
return st->a[st->top];//直接返回栈顶元素即可
}（7）打印栈：
void Print(ST* st)//进行打印
{
assert(st);
int len = sizeof(st->a) / sizeof(STDataType);
int i = 0;
for (i = 0; i <= st->top; i++)
{
printf("%3d", i);
}
printf("\n");
for (i = 0; i <= st->top; i++)
{
printf("---");
}
printf("\n");
for (i = 0; i <= st->top; i++)
{
printf("%3d", st->a[i]);
}
printf("\n\n\n");
return;
}（8）销毁栈：
void StackClear(ST* st)//由内而外进行销毁，防止内存泄漏
{
assert(st);
free(st->a);
st->a = NULL;
free(st);
st = NULL;
return;
}（9）测试栈：
void Test()
{
ST* st = InitNewStack(MAX_OP);
int i = 0;
StackPush(st, 1);
if (!StackEmpty(st))
{
StackPush(st, 2);
StackPush(st, 3);
StackPush(st, 4);
StackPush(st, 5);
StackPush(st, 6);
StackPush(st, 7);
StackPush(st, 8);
Print(st);
}
if (!StackEmpty(st))
{
StackPop(st);
StackPop(st);
StackPop(st);
Print(st);
}
printf("StackFront: %d\n", StackFront(st));
StackClear(st);
return;
}结果打印为：
怎么样，栈的操作实现是不是挺简单的，也没有想象的那么难，下面我们看看链式栈的实现方式吧。
三、链式栈的操作实现
（1）栈的结构定义：
typedef int STDataType;
typedef struct STNode {//栈的元素
struct STNode* next;//指针域
STDataType data;//数据域
}Node;
typedef struct Stack {//栈顶指针
Node* top;
}ST;（2）栈的初始化：
Node* InitNewNode(STDataType x)//栈节点的初始化
{
Node* p = (Node*)malloc(sizeof(Node));//开辟新节点
if (p == NULL)//节点检查
{
perror("malloc");
exit(-1);
}
p->next = NULL;//指针域置空
p->data = x;//数据域赋值
return p;//返回新节点
}
void InitNewST(ST* st)
{
assert(st);
st->top = NULL;//将栈顶指针置空
return;
}（3）入栈操作：
void StackPush(ST* st, STDataType x)
{
assert(st);
if (st->top == NULL)//栈顶指针为空时
{
Node* node = InitNewNode(x);
st->top = node;
return;
}
Node* node = InitNewNode(x);
node->next = st->top;//头插法入栈
st->top = node;//栈顶指针指向头节点
return;
}（4）出栈操作：
void StackPop(ST* st)
{
assert(st);
if (st->top == NULL)//空栈直接返回
return;
if (st->top->next)//栈的元素大于1个
{
Node* tmp = st->top;//直接进行头删
st->top = tmp->next;//指针指向下一个节点
free(tmp);
return;
}
free(st->top);//只有一个节点直接删除，并将top置空
st->top = NULL;
return;
}（5）栈判空：
bool StackEmpty(ST* st)
{
assert(st);
return st->top == NULL;//top不为空指针
}（6）取栈顶元素：
Node* StackTop(ST* st)
{
assert(st);
return st->top;//直接返回栈顶节点
}（7）打印栈：
void output(ST* st)
{
assert(st);
Node* p = st->top;
int len = 0;
while (p)
{
p = p->next;
len += 1;
}
int i = 0;
for (i = 0; i < len; i++)
{
printf("%3d", i);
printf(" ");
}
printf("\n");
for (i = 0; i < len; i++)
{
printf("-----");
}
printf("\n");
p = st->top;
while (p)
{
printf("%3d", p->data);
printf("->");
p = p->next;
}
printf("\n\n\n");
return;
}（8）销毁栈：
void StackDestroy(ST* st)
{
assert(st);
while (st->top)
{
Node* tmp = st->top->next;//记录栈顶指针的下一个元素
free(st->top);//释放掉当前元素
st->top = tmp;//再把栈顶指针指向下一个元素
}
return;
}（9）测试栈：
void Test()
{
ST st;
InitNewST(&st);
StackPush(&st, 5);
StackPush(&st, 4);
StackPush(&st, 3);
StackPush(&st, 2);
StackPush(&st, 1);
output(&st);
if (!StackEmpty(&st))
{
StackPop(&st);
StackPop(&st);
output(&st);
}
Node* p = StackTop(&st);
printf("The Stack Top Element is %d\n", p->data);
StackDestroy(&st);
return;
}测试结果：
四、队列的操作实现
这里队列就不实现线性队列了，线性队列可以参考上面的线性栈来写，这里主要实现一下链式队列
（1）队列的结构定义：
typedef int QDataType;
typedef struct QueueNode {//链式队列节点
struct QueueNode* next;
QDataType data;
}QNode;
typedef struct Queue {//队列
QNode* head;//队列头指针
QNode* tail;//队列尾指针
int size;//大小
}Que;（2）队列的初始化：
void InitNewQueue(Que* q)
{
assert(q);
q->head = q->tail = NULL;//头尾节点置空
q->size = 0;//初始化长度为0
return;
}（3）入队操作：
void QueuePush(Que* q, QDataType x)
{
assert(q);
QNode* newnode = (QNode*)malloc(sizeof(QNode));//开辟新的链式队列节点
if (newnode == NULL)//检测是否开辟失败
{
perror("malloc");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
if (q->tail == NULL)//尾指针为空即队列为空
{
q->head = q->tail = newnode;//头尾指针指向同一个元素
}
else//队列不为空
{
q->tail->next = newnode;//入队
q->tail = newnode;
}
q->size++;//记录大小
return;
}（4）出队操作：
void QueuePop(Que* q)
{
assert(q);
if (q->head->next == NULL)//只有一个节点
{
free(q->head);
q->head = q->tail = NULL;//将头尾节点置空
}
else//大于一个节点数量
{
QNode* next = q->head->next;//记录头指针下一个节点
free(q->head);//释放当前节点
q->head = next;//头指针移动
}
q->size -= 1;//记录大小
return;
}（5）队列判空：
bool QueueEmpty(Que* q)
{
assert(q);
return q->head == NULL;
}（6）取队首队尾元素：
QDataType QueueFront(Que* q)
{
assert(q);
assert(!QueueEmpty(q));//不为空队列直接返回头指针数据域
return q->head->data;
}
QDataType QueueBack(Que* q)
{
assert(q);
assert(!QueueEmpty(q));//不为空队列直接返回尾指针数据域
return q->tail->data;
}（7）队列大小：
QDataType QueueSize(Que* q)
{
assert(q);
return q->size;
}（8）销毁队列：
void QueueDestroy(Que* q)
{
assert(q);
while (q->head)//头指针不为空
{
QNode* tmp = q->head->next;//记录下头指针下一个节点
free(q->head);//释放当前节点
q->head = tmp;
}
q->head = q->tail = NULL;//头尾指针置空
q->size = 0;//数量清零
return;
}（9）测试队列：
void Test()
{
Que q;
InitNewQueue(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
QueuePush(&q, 5);
QueuePush(&q, 6);
printf("QueueSize : %d\n", QueueSize(&q));
while (!QueueEmpty(&q))
{
printf("%d ", QueueFront(&q));
QueuePop(&q);
}
printf("\n");
QueueDestroy(&q);
return;
}输出结果为：
如果你看到这里，觉得这篇文章对你有帮助的话，还望能三连支持一下~
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2023-11-11，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
相关产品与服务
腾讯云服务器利旧
云服务器（Cloud Virtual Machine，CVM）提供安全可靠的弹性计算服务。 您可以实时扩展或缩减计算资源，适应变化的业务需求，并只需按实际使用的资源计费。使用 CVM 可以极大降低您的软硬件采购成本，简化 IT 运维工作。
腾讯云开发者
