数据结构栈和堆列

  • 开发
  • 32

目录

栈：

栈的概念：

栈的实现：

栈接口的实现：

1.初始化栈：

2.入栈：

3.出栈：

4. 获取栈顶元素：

5.获取栈中有效数据的个数：

 6.检测栈是否为空，如果为空返回非零结果，如果不为空返回0：

 7.销毁栈：

队列：

队列的概念：

队列的实现：

接口的实现：

1.初始化队列：

2. 队尾入队列：

3.队头出队列：

4.获取队列头部元素：

 5.获取队列尾元素：

6.获取队列中有效数据个数：

7.检测队列是否为空，如果为空返回非零结果，如果非空返回0：

8.销毁队列：

栈：

栈的概念：

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵循先进先出LIFO(Last In First Out)的原则

  • 压栈：栈的插入操作叫做进栈/入栈，入数据在栈顶。
  • 出栈：栈的删除操作叫做出栈。出数据也在栈顶。

栈的实现：

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

C语言单链表-CSDN博客  C语言实现顺序表(增,删,改,查)-CSDN博客 0基础小白学C语言看这一篇就够了(C语言详讲万字！！！)_用c++设计一个程序,实现输入任意一个数(不大于10的5次方),计算从1加到这个数-CSDN博客

栈接口的实现：

栈和顺序表一样，可以做成动态的也可以做成静态的，因为静态的一般是用在那种给定长度的地方，所以这里使用动态的实现栈。

实现之前我们需要各个文件，分别是头文件"Stack.h"，以及两个源文件"Stack.c"和"Test.c"，他们的作用如下:

  • Stack.h：栈的结构体，头文件引用，接口函数的声明。
  • Stack.c：接口函数的实现。
  • Test.c：测试各个函数的功能。

如下我们先来展示各种接口的声明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 STDestroy(ST* ps);
void STPush(ST*ps,STDataType x);
void STPop(ST* ps);
STDataType STTop(ST* ps);

int STSize(ST* ps);
bool STEmpty(ST* ps);
1.初始化栈：

把传递进来的第一个栈的置空和值为0

void STInit(ST* ps) {
	assert(ps);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}
2.入栈：

入栈之前判断栈的大小是否足够，如果足够那么直接将数据存入对应的位置然后有效值++就行，如果空间不够那么需要扩容，如果扩容失败直接报错误信息。

void STPush(ST* ps, STDataType x) {
	assert(ps);
	if (ps->top==ps->capacity) {
		int newCapacity = ps->capacity * 2 == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
		if (tmp==NULL) {
			perror("realloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newCapacity;
	}
	ps->a[ps->top] = x;
	ps -> top++;
}
3.出栈：

首先断言以下以免出现栈都没有还在出栈，然后有效数据减减就行了。

void STPop(ST* ps) {
	assert(ps);
	assert(ps->top > 0);
	--ps->top;
}
4. 获取栈顶元素：

直接返回数据没啥好说的。

STDataType STTop(ST* ps) {
	assert(ps);
	assert(ps->top > 0);
	return  ps->a[ps->top - 1];
}
5.获取栈中有效数据的个数：

直接返回栈顶元素。

int STSize(ST* ps) {
	assert(ps);
	return ps->top;
}
 6.检测栈是否为空，如果为空返回非零结果，如果不为空返回0：

返回类型是一个布尔型也就是不是false就是true。

bool STEmpty(ST* ps) {
	assert(ps);
	return ps->top == 0;
}
 7.销毁栈：

把栈释放之后然后把指针置空，值值为0.

void STDestroy(ST* ps) {
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity=0;
}

如下是全代码的示例Stack.c:

#include"Stack.h"

void STInit(ST* ps) {
	assert(ps);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}
void STDestroy(ST* ps) {
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity=0;
}

void STPush(ST* ps, STDataType x) {
	assert(ps);
	if (ps->top==ps->capacity) {
		int newCapacity = ps->capacity * 2 == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
		if (tmp==NULL) {
			perror("realloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newCapacity;
	}
	ps->a[ps->top] = x;
	ps -> top++;
}

void STPop(ST* ps) {
	assert(ps);
	assert(ps->top > 0);
	--ps->top;
}
STDataType STTop(ST* ps) {
	assert(ps);
	assert(ps->top > 0);
	return  ps->a[ps->top - 1];
}
int STSize(ST* ps) {
	assert(ps);
	return ps->top;
}
bool STEmpty(ST* ps) {
	assert(ps);
	return ps->top == 0;
}

如下我们用Test.c文件测试整个代码运行是否正常:

#include"Stack.h"

void TestStack1() {
	ST st;
	STInit(&st);
	STPush(&st, 1);
	STPush(&st, 2);
	STPush(&st, 3);
	STPush(&st, 4);
	STPush(&st, 5);

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

	STDestroy(&st);
}
int main() {
	TestStack1();
	return 0;
}

队列：

队列的概念：

队列：只允许一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)入队列：进入插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头。

队列的实现：

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

接口的实现：

我们首先创建一个头文件"Queue.h"和两个源文件分别是"Queue.c"跟"Test.c"，他们的作用为:

  • Queue.h:头文件的引用接口函数的声明，以及栈的结构体。
  • Queue.c:接口的实现。
  • Test.c：测试每个接口。

如下代码是Queue.h中所有接口以及头文件引用的代码：

#pragma once

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

typedef int QDataType;
typedef struct QueueNode {
	struct QueueNode* next;
	QDataType data;
}QNode;

typedef struct Queue {
	QNode* head;
	QNode* tail;
	int size;
}Que;


void QueueInit(Que* pq);
void QueueDestroy(Que* pq);
void QueuePush(Que*pq,QDataType x);
void QueuePop(Que* pq);
QDataType QueueFront(Que* pq);
QDataType QueueBack(Que* pq);
bool QueueEmpty(Que* pq);
int QueueSize(Que* p);
1.初始化队列：

把拿到的头指针和尾指针置空，然后把其值置为0...

void QueueInit(Que* pq) {
	assert(pq);
	pq->head = pq->tail = NULL;
	pq->size = 0;
}
2. 队尾入队列：

先使用malloc创建出一个队列，然后判断创建是否成功，如若成功执行下列代码，首先把指针置空然后给数据赋值，最后判断一下是第几个元素如果是第一个那么直接让头指针和尾指针都指向它即可，如果不是那么需要改变尾指针的指向，然后有效数据加加。

void QueuePush(Que* pq, QDataType x) {
	assert(pq);
	QNode* newnode = malloc(sizeof(QNode));
	if (newnode == NULL) {
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->tail==NULL) {
		pq->head = pq->tail = newnode;
	}
	else {
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	pq->size++;
}
3.队头出队列：

出数据大致原理就是保存第一个然后让头指针指向下一个然后再把之前那个释放了，最后有效数据个数减减即可。

void QueuePop(Que* pq) {

	assert(pq);
	assert(!QueueEmpty(pq));

	if (pq->head->next == NULL) {
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else {
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
	pq->size--;
}
4.获取队列头部元素：

队头有一个指针head直接拿取即可。

QDataType QueueFront(Que* pq) {
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->head->data;
}
 5.获取队列尾元素：

队尾有一个指针也就是tail直接拿取即可。

QDataType QueueBack(Que* pq) {
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->tail->data;
}
6.获取队列中有效数据个数：

直接拿取有效数据size即可。

int QueueSize(Que* pq) {
	assert(pq);
	return pq->size;
}
7.检测队列是否为空，如果为空返回非零结果，如果非空返回0：

首先断言，返回时是一个表达式用来判断是否是真还是假。

bool QueueEmpty(Que* pq) {
	assert(pq);
	return pq->head == NULL;
}
8.销毁队列：

使用循环从队列的头部一直释放即可，最后把传进来的pq指针置空。

void QueueDestroy(Que* pq) {
	assert(pq);
	QNode* cur = pq->head;
	while (cur) {
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
	pq->size = 0;
}

下列是队列接口实现的全部代码Queue.c中的：

#include"Queue.h"

void QueueInit(Que* pq) {
	assert(pq);
	pq->head = pq->tail = NULL;
	pq->size = 0;
}



void QueueDestroy(Que* pq) {
	assert(pq);
	QNode* cur = pq->head;
	while (cur) {
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
	pq->size = 0;
}

void QueuePush(Que* pq, QDataType x) {
	assert(pq);
	QNode* newnode = malloc(sizeof(QNode));
	if (newnode == NULL) {
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->tail==NULL) {
		pq->head = pq->tail = newnode;
	}
	else {
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	pq->size++;
}

void QueuePop(Que* pq) {

	assert(pq);
	assert(!QueueEmpty(pq));

	if (pq->head->next == NULL) {
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else {
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
	pq->size--;
}
QDataType QueueFront(Que* pq) {
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->head->data;
}


QDataType QueueBack(Que* pq) {
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->tail->data;
}

bool QueueEmpty(Que* pq) {
	assert(pq);
	return pq->head == NULL;
}
int QueueSize(Que* pq) {
	assert(pq);
	return pq->size;
}

然后test.c测试代码是否能够正常运行:

#include"Queue.h"

void TestQueue() {
	Que q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);

	while (!QueueEmpty(&q)) {
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	printf("\n");

	QueueDestroy(&q);
}

int main() {
	TestQueue();
}

阅读全部

相关推荐

  2. 【数据结构】堆和栈的区别

    2024-04-03 02:34:03       44 阅读

  3. 堆、栈和队列（数据结构）

    2024-04-03 02:34:03       28 阅读

  4. 堆、栈和队列（数据结构）

    2024-04-03 02:34:03       32 阅读

  7. 数据结构9：栈和队列的相互实现

    2024-04-03 02:34:03       28 阅读

  9. 数据结构----堆 和 堆排序 代码

    2024-04-03 02:34:03       38 阅读

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-04-03 02:34:03       98 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2024-04-03 02:34:03       106 阅读

  9. 在Django里面运行非项目文件

    2024-04-03 02:34:03       87 阅读

  19. Python语言-面向对象

    2024-04-03 02:34:03       96 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2024-04-03 02:34:03       91 阅读

热门阅读

  2. 【nosql-redis】关于持久化的补充

    2024-04-03 02:34:03       34 阅读

  4. 关于投标的细节

    2024-04-03 02:34:03       38 阅读

  8. Nginx 配置，自定义日志格式 log_format

    2024-04-03 02:34:03       44 阅读

  10. 2024.2.21力扣每日一题——从中序和后序遍历序列构建二叉树

    2024-04-03 02:34:03       46 阅读

  12. 简述前端开发全景：从基础到未来的语言与趋势解析

    2024-04-03 02:34:03       39 阅读

  20. k8s 常用指令

    2024-04-03 02:34:03       39 阅读

  22. Centos7安装Docker-Compose

    2024-04-03 02:34:03       38 阅读

  23. bash简化if-else

    2024-04-03 02:34:03       38 阅读

  27. P10086 [ROIR 2022 Day 1] 口算比赛

    2024-04-03 02:34:03       30 阅读

  28. radash 工具整理常用 API

    2024-04-03 02:34:03       30 阅读