【数据结构】栈和队列--＞理解和实现（赋源码)-天翼云

【数据结构】栈和队列--＞理解和实现（赋源码)

2025-04-22 09:27:37 阅读次数：5

前面介绍了顺序表、单链表、双向循环链表，基本上已经结束了链表的讲解，今天谈一下栈、队列。可以简单的说是前面学习的一特殊化实现，但是总体是相似的。

前言

栈是一种特殊的线性表，它只允许在一端进行插入和删除操作。这一端被称为栈顶，另一端被称为栈底。栈的特点是后进先出（LIFO），即最后进入的元素最先被移除。

队列是另一种特殊的线性表，它允许在一端进行插入操作，在另一端进行删除操作。插入操作的一端称为队尾，删除操作的一端称为队头。队列的特点是先进先出（FIFO），即最先进入的元素最先被移除。

栈和队列有各自的特点，严格讲用顺序表还是链表的实现都可以。但我们根据结构特点选择一个更加适合的结构进行是实现。

一、栈和队列的理解

对于栈的理解：

【数据结构】栈和队列--＞理解和实现（赋源码)

栈如同这个图一样，要是想拿出数据，必须从上面一个一个往下面拿。这也正是 LIFO 的体现。

对于队列的理解：

【数据结构】栈和队列--＞理解和实现（赋源码)

队列如同这个图一样，要是想拿出数据，必须前面一个一个往向后面拿。这也正是 FIFO 的体现。

二、栈的实现（顺组表）

2.1 栈的功能

//初始化
void STInit(ST* ps);
//压栈
void STpush(ST* ps, STDataType x);
//删除
void STPop(ST* ps);
//大小
int STSize(ST* ps);
//判空
bool STEmpty(ST* ps);
//出栈
STDataType STTop(ST* ps);
//检查容量
void CheckCapacity(ST* ps);
//销毁
void STDestroy(ST* ps);

2.2 栈结构体的定义及其初始化

结构体的定义

typedef int STDataType;

typedef struct stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

初始化（开辟空间）

void STInit(ST* ps)
{
	assert(ps);
	ps->a = (STDataType*)malloc(sizeof(STDataType)*4);
	if (ps->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	
	ps->capacity = 4;
	ps->top = 0;
}

2.3 压栈（存储数据）

//压栈
void STpush(ST* ps,STDataType x)
{
	assert(ps);

	ps->a[ps->top] = x;
	ps->top++;
}

2,4 删除数据

在这里面删除数据是配合，栈顶出栈。每次拿出一个数据，就要减少一个数据。

void STPop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));

	ps->top--;
}

2.5 计算栈内元个数

//大小
int STSize(ST* ps)
{
	assert(ps);

	return ps->top;
}

2.6 判断栈内是否为空

这里运用 bool 类型直接返回，比较方便。

bool STEmpty(ST* ps)
{
	assert(ps);

	return ps->top == 0;
}

2.7 出栈

//出栈
STDataType STTop(ST* ps)
{
	assert(ps);

	return ps->a[ps->top-1];
}

2.8 增加容量

//检查容量
void CheckCapacity(ST*ps)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		ST* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * (ps->capacity) * 2);
		if (tmp == NULL)
		{
			perror("malloc fail");
			return;
		}
		ps->capacity *= 2;
		ps->a = tmp;
	}
}

2.9 销毁栈

//销毁
void STDestroy(ST* ps)
{
	assert(ps);

	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

三、队列的实现（单链表）

3.1 队列的功能

//初始化
void QueueInit(Queue* ps);
//销毁
void QueueDestroy(Queue* ps);
//入队
void QueuePush(Queue* ps, QDataType x);
//删除
void QueuePop(Queue* ps);
//大小
int QueueSize(Queue* ps);
//判空队
bool QueueEmpty(Queue* ps);
//出队头
QDataType QueueTop(Queue* ps);
//出队尾
QDataType QueueBack(Queue* ps);

3.2 队列的结构体定义以及初始化

结构体定义

定义两个结构体，第一个为存放数据，第二个结构体为两个指针，分别指向头和尾

typedef int QDataType;

typedef struct QNode
{
	struct QNode* next;
	QDataType data;

}QNode;

typedef struct Queue
{
	QNode*head;
	QNode*tail;
	 
	int szie;
}Queue;

初始化

//初始化
void QueueInit(Queue* ps)
{
	assert(ps);

	ps->head = ps->tail = NULL;

	ps->szie = 0;

}

3.3 队列销毁

//销毁
void QueueDestroy(Queue* ps)
{
	assert(ps);
	QNode* cur = ps->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}

	ps->head = ps->tail = NULL;
	ps->szie = 0;
}

3.4 入队（插入数据）

//入队
void QueuePush(Queue* ps,QDataType x)
{
	assert(ps);

	QNode* newcode = (QNode*)malloc(sizeof(QNode));
	if (newcode == NULL)
	{
		perror("malloc fail");
		return ;
	}
	newcode->next = NULL;
	newcode->data = x;

	if (ps->head == NULL)
	{
		ps->head = ps->tail = newcode;
		
	}
	else

	{
		
		ps->tail->next = newcode;
		ps->tail = newcode;
	}

	ps->szie++;

}

3.5 删除数据（头删）

//删除
void QueuePop(Queue* ps)
{
	assert(ps);
	assert(ps->head != NULL);
	assert(!QueueEmpty(ps));

	if (ps->head->next == NULL)
	{
		free(ps->head);
		ps->head = ps->tail = NULL;
	}
	else
	{
		QNode* next = ps->head->next;
		free(ps->head);
		ps->head = next;

	}
	ps->szie--;
}

3.6 计算队列元素个数

//大小
int QueueSize(Queue* ps)
{
	assert(ps);

	return ps->szie;
}

3.7 判断是否队列为空

//判空队
bool QueueEmpty(Queue* ps)
{
	assert(ps);

	return ps->szie == 0;
}

3.8 出队（头）

//出队头
QDataType QueueTop(Queue* ps)
{
	assert(ps);
	assert(!QueueEmpty(ps));

	return ps->head->data;
}

3.9 出队（尾）

//出队尾
QDataType QueueBack(Queue* ps)
{
	assert(ps);

	return ps->tail->data;
}

四、栈和队列的源码

栈

Stack.h

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>


typedef int STDataType;

typedef struct stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

//初始化
void STInit(ST* ps);
//压栈
void STpush(ST* ps, STDataType x);
//删除
void STPop(ST* ps);
//大小
int STSize(ST* ps);
//判空
bool STEmpty(ST* ps);
//出栈
STDataType STTop(ST* ps);
//检查容量
void CheckCapacity(ST* ps);
//销毁
void STDestroy(ST* ps);

Stack.c

#define _CRT_SECURE_NO_WARNINGS


#include "stack.h"


//初始化
void STInit(ST* ps)
{
	assert(ps);
	ps->a = (STDataType*)malloc(sizeof(STDataType*)*4);
	if (ps->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	
	ps->capacity = 4;
	ps->top = 0;
}
//销毁
void STDestroy(ST* ps)
{
	assert(ps);

	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

//检查容量
void CheckCapacity(ST*ps)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		ST* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * (ps->capacity) * 2);
		if (tmp == NULL)
		{
			perror("malloc fail");
			return;
		}
		ps->capacity *= 2;
		ps->a = tmp;
	}
}

//压栈
void STpush(ST* ps,STDataType x)
{
	assert(ps);

	ps->a[ps->top] = x;
	ps->top++;
}

//删除
void STPop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));

	ps->top--;
}

//判空
bool STEmpty(ST* ps)
{
	assert(ps);

	return ps->top == 0;
}

//出栈
STDataType STTop(ST* ps)
{
	assert(ps);

	return ps->a[ps->top-1];
}

//大小
int STSize(ST* ps)
{
	assert(ps);

	return ps->top;
}

test.c

#define _CRT_SECURE_NO_WARNINGS


#include "stack.h"

void teststack()
{
	ST st;
	STInit(&st);

	STpush(&st, 1);
	STpush(&st, 2);
	STpush(&st, 3);
	STpush(&st, 4);
	STpush(&st, 5);

	printf("%d", STSize(&st));
	printf("\n");

	while (!STEmpty(&st))
	{
		printf("%d ", STTop(&st));
		STPop(&st);
	}
	printf("\n");
	printf("%d", STSize(&st));

	STDestroy(&st);

}



int main()
{
	teststack();

	return 0;
}

队列

Queue.h

#pragma once

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int QDataType;

typedef struct QNode
{
	struct QNode* next;
	QDataType data;

}QNode;

typedef struct Queue
{
	QNode*head;
	QNode*tail;
	 
	int szie;
}Queue;


//单链表的实现，FIFO

//初始化
void QueueInit(Queue* ps);
//销毁
void QueueDestroy(Queue* ps);
//入队
void QueuePush(Queue* ps, QDataType x);
//删除
void QueuePop(Queue* ps);
//大小
int QueueSize(Queue* ps);
//判空队
bool QueueEmpty(Queue* ps);
//出队头
QDataType QueueTop(Queue* ps);
//出队尾
QDataType QueueBack(Queue* ps);

Queue.c

#define _CRT_SECURE_NO_WARNINGS

#include "queue.h"



//初始化
void QueueInit(Queue* ps)
{
	assert(ps);

	ps->head = ps->tail = NULL;

	ps->szie = 0;

}

//销毁
void QueueDestroy(Queue* ps)
{
	assert(ps);
	QNode* cur = ps->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}

	ps->head = ps->tail = NULL;
	ps->szie = 0;
}

//入队
void QueuePush(Queue* ps,QDataType x)
{
	assert(ps);

	QNode* newcode = (QNode*)malloc(sizeof(QNode));
	if (newcode == NULL)
	{
		perror("malloc fail");
		return ;
	}
	newcode->next = NULL;
	newcode->data = x;

	if (ps->head == NULL)
	{
		ps->head = ps->tail = newcode;
		
	}
	else

	{
		
		ps->tail->next = newcode;
		ps->tail = newcode;
	}

	ps->szie++;

}

//删除
void QueuePop(Queue* ps)
{
	assert(ps);
	assert(ps->head != NULL);
	assert(!QueueEmpty(ps));

	if (ps->head->next == NULL)
	{
		free(ps->head);
		ps->head = ps->tail = NULL;
	}
	else
	{
		QNode* next = ps->head->next;
		free(ps->head);
		ps->head = next;

	}
	ps->szie--;
}

//大小
int QueueSize(Queue* ps)
{
	assert(ps);

	return ps->szie;
}

//判空队
bool QueueEmpty(Queue* ps)
{
	assert(ps);

	return ps->szie == 0;
}

//出队头
QDataType QueueTop(Queue* ps)
{
	assert(ps);
	assert(!QueueEmpty(ps));

	return ps->head->data;
}

//出队尾
QDataType QueueBack(Queue* ps)
{
	assert(ps);

	return ps->tail->data;
}

test.c

#define _CRT_SECURE_NO_WARNINGS

#include "queue.h"



void testQueue()
{
	Queue s;
	QueueInit(&s);

	QueuePush(&s, 1);
	QueuePush(&s, 2);
	QueuePush(&s, 3);
	QueuePush(&s, 4);

	

	//printf("%d ", QueueTop(&s));
	//QueuePop(&s);
	//printf("%d ", QueueTop(&s));
	//QueuePop(&s);	
	//printf("%d ", QueueTop(&s));
	//QueuePop(&s);	
	//printf("%d ", QueueTop(&s));
	//QueuePop(&s);
	//printf("\n");

	while (!(QueueEmpty(&s)))
	{
		printf("%d ", QueueTop(&s));
		QueuePop(&s);
	}


	QueueDestroy(&s);

}

int main()
{
	testQueue();


	return 0;
}

版权声明：本文内容来自第三方投稿或授权转载，原文地址：https://chian-ocean.blog.csdn.net/article/details/139523310，作者：chian-ocean，版权归原作者所有。本网站转在其作品的目的在于传递更多信息，不拥有版权，亦不承担相应法律责任。如因作品内容、版权等问题需要同本网站联系，请发邮件至ctyunbbs@chinatelecom.cn沟通。

活动

智算服务

应用商城

合作伙伴

开发者

支持与服务

了解天翼云

【数据结构】栈和队列--＞理解和实现（赋源码)

【数据结构】栈和队列--＞理解和实现（赋源码)

前言

一、栈和队列的理解

对于栈的理解：

对于队列的理解：

二、栈的实现（顺组表）

2.1 栈的功能

2.2 栈结构体的定义及其初始化

结构体的定义

初始化（开辟空间）

2.3 压栈（存储数据）

2,4 删除数据

2.5 计算栈内元个数

2.6 判断栈内是否为空

2.7 出栈

2.8 增加容量

2.9 销毁栈

三、队列的实现（单链表）

3.1 队列的功能

3.2 队列的结构体定义以及初始化

结构体定义

初始化

3.3 队列销毁

3.4 入队（插入数据）

3.5 删除数据（头删）

3.6 计算队列元素个数

3.7 判断是否队列为空

3.8 出队（头）

3.9 出队（尾）

四、栈和队列的源码

栈

Stack.h

Stack.c

test.c

队列

Queue.h

Queue.c

test.c

相关文章

【NetApp数据恢复】误操作导致NetApp存储的卷丢失，卷内虚拟机无法访问的数据恢复案例

js本地上传图片后实现预览与删除功能

外设驱动库开发笔记54：外设库驱动设计改进的思考

BFS解决拓扑排序(1)_课程表

Linux系统基础-多线程超详细讲解(5)_单例模式与线程池

画图时使用的函数和一些错误处理

超级好用的C++实用库之国密sm4算法

C++ 11新特性之tuple

30天拿下Rust之引用

30天拿下Rust之所有权

作者介绍

最新文章

外设驱动库开发笔记54：外设库驱动设计改进的思考

Linux系统基础-多线程超详细讲解(5)_单例模式与线程池

超级好用的C++实用库之国密sm4算法

C++ 11新特性之tuple

AJAX-事件循环（超详细过程）

数据结构-队列

热门文章

Python|斐波那契数列

游戏编程之十一 图像页CPICPAGE介绍

PHP：将list列表转为tree树形数据

Python爬虫：scrapy爬虫设置随机访问时间间隔

数据结构与算法之七 栈

Python编程：Crypto模块RSA非对称加密

热门标签

相关产品

弹性云主机

天翼云电脑（公众版）

对象存储

云硬盘

随机文章

如何加快外包式的定制化开发系列分享--完成后端接口编写

游戏编程之十一图像页CPICPAGE介绍

数据结构与算法之七栈

【C++单调队列前缀和】862. 和至少为 K 的最短子数组|2306