数据结构:栈的实现(C实现)

这篇具有很好参考价值的文章主要介绍了数据结构:栈的实现(C实现)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

数据结构:栈的实现(C实现),数据结构,数据结构,c语言,算法

个人主页 : 个人主页
个人专栏 : 《数据结构》 《C语言》


前言

栈:一种特殊的线性结构,其只允许在一端进行插入,删除数据。允许操作数据的一端被称为栈顶,另一端被称为栈底
本篇博客将要实现的是数组栈


一、栈的实现思路

对于栈的特殊性,用数组(在数组尾部插入删除数据) 和 链表(头插头删数据)实现栈的时间复杂度都是O(1),难度不大。
数组栈的优劣

  • 数组支持随机访问(用下标访问数据),许多算法需要随机访问的支持,如二分法…
  • 缓存利用率高

  • 空间不够时要扩容
  • 有时会造成空间浪费

1. 结构的定义

栈的结构非常简单
一个指向动态开辟空间的指针,一个记录实际空间大小的变量,一个记录栈顶元素的下标即可。

数据结构:栈的实现(C实现),数据结构,数据结构,c语言,算法

typedef int STDataType;

typedef struct Stack
{
	STDataType* data;
	int top;//栈顶下标
	int capacity;//空间大小
}Stack;

2. 初始化栈(StackInit)

data指针指向动态开辟的空间,capacity记录此时空间大小,top置为0。

  • top 置0,表示栈顶数据将要插入的位置。
  • top 置-1,表示此时栈顶数据的位置。

这里,采用top 置0。

数据结构:栈的实现(C实现),数据结构,数据结构,c语言,算法

//初始化栈

#define SIZE 4

void StackInit(Stack* ps)
{
	assert(ps);

	ps->data = (STDataType*)malloc(sizeof(STDataType) * SIZE);
	if (ps->data == NULL)
	{
		perror("malloc");
		exit(-1);
	}

	ps->top = 0;
	ps->capacity = SIZE;
}

3. 入栈(StackPush)

因为top初始化为0,所以直接在top下标处入数据即可。但要注意,在入数据前要检查容量,如果top == capacity 要扩容。

  • 此处检查容量的操作,可以封装成一个函数,但没必要,因为栈的操作只有入栈要检查容量,其它的操作并不需要检查容量,封装成一个函数反而效率减低了(函数的调用要形成函数栈帧)。

数据结构:栈的实现(C实现),数据结构,数据结构,c语言,算法

//入栈
void StackPush(Stack* ps, STDataType x)
{
	assert(ps);

	if (ps->top == ps->capacity)
	{
		STDataType* tmp = (STDataType*)realloc(ps->data, sizeof(STDataType) * (ps->capacity * 2));
		if (tmp == NULL)
		{
			perror("realloc");
			exit(-1);
		}

		ps->data = tmp;
		ps->capacity *= 2;
	}

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

4. 出栈(StackPop)

top 表示的是栈顶数据将要入栈的位置,那么出栈操作,只需要让top 减 1即可。(下次入栈数据会直接覆盖)
但要注意,top = 0 时,表示栈内没有数据,不能进行出栈操作。

  • 出栈操作不能获取数据

数据结构:栈的实现(C实现),数据结构,数据结构,c语言,算法

//出栈
void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->top != 0);

	ps->top--;
}

5. 获取栈顶元素(StackTop)

top 指向的是数据将要入栈的位置,也就是栈顶数据的下一个位置。
那么要获取栈顶数据,只需要读取top - 1处即可。但要注意,如果top = 0,那么top - 1 = -1,会越界访问,所以top = 0 时,不能获取栈顶元素。

数据结构:栈的实现(C实现),数据结构,数据结构,c语言,算法


//获取栈顶元素
STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->top > 0);
	
	return ps->data[ps->top - 1];
}

6. 检查栈是否为空(StackEmpty)

top 指向的是数据将要入栈的位置,其数值也表示栈内数据个数。
所以我们只需要进行 top == 0 的判断,即可知道栈是否为空。

//检查栈是否为空
bool StackEmpty(Stack* ps)
{
	assert(ps);

	return ps->top == 0;
}

7. 销毁栈(StackDestroy)

free掉动态开辟的空间,使capacity 置 0,top 置 0。

//销毁栈
void StackDestroy(Stack* ps)
{
	assert(ps);

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

二、代码实现

Stack.h 文件存放的是函数的声明,头文件的引用,结构体的定义
Stack.c 文件存放的是函数的实现

//Stack.h  文件

#pragma once

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

#define SIZE 4

typedef int STDataType;

typedef struct Stack
{
	STDataType* data;
	int top;
	int capacity;
}Stack;


//初始化栈
void StackInit(Stack* ps);

//入栈
void StackPush(Stack* ps, STDataType x);

//出栈
void StackPop(Stack* ps);

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

//检查栈是否为空
bool StackEmpty(Stack* ps);

//销毁栈
void StackDestroy(Stack* ps);


//Stack.c  文件


#include "Stack.h"

//初始化栈
void StackInit(Stack* ps)
{
	assert(ps);

	ps->data = (STDataType*)malloc(sizeof(STDataType) * SIZE);
	if (ps->data == NULL)
	{
		perror("malloc");
		exit(-1);
	}

	ps->top = 0;
	ps->capacity = SIZE;
}


//入栈
void StackPush(Stack* ps, STDataType x)
{
	assert(ps);

	if (ps->top == ps->capacity)
	{
		STDataType* tmp = (STDataType*)realloc(ps->data, sizeof(STDataType) * (ps->capacity * 2));
		if (tmp == NULL)
		{
			perror("realloc");
			exit(-1);
		}

		ps->data = tmp;
		ps->capacity *= 2;
	}

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



//出栈
void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->top != 0);

	ps->top--;
}



//获取栈顶元素
STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->top > 0);
	
	return ps->data[ps->top - 1];
}


//检查栈是否为空
bool StackEmpty(Stack* ps)
{
	assert(ps);

	return ps->top == 0;
}



//销毁栈
void StackDestroy(Stack* ps)
{
	assert(ps);

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

总结

以上就是我对于栈的实现。
数据结构:栈的实现(C实现),数据结构,数据结构,c语言,算法文章来源地址https://www.toymoban.com/news/detail-642710.html

到了这里,关于数据结构:栈的实现(C实现)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构与算法】栈的讲解

    栈(stack)是限定仅在表尾进行插入和删除操作的线性表。 我们把 允许插入和删除的一段称为栈顶(top) , 另一端称为栈底 , 不含任何数据元素的栈称为空栈 。 栈又称为后进先出的线性表 。 进一步理解栈,栈首先他是一个 线性表 ,所以栈元素具有前驱后继关系。 栈的插入操

    2023年04月08日
    浏览(39)
  • 【数据结构】链栈的基本操作(C语言)

    零零总总搜索了一些关于链栈的资料,了解了链栈的基本操作,一直觉得别人写的代码或多或少存在一些问题,所以打算自己写一篇关于链栈的文章,也算是对所学知识的梳理和巩固了。 首先说明本文使用C语言进行链栈的基本操作,链栈是无头结点的。这里补充说明一下,

    2024年02月05日
    浏览(59)
  • 【数据结构】 链栈的基本操作 (C语言版)

    目录 一、链栈 1、链栈的定义: 2、链栈的优缺点: 二、链栈的基本操作算法(C语言)     1、宏定义   2、创建结构体 3、链栈的初始化   4、链栈的进栈 5、链栈的出栈 6、获取栈顶元素 7、栈的遍历输出 8、链栈的判空  9、求链栈的栈长 10、链栈的清空 11、链栈的销毁

    2024年01月24日
    浏览(49)
  • 【数据结构】 顺序栈的基本操作 (C语言版)

    目录 一、顺序栈 1、顺序栈的定义: 2、顺序栈的优缺点 二、顺序栈的基本操作算法(C语言)    1、宏定义  2、创建结构体 3、顺序栈的初始化  4、顺序栈的入栈 5、顺序栈的出栈 6、取栈顶元素 7、栈的遍历输出 8、顺序栈的判空 9、顺序栈的判满  10、求顺序栈长度 11、顺

    2024年01月24日
    浏览(53)
  • 数据结构学习——C语言对栈的基本操作

             栈(Stack)是一种常用的数据结构,遵循先进后出(LIFO)的原则,对表尾进行操作,常用于临时存储和撤销等操作,其基本操作包括栈的创建、入栈(也叫压栈Push)、出栈(又称弹栈)、栈的遍历、栈的清空(clear)、栈的销毁(destroy)等。         栈的创建有两种方式,一种是通

    2024年02月07日
    浏览(58)
  • 【数据结构 迷宫问题求解】栈的应用|c语言|迷宫问题

    亲测可行: 使用蓝桥杯比赛编译器:DEV C++  求迷宫中从入口到出口的路径是一个经典的程序设计问题,通常采用“穷举求解”的方法,即顺着某一方向向前探索,若能走通,则继续往前走;否则原路返回,换一个方向继续探索,直至所有可能的通路都探索到为止。 因此,在

    2024年02月08日
    浏览(49)
  • 数据结构 栈的概念及栈的实现

    目录 1.栈的概念及结构 2.栈的实现  2.1  初始化栈 2.2 入栈  2.3 出栈  2.4 获取栈顶元素 2.5 获取栈中有效元素个数   2.6  检测栈是否为空,如果为空返回非零结果,如果不为空返回0 2.7 销毁栈  3. 完整代码 test.c  Stack.h Stack.c   栈(后进先出,先进后出) : 一种 特殊

    2024年01月21日
    浏览(49)
  • 数据结构:栈的概念及栈的实现

    目录 1.栈的概念及结构 2.栈的实现  2.1  初始化栈 2.2 入栈  2.3 出栈  2.4 获取栈顶元素 2.5 获取栈中有效元素个数   2.6  检测栈是否为空,如果为空返回非零结果,如果不为空返回0 2.7 销毁栈  3. 完整代码 test.c  Stack.h Stack.c   栈(后进先出,先进后出) : 一种 特殊

    2024年02月01日
    浏览(41)
  • 数据结构---栈的实现

    前言 一、什么是栈? 二、 栈的实现 1. 栈的结构 2. 栈的接口实现过程 总结 栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是

    2024年02月02日
    浏览(66)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包