数据结构之栈的实现(附源码)

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

目录

一、栈的概念及结构

​二、栈的实现

三、初学栈的练习题


一、栈的概念及结构

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

压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶

出栈:栈的删除操作叫做出栈。出数据也在栈顶。

二、栈的实现

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

数据结构之栈的实现(附源码),数据结构
 

具体实现代码如下:

#pragma once

//Stack.h
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
// 支持动态增长的栈
//使用数组实现
typedef int STDataType;
typedef struct Stack
{
	STDataType* _a;
	int _top;		// 栈顶
	int _capacity;  // 容量 
}Stack;
// 初始化栈 
void StackInit(Stack* ps);
// 入栈 
void StackPush(Stack* ps, STDataType data);
// 出栈 
void StackPop(Stack* ps);
// 获取栈顶元素 
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数 
int StackSize(Stack* ps);
// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0 
int StackEmpty(Stack* ps);
// 销毁栈 
void StackDestroy(Stack* ps);
//Stack.c
#include "Stack.h"

void StackInit(Stack* ps)
{
	assert(ps);
	ps->_a = NULL;
	ps->_top = 0;
	ps->_capacity = 0;
}

void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	//容量满了
	if (ps->_capacity == ps->_top)
	{
		//如果数组的容量为0,就赋值为4,;如果数组的容量不为0且容量满了,就扩大为原来容量的二倍。
		int newCapacity = ps->_capacity == 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] = data;
	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->_a[ps->_top - 1];
}

int StackSize(Stack* ps)
{
	assert(ps);
	return ps->_top;
}

int StackEmpty(Stack* ps)
{
	return ps->_top;
}

void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->_a);
	ps->_a = NULL;
	ps->_capacity = 0;
	ps->_top = 0;
}
test.c
#include "Stack.h"

void test01()
{
	Stack st;
	StackInit(&st);

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

	while (StackEmpty(&st))
	{
		printf("%d ", StackTop(&st));
		StackPop(&st);
	}
	printf("\n");

	StackDestroy(&st);
}

int main()
{
	test01();

	return 0;
}

三、初学栈的练习题

题1:

给定一个只包括 '('')''{''}''['']' 的字符串 s ,判断字符串是否有效。

有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

 思路:当输入的字符串中出现左括号时就进栈,出现右括号时就与栈顶的左括号看是否相匹配。若相匹配就栈顶的左括号出栈,不匹配就直接返回false。若所有左右括号都匹配才返回true。

具体实现代码如下(C语言实现):文章来源地址https://www.toymoban.com/news/detail-731422.html

//C语言实现需要自己将栈的各个功能实现
typedef char STDataType;

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

void StackInit(Stack* ps)
{
	assert(ps);
	ps->_a = NULL;
	ps->_top = 0;
	ps->_capacity = 0;
}

void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	if (ps->_capacity == ps->_top)
	{
		int newCapacity = ps->_capacity == 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] = data;
	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->_a[ps->_top - 1];
}

int StackSize(Stack* ps)
{
	assert(ps);
	return ps->_top;
}

int StackEmpty(Stack* ps)
{
	return ps->_top;
}

void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->_a);
	ps->_a = NULL;
	ps->_capacity = 0;
	ps->_top = 0;
}


bool isValid(char * s)
{
    Stack st;
    StackInit(&st);
    char topVal;
    while(*s)
    {
        //左括号入栈
        if(*s == '(' || *s == '[' || *s == '{')
        {
            StackPush(&st, *s);
        }
        //右括号与栈顶左括号进行匹配
        else
        {
            //栈里已经没有左括号了,再输入一个右括号,不匹配。
            if(StackEmpty(&st) == 0)
            {
                StackDestroy(&st);
                return false;
            }
            topVal = StackTop(&st);
            //不匹配返回false。
            if((topVal == '(' && *s != ')') || (topVal == '[' && *s != ']')
            || (topVal == '{' && *s != '}'))
            {
                StackDestroy(&st);
                return false;
            }
            //匹配成功栈顶出栈。
            StackPop(&st);
        }
        s++;
    }
    //最后栈里还剩有左括号返回false,不剩返回true。
    int ret = StackEmpty(&st);
    if(ret == 0)
    return true;
    else
    return false;
}

 

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

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

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

相关文章

  • 数据结构 栈的概念及栈的实现

    目录 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日
    浏览(65)
  • 【数据结构】:栈的实现

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

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

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

    2024年02月05日
    浏览(47)
  • 【数据结构】栈的实现

    栈:是一种受限制的线性表,即只能在尾部进行插入、删除的线性表,而且是一种先进后出的数据结构。尾部这一端又叫做栈顶,另一端叫做栈底。 入栈:向一个栈内插入元素叫做入栈或压栈,它把新元素放到栈顶元素的上面,是它成为新的栈顶元素。 出栈:在栈内删除元

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

    个人主页 : 个人主页 个人专栏 : 《数据结构》 《C语言》 栈:一种特殊的线性结构,其只允许在一端进行插入,删除数据。允许操作数据的一端被称为 栈顶 ,另一端被称为 栈底 。 本篇博客将要实现的是 数组栈 。 对于栈的特殊性,用数组(在数组尾部插入删除数据) 和

    2024年02月13日
    浏览(63)
  • 【数据结构—栈的实现(数组栈)】

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言 一、栈 1.1栈的概念及结构 二、栈的实现 2.1头文件的实现—Stack.h 2.2源文件的实现—Stack.c 2.3源文件的测试—test.c 三、栈的实际测试数据展示 3.1正常的出入栈展示: 3.2进栈同时也在出栈的

    2024年02月04日
    浏览(47)
  • 数据结构:线性表(栈的实现)

    栈(Stack)是只允许在一端进行插入或删除操作的线性表.首先栈是一种线性表,但限定这种线性表只能在某一端进行插入和删除操作. 进行 数据插入和删除操作的一端 叫 栈顶 ,另一端称为 栈底 . 栈中的元素遵循 后进先出 LIFO(Last In First Out)的原则 压栈 :栈的插入操作叫做进栈/压栈

    2024年02月09日
    浏览(39)
  • 【数据结构】栈的实现(C语言)

    文章目录 1.栈 1.1 栈的定义 1.2 C语言实现栈 1.2.1接口函数 1.2.2栈的创建 1.2.3栈的初始化  1.2.4栈的销毁 1.2.5压栈 1.2.6出栈 1.2.7判断栈是否为空 1.2.8取栈顶元素 1.2.9 栈有多少个数据  1.3 C语言实现栈的具体代码 头文件stack.h 接口函数stack.c 测试函数test.c         栈(stack)又名堆

    2024年02月05日
    浏览(47)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包