首页 > 编程语言 >【数据结构】栈和队列--＞理解和实现（赋源码)

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

时间：2024-06-07 12:01:34浏览次数：29  
标签：ps head -- void Queue ST assert 源码 数据结构

Toc

欢迎光临我的Blog，喜欢就点歌关注吧♥

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

前言

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

  2. 队列是另一种特殊的线性表，它允许在一端进行插入操作，在另一端进行删除操作。插入操作的一端称为队尾，删除操作的一端称为队头。队列的特点是先进先出（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 = (ST*)malloc(sizeof(ST)*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 = (ST*)realloc(ps->a, sizeof(ST) * (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 = (ST*)malloc(sizeof(ST)*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 = (ST*)realloc(ps->a, sizeof(ST) * (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;
}

标签：ps,head,--,void,Queue,ST,assert,源码,数据结构
From： https://blog.csdn.net/Cayyyy/article/details/139523310

相关文章

  • 【2024-06-06】认清上进
    20:00我们都太专注于自己的伤口，忘了要去握住别人伸出的手。                                                 ——宫崎骏35岁之前，我们可以为了生活而牺牲一点生活时间......
  • 前端面试题日常练-day56 【面试题】
    题目希望这些选择题能够帮助您进行前端面试的准备，答案在文末1.PHP中的预定义变量$_SERVER用于存储什么类型的数据？a)用户的输入数据b)浏览器发送的请求信息c)服务器的配置信息d)PHP脚本中定义的变量2.在PHP中，以下哪个函数可以用于获取一个字符串的长度？a)str_l......
  • list 列表（属于集合collection中的一种）
    list类型，有序可变list内的数据可以混合，string+int等 取出集合内元素：list=["hello",11,33,"world"]（index索引从0开始）0123单个取出：(变量接收)=list[0]批量取出：(变量接收)=list[0:2]（此处范围包左不包右，去除的元素索引为0和1） 内置函数：(变......
  • 怎么能通过chatgpt-on-wechat获取全部的微信聊天信息
    要通过chatgpt-on-wechat工具获取全部的微信聊天信息，你可以按照以下步骤操作：安装并配置itchat库：itchat是一个开源的微信个人号接口，可以帮助你获取微信群聊信息。pipinstallitchat登录微信：使用itchat登录微信，获取群聊列表并监听群消息。importitchat#......
  • JAVA开发之maven安装
    一、maven下载官网地址：https://maven.apache.org/download.cgi最新版maven，最好选择3.8版本以上其他版本maven:二、安装下载完成后直接解压三、环境变量配置重复的配置，我就不详细说了......
  • ThinkPHP发邮件配置教程？群发功能安全吗？
    ThinkPHP发邮件的注意事项？如何优化邮件发送的性能？无论是用户注册、密码重置还是消息提醒，发送邮件都是一个常见的需求。AokSend将详细介绍如何在ThinkPHP框架中配置和发送邮件，帮助开发者轻松实现邮件功能。ThinkPHP发邮件：了解需求在开始配置之前，我们需要明确邮件发送的具体......
  • UiPath发送邮件给多人时需要注意哪些限制？
    UiPath发送邮件给多人的步骤？如何使用UiPath发信？尽管UiPath提供了强大的邮件发送功能，但在批量发送邮件时，有一些限制和注意事项是我们必须了解的。AokSend将详细介绍这些限制，并提供一些优化建议。UiPath发送邮件给多人：收件数量多数电子邮件服务提供商对单次邮件发送的收件人......
  • Redis(事务、持久化、高可用 、高可扩、过期删除、内存淘汰)说明、分析、区别
    Redis高级理解Redis事务机制掌握Redis持久化机制理解Redis高可用—主从复制、哨兵模式理解Redis高可扩—RedisCluster数据分片掌握Redis过期删除策略掌握Redis内存淘汰策略1事务机制1.1场景分析以关注为例，在B站上程序员关注了A，同时A也关注了程序员，那么......
  • Python数据分析常用开源库 pycharm
    内容介绍Pandas数据处理的库，可以做可视化文件类数据交互的是比较好的CSVExcel环境搭建起来SeriesDataFrame前3天主要介绍DataFrame的使用（Pandas的API）第四天数据可视化day05~day08Pandas解决数据分析问题报表，取数（SQL，Pandas，Excel）业务分析能......
  • Java学习【深入探索包装类和泛型】
    Java学习【深入探索包装类和泛型】......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99