文档建议反馈控制台
首页
学习
活动
专区
圈层
工具
MCP广场
文章/答案/技术大牛
发布
社区首页 >专栏 >深入了解栈与队列:从基础到应用

深入了解栈与队列:从基础到应用

作者头像
夜雨声烦1413
发布于 2026-01-12 15:10:00
发布于 2026-01-12 15:10:00
1380
举报

嘿嘿,家人们,今天咱们来详细剖析数据结构中的栈和队列,好啦,废话不多讲,开干!

1.:栈

1.1:栈的概念与结构

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

1.2:栈的实现

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

1.2.1:Stack.h
代码语言：javascript
复制
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int STDataType;

typedef struct Stack
{
	STDataType* _arr;
	//指向栈顶
	int _top;
	//容量
	int _capacity;
}Stack;


void StackInit(Stack* pst);
//入栈
void StackPush(Stack* pst, STDataType data);
// 出栈
void StackPop(Stack* pst);

// 获取栈顶元素
STDataType StackTop(Stack* ps);

// 获取栈中有效元素个数
int StackSize(Stack* pst);

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* pst);

// 销毁栈
void StackDestroy(Stack* pst);
1.2.2:Stack.c
1.2.2.1:初始化与入栈与出栈与获取栈顶元素
代码语言：javascript
复制
#define _CRT_SECURE_NO_WARNINGS
#include "Stack.h"

void StackInit(Stack* pst)
{
	assert(pst);
	pst->_arr = NULL;
	//指向栈顶,一开始没有元素
	pst->_top = -1;
	pst->_capacity = 0;
}

void CheckCapacity(Stack * pst)
{
	assert(pst);
	if(pst->_top + 1 == pst->_capacity)
	{
		int NewCapacity = pst->_capacity == 0 ? 4 : pst->_capacity * 2;
		//如果传了个空指针,就等价于malloc(NewCapacity *  sizeof(STDataType))
		STDataType * Tmp = (STDataType*)realloc(pst->_arr, NewCapacity *  sizeof(STDataType));
		if(Tmp == NULL)
		{
			perror("realloc fail");
			exit;
		}
		pst->_arr = Tmp;
		pst->_capacity = NewCapacity;
	}
}

void StackPush(Stack* pst, STDataType data)
{
	assert(pst);
	CheckCapacity(pst);
	//由于top指向的是栈顶,因此先++,在入栈
	pst->_top++;
	pst->_arr[pst->_top] = data;
}

void StackPop(Stack* pst)
{
	assert(pst);
	//确保栈里面有元素
	assert(pst->_top >= 0);
	pst->_top--;
}

// 获取栈顶元素
STDataType StackTop(Stack* pst)
{
	assert(pst);
	assert(pst->_top >= 0);
	return pst->_arr[pst->_top];
}
1.2.2.2:获取元素个数与判断栈为空与销毁栈
代码语言：javascript
复制
// 获取栈中有效元素个数
int StackSize(Stack* pst)
{
	assert(pst);
	//top指向的是栈顶,因此要 + 1,数组下标从0开始
	return pst->_top + 1;
}


// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* pst)
{
	assert(pst);
	if (pst->_top == -1)
		return 1;
	return 0;

}

// 销毁栈
void StackDestroy(Stack* pst)
{
	assert(pst);
	free(pst->_arr);
	pst->_arr = NULL;
	pst->_top = -1;
	pst->_capacity = 0;
}
1.2.3:Test.c
1.2.3.1:测试初始化与入栈与出栈与获取栈顶元素
代码语言：javascript
复制
#include "Stack.h"

void TestPushAndPop(Stack* pst)
{
	StackInit(pst);
	StackPush(pst,1);
	printf("%d\n", StackTop(pst));
	StackPush(pst,2);
	printf("%d\n", StackTop(pst));
	StackPush(pst,3);
	printf("%d\n", StackTop(pst));
	StackPush(pst,4);
	printf("%d\n", StackTop(pst));

	printf("--------------------------------\n");
	printf("%d\n", StackTop(pst));
	StackPop(pst);
	printf("%d\n", StackTop(pst));
	StackPop(pst);
	printf("%d\n", StackTop(pst));
	StackPop(pst);
	printf("%d\n", StackTop(pst));
	StackPop(pst);
}

int main()
{
	Stack pst;
	TestPushAndPop(&pst);
	return 0;
}
1.2.3.2:测试获取元素个数与判断栈为空与销毁栈
代码语言：javascript
复制
#include "Stack.h"

void TestPushAndPop(Stack* pst)
{
	StackInit(pst);
	StackPush(pst,1);
	printf("%d\n", StackTop(pst));
	StackPush(pst,2);
	printf("%d\n", StackTop(pst));
	StackPush(pst,3);
	printf("%d\n", StackTop(pst));
	StackPush(pst,4);
	printf("%d\n", StackTop(pst));

	printf("--------------------------------\n");
	printf("%d\n", StackTop(pst));
	StackPop(pst);
	printf("%d\n", StackTop(pst));
	StackPop(pst);
	printf("%d\n", StackTop(pst));
	StackPop(pst);
	printf("%d\n", StackTop(pst));
	StackPop(pst);
}

void TestOther(Stack * pst)
{
	StackInit(pst);
	StackPush(pst, 1);
	StackPush(pst, 2);
	StackPush(pst, 3);
	StackPush(pst, 4);
	//为空返回非0数字,非空则为0
	while(!StackEmpty(pst))
	{
		printf("%d And Size == %d\n", StackTop(pst), StackSize(pst));
		StackPop(pst);
	}
	StackDestroy(pst);
}

int main()
{
	Stack pst;
	/*TestPushAndPop(&pst);*/
	TestOther(&pst);
	return 0;
}

1.3:栈的总代码

1.3.1:Stack.h
代码语言：javascript
复制
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int STDataType;

typedef struct Stack
{
	STDataType* _arr;
	//指向栈顶
	int _top;
	//容量
	int _capacity;
}Stack;


void StackInit(Stack* pst);
//入栈
void StackPush(Stack* pst, STDataType data);
// 出栈
void StackPop(Stack* pst);

// 获取栈顶元素
STDataType StackTop(Stack* ps);

// 获取栈中有效元素个数
int StackSize(Stack* pst);

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* pst);

// 销毁栈
void StackDestroy(Stack* pst);
1.3.2:Stack.c
代码语言：javascript
复制
#define _CRT_SECURE_NO_WARNINGS
#include "Stack.h"

void StackInit(Stack* pst)
{
	assert(pst);
	pst->_arr = NULL;
	//指向栈顶,一开始没有元素
	pst->_top = -1;
	pst->_capacity = 0;
}

void CheckCapacity(Stack* pst)
{
	assert(pst);
	if (pst->_top + 1 == pst->_capacity)
	{
		int NewCapacity = pst->_capacity == 0 ? 4 : pst->_capacity * 2;
		//如果传了个空指针,就等价于malloc(NewCapacity *  sizeof(STDataType))
		STDataType* Tmp = (STDataType*)realloc(pst->_arr, NewCapacity * sizeof(STDataType));
		if (Tmp == NULL)
		{
			perror("realloc fail");
			exit;
		}
		pst->_arr = Tmp;
		pst->_capacity = NewCapacity;
	}
}

void StackPush(Stack* pst, STDataType data)
{
	assert(pst);
	CheckCapacity(pst);
	//由于top指向的是栈顶,因此先++,在入栈
	pst->_top++;
	pst->_arr[pst->_top] = data;
}

void StackPop(Stack* pst)
{
	assert(pst);
	//确保栈里面有元素
	assert(pst->_top >= 0);
	pst->_top--;
}

// 获取栈顶元素
STDataType StackTop(Stack* pst)
{
	assert(pst);
	assert(pst->_top >= 0);
	return pst->_arr[pst->_top];
}

// 获取栈中有效元素个数
int StackSize(Stack* pst)
{
	assert(pst);
	//top指向的是栈顶,因此要 + 1,数组下标从0开始
	return pst->_top + 1;
}


// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* pst)
{
	assert(pst);
	if (pst->_top == -1)
		return 1;
	return 0;

}

// 销毁栈
void StackDestroy(Stack* pst)
{
	assert(pst);
	free(pst->_arr);
	pst->_arr = NULL;
	pst->_top = -1;
	pst->_capacity = 0;
}
1.3.3:Test.c
代码语言：javascript
复制
#include "Stack.h"

void TestPushAndPop(Stack* pst)
{
	StackInit(pst);
	StackPush(pst,1);
	printf("%d\n", StackTop(pst));
	StackPush(pst,2);
	printf("%d\n", StackTop(pst));
	StackPush(pst,3);
	printf("%d\n", StackTop(pst));
	StackPush(pst,4);
	printf("%d\n", StackTop(pst));

	printf("--------------------------------\n");
	printf("%d\n", StackTop(pst));
	StackPop(pst);
	printf("%d\n", StackTop(pst));
	StackPop(pst);
	printf("%d\n", StackTop(pst));
	StackPop(pst);
	printf("%d\n", StackTop(pst));
	StackPop(pst);
}

void TestOther(Stack * pst)
{
	StackInit(pst);
	StackPush(pst, 1);
	StackPush(pst, 2);
	StackPush(pst, 3);
	StackPush(pst, 4);
	//为空返回非0数字,非空则为0
	while(!StackEmpty(pst))
	{
		printf("%d And Size == %d\n", StackTop(pst), StackSize(pst));
		StackPop(pst);
	}
	StackDestroy(pst);
}

int main()
{
	Stack pst;
	/*TestPushAndPop(&pst);*/
	TestOther(&pst);
	return 0;
}

2:队列

2.1:队列的概念与结构

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据,效率会比较低.

2.2:队列的实现

2.2.1:Queue.h
代码语言：javascript
复制
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef int QListDataType;


//队列的节点
typedef struct QueueNode
{
	QListDataType _Value;
	struct QueueNode* _Next;
}QNode;

typedef struct Queue
{
	//队头
	QNode* _Front;
	//队尾
	QNode* _Tail;
	int _size;
}Queue;

// 初始化队列
void QueueInit(Queue* q);

// 队尾入队列
void QueuePush(Queue* q, QListDataType data);

// 队头出队列
void QueuePop(Queue* q);

// 获取队列头部元素
QListDataType QueueFront(Queue* q);

// 获取队列队尾元素
QListDataType QueueBack(Queue* q);

// 获取队列中有效元素个数
int QueueSize(Queue* q);

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q);

// 销毁队列
void QueueDestroy(Queue* q);
2.2.2:Queue.c
2.2.2.1:初始化与入队列和出队列与获取队列元素个数
代码语言：javascript
复制
#define _CRT_SECURE_NO_WARNINGS
#include "Queue.h"

// 初始化队列
void QueueInit(Queue* q)
{
	assert(q);
	q->_Front = NULL;
	q->_Tail = NULL;
	q->_size = 0;
}


// 队尾入队列
void QueuePush(Queue* q, QListDataType Value)
{
	assert(q);
	QNode* NewNode = (QNode*)malloc(sizeof(QNode));
	if (NewNode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	NewNode->_Next = NULL;
	NewNode->_Value = Value;
	//队头和队尾指向一致时
	if (q->_Front == NULL)
	{
		q->_Front = NewNode;
		q->_Tail = NewNode;
	}
	else
	{
		//链接新节点
		q->_Tail->_Next = NewNode;
		//队尾指向新节点
		q->_Tail = NewNode;
	}
	q->_size++;
}

// 队头出队列
void QueuePop(Queue* q)
{
	assert(q);
	assert(q->_Front && q->_Tail);
	if(q->_Front == q->_Tail)
	{
		free(q->_Front);
		q->_Front = q->_Tail = NULL;
	}
	else
	{
		//保留下一个节点
		QNode* Temp = q->_Front->_Next;
		//释放旧节点
		free(q->_Front);
		//指向新节点
		q->_Front = Temp;
	}
	q->_size--;
}

// 获取队列中有效元素个数
int QueueSize(Queue* q)
{
	return q->_size;
}
2.2.2.2:获取队头与队尾与判断队列为空与销毁队列
代码语言：javascript
复制
#define _CRT_SECURE_NO_WARNINGS
#include "Queue.h"


// 获取队列中有效元素个数
int QueueSize(Queue* q)
{
	return q->_size;
}

// 获取队列头部元素
QListDataType QueueFront(Queue* q)
{
	assert(q && q->_Front);
	return q->_Front->_Value;
}

// 获取队列队尾元素
QListDataType QueueBack(Queue* q)
{
	assert(q && q->_Tail);
	return q->_Tail->_Value;
}



// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q)
{
	return q->_size == 0 ? true : false;
}

// 销毁队列
void QueueDestroy(Queue* q)
{
	QNode* Current = q->_Front;
	while (Current != NULL)
	{
		//保留下一个节点
		QNode* Temp = Current->_Next;
		free(Current);
		Current = Temp;
	}
	q->_Front = NULL;
	q->_Tail = NULL;
	q->_size = 0;

}
2.2.3:Test.c
2.2.3.1:测试初始化与入队列和出队列与获取队列元素个数
代码语言：javascript
复制
#include "Queue.h"

void TestPushAndPop(Queue * q)
{
	QueueInit(q);
	QueuePush(q, 2);
	QueuePush(q, 3);
	QueuePush(q, 4);
	QueuePush(q, 5);
	printf("size == %d\n", QueueSize(q));
	QueuePop(q);
	QueuePop(q);
	QueuePop(q);
	QueuePop(q);
	printf("size == %d\n", QueueSize(q));
}

int main()
{
	Queue q;
	TestPushAndPop(&q);
	return 0;
}
2.2.3.2:测试获取队头与队尾与判断队列为空与销毁队列
代码语言：javascript
复制
#include "Queue.h"

void TestOther(Queue* q)
{
	QueueInit(q);
	QueuePush(q, 2);
	QueuePush(q, 3);
	QueuePush(q, 4);
	QueuePush(q, 5);
	printf("size == %d And Front == %d And Tail == %d\n", QueueSize(q),QueueFront(q),QueueBack(q));
	QueuePop(q);
	printf("size == %d And Front == %d And Tail == %d\n", QueueSize(q), QueueFront(q), QueueBack(q));
	QueuePop(q);
	printf("size == %d And Front == %d And Tail == %d\n", QueueSize(q), QueueFront(q), QueueBack(q));
	QueueDestroy(q);
}

int main()
{
	Queue q;
	TestOther(&q);
	return 0;
}

3:队列的总代码

3.1:Queue.h

代码语言：javascript
复制
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef int QListDataType;


//队列的节点
typedef struct QueueNode
{
	QListDataType _Value;
	struct QueueNode* _Next;
}QNode;

typedef struct Queue
{
	//队头
	QNode* _Front;
	//队尾
	QNode* _Tail;
	int _size;
}Queue;

// 初始化队列
void QueueInit(Queue* q);

// 队尾入队列
void QueuePush(Queue* q, QListDataType data);

// 队头出队列
void QueuePop(Queue* q);

// 获取队列头部元素
QListDataType QueueFront(Queue* q);

// 获取队列队尾元素
QListDataType QueueBack(Queue* q);

// 获取队列中有效元素个数
int QueueSize(Queue* q);

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q);

// 销毁队列
void QueueDestroy(Queue* q);

3.2:Queue.c

代码语言：javascript
复制
#define _CRT_SECURE_NO_WARNINGS
#include "Queue.h"

// 初始化队列
void QueueInit(Queue* q)
{
	assert(q);
	q->_Front = NULL;
	q->_Tail = NULL;
	q->_size = 0;
}


// 队尾入队列
void QueuePush(Queue* q, QListDataType Value)
{
	assert(q);
	QNode* NewNode = (QNode*)malloc(sizeof(QNode));
	if (NewNode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	NewNode->_Next = NULL;
	NewNode->_Value = Value;
	//队头和队尾指向一致时
	if (q->_Front == NULL)
	{
		q->_Front = NewNode;
		q->_Tail = NewNode;
	}
	else
	{
		//链接新节点
		q->_Tail->_Next = NewNode;
		//队尾指向新节点
		q->_Tail = NewNode;
	}
	q->_size++;
}

// 队头出队列
void QueuePop(Queue* q)
{
	assert(q);
	assert(q->_Front && q->_Tail);
	if(q->_Front == q->_Tail)
	{
		free(q->_Front);
		q->_Front = q->_Tail = NULL;
	}
	else
	{
		//保留下一个节点
		QNode* Temp = q->_Front->_Next;
		//释放旧节点
		free(q->_Front);
		//指向新节点
		q->_Front = Temp;
	}
	q->_size--;
}

// 获取队列中有效元素个数
int QueueSize(Queue* q)
{
	return q->_size;
}

// 获取队列头部元素
QListDataType QueueFront(Queue* q)
{
	assert(q && q->_Front);
	return q->_Front->_Value;
}

// 获取队列队尾元素
QListDataType QueueBack(Queue* q)
{
	assert(q && q->_Tail);
	return q->_Tail->_Value;
}



// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q)
{
	return q->_size == 0 ? true : false;
}

// 销毁队列
void QueueDestroy(Queue* q)
{
	QNode* Current = q->_Front;
	while (Current != NULL)
	{
		//保留下一个节点
		QNode* Temp = Current->_Next;
		free(Current);
		Current = Temp;
	}
	q->_Front = NULL;
	q->_Tail = NULL;
	q->_size = 0;

}

3.3:Test.c

代码语言：javascript
复制
#include "Queue.h"

void TestPushAndPop(Queue * q)
{
	QueueInit(q);
	QueuePush(q, 2);
	QueuePush(q, 3);
	QueuePush(q, 4);
	QueuePush(q, 5);
	printf("size == %d\n", QueueSize(q));
	QueuePop(q);
	QueuePop(q);
	QueuePop(q);
	QueuePop(q);
}

void TestOther(Queue* q)
{
	QueueInit(q);
	QueuePush(q, 2);
	QueuePush(q, 3);
	QueuePush(q, 4);
	QueuePush(q, 5);
	printf("size == %d And Front == %d And Tail == %d\n", QueueSize(q),QueueFront(q),QueueBack(q));
	QueuePop(q);
	printf("size == %d And Front == %d And Tail == %d\n", QueueSize(q), QueueFront(q), QueueBack(q));
	QueuePop(q);
	printf("size == %d And Front == %d And Tail == %d\n", QueueSize(q), QueueFront(q), QueueBack(q));
	QueueDestroy(q);
}

int main()
{
	Queue q;
	//TestPushAndPop(&q);
	TestOther(&q);
	return 0;
}

好啦,uu们,栈和队列的这部分滴详细内容博主就讲到这里啦,如果uu们觉得博主讲的不错的话,请动动你们滴小手给博主点点赞,你们滴鼓励将成为博主源源不断滴动力,同时也欢迎大家来指正博主滴错误~

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2026-01-12，如有侵权请联系 cloudcommunity@tencent.com 删除
数组
queue
stack
队列
基础

本文分享自 作者个人站点/博客 前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ，欢迎热爱写作的你一起参与！

数组
queue
stack
队列
基础
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
目录
  • 1.:栈
    • 1.1:栈的概念与结构
    • 1.2:栈的实现
      • 1.2.1:Stack.h
      • 1.2.2:Stack.c
      • 1.2.3:Test.c
    • 1.3:栈的总代码
      • 1.3.1:Stack.h
      • 1.3.2:Stack.c
      • 1.3.3:Test.c
  • 2:队列
    • 2.1:队列的概念与结构
    • 2.2:队列的实现
      • 2.2.1:Queue.h
      • 2.2.2:Queue.c
      • 2.2.3:Test.c
  • 3:队列的总代码
    • 3.1:Queue.h
    • 3.2:Queue.c
    • 3.3:Test.c
领券

腾讯云开发者

扫码关注腾讯云开发者

扫码关注腾讯云开发者

领取腾讯云代金券

热门产品

热门推荐

更多推荐

Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 粤公网安备44030502008569号

腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号

问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

Copyright © 2013 - 2026 Tencent Cloud.

All Rights Reserved. 腾讯云 版权所有

登录 后参与评论