[数据结构]C语言栈的实现

有始有终,所以我准备把各种数据结构都讲一次,栈也分顺序存储和链式储存,这里我们选择链式存储来讲,顺序存储没有难度(链式其实也是)

作为数据结构中最简单的栈,这里不会说太多,首先考虑一下下面的model:

这就是一个栈,相信你或多或少也了解一些栈的知识,当然如果不了解或者不知道你涉及过那还是继续看吧

栈数据结构是后进先出(Last  In First Out,简称LIFO),何谓后进先出?你可以把栈视作一个有下底的盒子,然后你把各种书放进去,如果你想拿书,你拿到的第一步一定是你最后放进去的,这就是栈

首先考虑他的形势,我们需要一个top指针和一个buttom指针分别指向栈顶和栈底的下一个节点,为什么是下一个?因为方便:试想一下我们要判断栈是否空就只需要判断top是否等于buttom,如果buttom指向栈底显然就会麻烦许多

下面我们先用C语言来实现一下:

首先我们需要对这个装东西的“盒子”定义,而这个盒子就是栈,然后还需要定义“书”,也就是节点:

struct node{
	char data;
	struct node *next;
};

struct stack{
	struct node *top;
	struct node *buttom;
};

如果你是一个善于思考的人你有可能会提出这样一个问题:为什么要定义struct stack而不把他里面的top和buttom放到node里面?同样的回答是因为方便理解,试想一下如果定义成下面这样:

struct node{
	char data;
	struct node *next;
	struct node *top;
	struct node *buttom;
};

这样完全行得通,但是你会发现在后面的代码抽象时会很难以理解

这里可以多引入之前的链表的例子,不过你完全可以跳过,还及得链表吗?链表里面有一个head和tail指针,但是我们再实际编写代码的时候却把它当做头结点来用,我们完全可以定义一个这样的:

struct linkedlist{
	struct node *head;
	struct node *tail;
};

struct node{
	size_t data;
	struct node *next;
};

但是我们没有,因为我们没必要吧head和tail单独抽出来,因为我们没有使用过head->next这样的code,而且我们没有把链表和节点的概念分开,我们始终认为链表是由节点组成的,而栈我们认为他是一个概念,然后节点可以放在里面(不过实际上的代码是一个概念,只是形象的用了两个结构体表示)

回到上面的话题,栈定义完了,接下来就是栈的操作,栈操作主要有入栈(push)和出栈(pop),还有遍历输出,其次就是一些诸如清栈、判断栈是否为空/满的操作,注意,由于我们这里讲的是链式栈,所以不存在栈满,如果用数组储存就会遇到

结构创建完成我们需要创建一个空栈,前面我们已经说了要想让栈为空只需要top=buttom,于是你可能很容易写出现下面代码

struct stack *create_stack(){
	struct stack *sk=new stack;
	if(sk==NULL){
		return false;
	}
	sk->top=sk->buttom;
	return sk;
}

这里先讨论入栈:

入栈

假设我们要向栈里面添加一个数据需要进行哪些操作?问题答案显而易见,我们要把top指针指向添加的节点,而且要让新节点的next指向之前top指向的节点

于是我就直接贴代码了:

void push(struct stack *sk,char p){
	node *n=new node;
	n->data=p;
	n->next=sk->top;
	sk->top=n;
}

出栈

出栈一般有两种:1.让指定数据出栈2.让top指向的数据出栈,注意,如果要让指定的数据出栈,而且如果那个数据在中间,那你就不得不把从top到那个数据的全部节点出栈,因为栈是后进先出,而且只允许一段入/出,这里我们讨论把top指向的节点出栈

这个非常简单,你可能会马上想到

sk->top=sk->top->next;

但是如果再想一下,你虽然完成了出栈,但是出了栈的那个节点怎么办?如果你不delete它它就会一直在堆中,每出栈一次就有一个无用节点占用内存,所以我们还要设法把这个无用节点删除,因此我们需要引入一个临时变量

void pop(struct stack *sk){
	node *n=sk->top;
	sk->top=n->next;
	delete n;
}

就像上面,另还要注意出栈需要考虑栈是否为空,我没有写

至此,一个C语言版本的栈及其主要操作就完成了,这也是我第一次写栈结构,因为我用C++

stack<int> sk;
sk.push(5);
//..  

这里有一篇关于STL STACK的讨论的文章有兴趣的可以去看看http://blog.csdn.net/housisong/article/details/505254

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏用户2442861的专栏

字符编码笔记:ASCII,Unicode和UTF-8

今天中午,我突然想搞清楚Unicode和UTF-8之间的关系,于是就开始在网上查资料。

891
来自专栏静默虚空的博客

[设计模式]原型模式

简介 原型模式 (Prototype)用原型实例指定创建对象的种类,并且通过拷贝这些原型创建新的对象。 原型模式是一种对象创建型模式 (可参考 设计模式 创建型...

1988
来自专栏Android机动车

数据结构学习笔记——栈

我们允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom),不含任何数据元素的栈称为空栈。

923
来自专栏赵俊的Java专栏

LeetCode 657 Robot Return to Origin

这道题很简单,只需要假设当前节点是 0, 0,定义两个变量, i 和 j,默认值都为 0,每当向上 i + 1,向下 i - 1,向右 j + 1,向左 j -...

1042
来自专栏C语言及其他语言

【每日一题】问题 1183: 人见人爱A+B

北大的acm上面已经有10来道A+B的题目了,相信这些题目曾经是大家的最爱,希望今天的这个A+B能给大家带来好运,也希望这个题目能唤起大家对ACM曾经的热爱。...

1362
来自专栏java架构师

Stream篇(2)【TextReader】

说明:一个对于Text的读取器。无论哪种文件类型,其实都是通过一个个char组成的。 这是个抽象类,无法直接实例化 重要方法: 1、void Close() 2...

3509
来自专栏nummy

python string模块学习

如果字符串模板中的变量没有提供值,会抛出异常,这时,可以使用safe_substitute().

822
来自专栏专注 Java 基础分享

计算机编码基础

     乱码是我们在日常的工作中经常遇到的问题,你可能从网上好不容易下载了一个炫酷的jQuery插件,但是却在打开的时候,发现某几个js文件都是类似“澶у0?...

1969
来自专栏Java社区

Java开发者容易犯的十个错误

1252
来自专栏linux驱动个人学习

Android系统的智能指针(轻量级指针、强指针和弱指针)的实现原理分析【转】

Android系统的运行时库层代码是用C++来编写的,用C++ 来写代码最容易出错的地方就是指针了,一旦使用不当,轻则造成内存泄漏,重则造成系统崩溃。不过系统为...

992

扫码关注云+社区

领取腾讯云代金券