数据结构线性存储 -- 栈讲解

灰太狼 2022-03-16 08:04 406阅读 0赞

## 1.栈的定义 ##

我们有时会听到这句话,  静态定义的内存是在栈中分配的, 动态内存是在堆里面分配的.

例如下面这个简单的函数:

int f(int k){ 
            int m = 2 * k;
            int * p = (int *)malloc(16);
            return m;  
    }

那么我们认为 作为参数的 k,   函数内静态定义的整形变量 m,   指针p,  它们本身都占用一定的内存.

其中m 和 k占用4字节,  p占用8字节(64位系统)

这些静态变量本身所占用的内存就是静态定义的内存,  它们都在栈里面分配的

而(int \*)malloc(16) 动态分配了16个字节的内存, 是在堆里面分配的.

那么到底什么是栈?

##           定义: ##

一种可以实现"先进后出"的存储结构.

那么什么是先进后出呢?   就比如1个箱子,  先放进去的东西在箱底,  然后被后面放进去的东西盖住了, 如果要取出箱底的东西, 则必然要实现把后面放进去的东西先取出来.

也就是说栈

1.只有1个 出入口(栈顶)

2. 另一端是封闭的(栈底)

3. 不允许在元素之间的插入移除操作

如下图:

![E6_A0_88.JPG][]

## 2.栈的分类 ##

C语言中, 栈可以分成两类,  静态栈 和 动态栈

###             2.1 静态栈 ###

以数组为内核的栈, 就是静态栈, 静态栈里面各个元素的物理内存地址是连续的

###             2.2 动态栈 ###

相应地, 以链表为内核的栈就是动态栈,  栈里面的元素是用尾部指针来联系的,

本文主要讲解的是动态栈.

## 3. 栈的基本操作 ##

栈只有两个基本操作, 就是压栈(入栈) 和 出栈

###            3.1 压栈    ###

所谓入栈就是吧1个元素放到栈的头部, 然后这个新元素就是栈顶了.

###            3.2 出栈 ###

从栈顶把栈顶元素移除出栈,  然后栈顶就是原来栈顶的下1个元素.

可以理解出,  对于栈来将, 增加和删除元素都只能在栈顶进行,   没有在栈的中间的任何元素操作.

**所以动态栈本质上就是1个阉割了部分功能的链表. **

BOOL st\_free(STPERSON \* pSt)\{  
    st\_clear(pSt);  
  
    free(pSt->phead);  
    free(pSt->pbuttom);  
  
    free(pSt);  
    pSt=NULL;  
    return TRUE;  
\}

## 4. 动态栈的基本结构 ##

上面提到了, 动态栈是以链表为核心的,   链表的一端是栈底, 另一边就是出入栈顶了.

那么对于单链表来将,  链表是存在1个方向的,  反方向是不能由1个元素找到它的上1个元素.

究竟单链表的首节点是栈顶, 还是尾节点是栈顶?

###           4.1 假如栈顶是单链表的尾节点 ###

这种情况下, 单链表的首节点就是栈底了~  如果进行入栈动作是挺方便的, 只需将栈顶的尾部指针指向新的元素. 然后新的元素指针set成NULL. 如下图:

问题1, 怎么找到原来的栈顶(下图元素4地址呢),   当然可以由链表的首节点一直遍历, 知道某个元素的尾部指针是NULL就是栈顶, 不过遍历是1个成本很高的动作, 所以实际上我们会定义1个栈顶指针, 专门存放栈顶的地址, 当进行入栈动作, 我们会这个栈顶指针指向新的栈顶地址.

![444127020130414000823044.png][]

但是我们进行出栈时, 就需要把栈顶元素移除. 实际上是把, 栈顶上面的元素的尾部指针set成NULL, 然后把栈顶指针指向这个元素(新栈顶), 就ok了.

**问题来了, 因为单链表只能1个方向遍历, 所以我们无法根据旧栈顶地址直接获得新栈顶(上1个元素)的地址, 只能从链表的首元素(栈底)逐个遍历,  这就是用尾节点作为栈顶的弊端.**

![444127020130414001000063.png][]

###          4.2 假如栈顶是单链表的尾节点 ###

这种情况下, 首节点是栈顶, 所以尾指点就是栈底了.

当执行入栈动作时,  只需要吧新的元素的尾部指针指向旧栈顶元素, 然后栈顶指针指向这个新的元素就ok了, 一样很方便.

**但是这样的话链表的首节点就改变了, 也就是说整个链表的地址改变了**

如下图  
![444127020130414001116025.png][]

而当执行出栈动作时,  需要获得, 栈顶下1个元素的地址, 而这个地址就恰好存放在栈顶元素的尾部指针中,  所以不需要遍历就可以直接由栈顶地址获得下面1个元素的地址了. 然后吧栈顶指针指向这个新栈顶地址就ok了.

如下图:

![444127020130414001222034.png][]

可以看出这中模式下,  无论出栈和入栈动作都可以方便地获取所需元素的地址, 不需要遍历. 所以我们1般会用1个链表的首节点作为栈顶.

###          4.3 添加不存放有效数据的头节点和尾节点. 并把尾节点作为栈底. ###

由上面的分析得出, 出栈和入栈的大部分情况下, 栈底元素基本不变的,  而每执行1次出栈或入栈动作, 栈顶元素地址改变了, 整个链表的地址就改变了.

为了方便操作, 在实际编码中,  我们会在链表里添加1个头节点(并不是首节点), 然后头节点的地址作为整个链表的地址, 头节点的指针指向首节点的地址,    而栈顶指针仍然是指向首节点, 这样的话, 改变首节点(出栈或入栈)的同时修改头节点的指针, 这样整个链表的地址就无需改变了.

同样为了方便操作, 我们也会定义1个不存放实际数据的尾节点, 作为栈底, 实际意义上的栈底元素尾部指针指向这个栈底元素,  那么执行1个栈是空的, 那么它仍然具有1个不存放实际数据的栈底

如下图:

![444127020130414000613012.png][]

## 5. 一个动态栈的简单c语言代码实现 ##

当然了, 这个栈的内核是1个链表, 而且只会实现最基本的功能.

### 5.1 首先编写1个头文件 ###

在这个头文件里, 我们要定义2个结构体,

1个结构体对应栈的节点. 它应该包括若干数据成员和1个尾部指针成员pnext, 用于指向下1个节点.

而另1个结构体对应栈本身, 它包括4个成员, 分别是:

phead     他是1个不存放有效数据的头节点.  phead的地址就是栈的链表内核的地址.  phead->pnext 就是栈顶

pbuttom   他是1个不存放有效数据的栈底节点, 但phead->pnext 指向pbuttom时, 则这个是i个空栈.

len            它用于存放链表的节点个数, 方便程序员得到这个信息.

is\_inited   用于判断这个栈是否已经初始化,  否则新定义1个栈, 里面成员肯定是野指针

另外, 这个头文件还应该声明要定义的算法函数,  这样别的文件引用这个头文件, 就可以使用对应的函数了.

代码如下:

**stuck1.h**

#include "bool_me.h"
    #ifndef __STUCK1_H_
    #define __STUCK1_H_
    	struct person_st{ //node
    		int id;
    		char name[16];
    		struct person_st * pnext;
    	};
    
    	typedef struct person_st PERSON_ST;
    
    	struct stuck_person{ //struct
    		PERSON_ST * phead; //address of the headnode of the linklist
    		PERSON_ST * pbuttom; // buttom of the stuck
    		int len;
    		BOOL is_inited;
    	};
    
    	typedef struct stuck_person STPERSON;
    
    	//init a new node with dynamic memory
    	PERSON_ST * person_st_new(int id, char * pname);
    
    	//printf the infomation of a node
    	void person_st_printf(PERSON_ST * pnode);
    
    	//create a stuck with dynamic linklist
    	STPERSON * st_create(void);
    
    	//judge whether the stuck is empty (phead->pnext == pbutton)
    	BOOL st_is_empty(STPERSON * pSt);
    
    	//push a new element into the stuck
    	BOOL st_push(STPERSON * pSt, PERSON_ST * pnode);
    
    	//pop a top element out from the stuck
    	BOOL st_pop(STPERSON * pSt, PERSON_ST ** pOutput);
    
    	//traverse the stuck to print all the elements
    	void st_print(STPERSON * pSt);
    
    	//put out and free all the elements from the elements;
    	BOOL st_clear(STPERSON *pSt);
    
    	//traverse the stuck to free all the elements, and free the stuck itself
    	BOOL st_free(STPERSON * pSt);
    
    #endif

上面定义了1个节点类型结构体 PERSON\_ST

和1个栈结构体 STPERSON

可以见到我定义了若干个算法函数, 下面会逐个讲解这些函数.

### 5.2 错误处理函数st\_error(char \* pstr) ###

这个函数专门用于输出出错信息, 并退出整个函数, 而且我不会让外面的文件直接调用这个函数, 所以加上static 前序

**stuck1.c   //下面的函数定义都写在这个文件中, 这个文件也要引用上面的头文件**

static void st_error(const char * pErr){
    	printf("%s\n",pErr);
    	exit(-1);
    }

### 5.3 动态新建1个节点函数 PERSON\_ST \* person\_st\_new(int id, char \* pname)    ###

这个函数功能是动态创建1个节点,  所以动态定义就是指分配给它的内存是动态分配的, 这样这个节点可以方便地让其他函数使用, 必要时也可以手动释放.

而且我们会接受两个参数. 新建这个节点时,会同时给它的两个成员赋值. 相当于初始化了.

代码如下:

PERSON_ST * person_st_new(int id, char * pname){
    	PERSON_ST * pnode = (PERSON_ST *)malloc(sizeof(PERSON_ST));
    	if (NULL == pnode){
    		st_error("fail to assign memory to new node");
    	}
    	pnode->id=id;
    	strncpy(pnode->name, pname+0,15);
    	return pnode;
    }

注意, 如上面代码, 我还会判断参数字符串 pname 的长度, 如果超过了结构体的成员定义, 则截取对应长度后再赋值

### 5.4 打印1个节点的函数 person\_st\_print(PERSON\_ST \* pnode) ###

这个函数太简单, 不解析了

代码如下:

void person_st_print(PERSON_ST * pnode){
    	printf("id is %d, name is %s\n",pnode->id, pnode->name);
    }

### 5.5 创建并初始化1个 栈   STPERSON \* st\_create(void) ###

相当于面向对象语言里的new函数啦.  这里会动态分配内存给他的每个指针成员

步骤:

1. 动态分配内存给1个  栈 指针pSt

2. 分别动态分配内存给栈成员 phead 和 pbuttom

3. 将phead的尾部指针指向puttom 这样的话这个就是1个空栈

4. puttom的尾部指针指向NULL

5. 栈成员len 设为0

6. 栈成员is\_init 设为TRUE

7. 返回这个栈指针

代码如下:

STPERSON * st_create(void){
    	STPERSON * pSt = (STPERSON *)malloc(sizeof(STPERSON));
    	pSt->phead = (PERSON_ST *)malloc(sizeof(PERSON_ST));
    	if (NULL == pSt->phead){
    		st_error("fail to assign memory to headnode");
    	}
    
    	pSt->pbuttom = (PERSON_ST *)malloc(sizeof(PERSON_ST));
    	if (NULL == pSt->pbuttom){
    		st_error("fail to assign memory to buttom");
    	}
    
    	pSt->pbuttom = (PERSON_ST *)malloc(sizeof(PERSON_ST));
    
    	pSt->phead->id=0;
    	pSt->pbuttom->id=-1;
    	pSt->phead->pnext = pSt->pbuttom;
    	pSt->pbuttom->pnext=NULL;
    	pSt->len=0;
    	pSt->is_inited = TRUE;
    	return pSt;
    }

### 5.6 判断某个栈是否空栈 BOOL st\_is\_empty(STPERSON \* pSt)    ###

这个函数也很简单, 只需要判断phead 的尾部指针是否指向 pbuttom(栈底)就可以了, 上面说过了, 这两个节点都不存放有效数据的.  也就是说这个两个节点之间没有任何存放有效数据的节点.

代码如下:

BOOL st_is_empty(STPERSON * pSt){
    	if (TRUE != pSt->is_inited){
    		st_error("the stuck is not initialed yet");
    	}
    
    	if (pSt->phead->pnext == pSt->pbuttom){
    		return TRUE;
    	}
    
    	return FALSE;
    }

### 5.7 入栈函数 BOOL st\_push(STPERSON \* pSt, PERSON\_ST \* pnode) ###

这个函数的作用就是将参数中的 pnode节点压入 栈pSt中,  至于这个pnode节点如何得来? 可以用上面的person\_st\_new新建1个(必须, 否则不能手动释放).

步骤:

1. 这个要压栈的节点尾部指针指向 phead->pnext(旧 栈顶),

2. phead->pnex 指向这个要压栈的节点( 新栈顶)

3. 栈的成员len+1

代码如下:

//push a new element into the stuck
    BOOL st_push(STPERSON * pSt, PERSON_ST * pnode){
    	if (TRUE != pSt->is_inited){
    		printf("the stuck is not initialed yet\n");
    		return FALSE;
    	}
    
    	pnode->pnext = pSt->phead->pnext;
    	pSt->phead->pnext = pnode;
    	pSt->len++;
    	return TRUE;
    }

### 5.8 栈打印所有元素函数 void st\_print(STPERSON \* pSt) ###

这里的元素指的是存放有效数据的节点.  头节点和栈底节点不打印输出

逻辑也很简单, 首先判断是否空栈,  然后从栈顶元素(头节点的下1个元素)开始逐个输出,  知道遇到pbuttom

代码如下:

//traverse the stuck to print all the elements
    void st_print(STPERSON * pSt){
    	if (TRUE != pSt->is_inited){
    		printf("the stuck is not initialed yet, fail to print it\n");
    		return;
    	}
    
    	if (TRUE == st_is_empty(pSt)){
    		printf("the stuck is empty!\n");
    		return;
    	}
    
    	PERSON_ST * pnode = pSt->phead;
    	while (pSt->pbuttom != pnode->pnext){
    		pnode = pnode->pnext;
    		person_st_print(pnode);
    	}
    }

### 5.9 出栈函数 BOOL st\_pop (STPERSON \* pSt, PERSON\_ST \*\* pOutput) ###

这个就是出栈函数, 他会把栈顶元素移除出这个栈.  而且把这个栈顶元素的地址传出到 pOutput.

这个pOutput 就是在外面定义的1个 节点类型指针, 然后把这个指针本身的地址传入来作为参数.  然后函数里会改变这个pOutput指针的值, 让他指向栈顶元素, 只有动态分配的内存才能这样操作啊.

原理可以参阅我的另一篇文章:

[c语言 跨函数使用内存][c_]

步骤如下:

1. 判断是否空栈, 否则返回false

2. 让\*pOutput 指向 栈顶

3. phead 指向栈顶的下1个元素(新栈顶)

4. 栈成员len-1;

5 返回true;

代码如下:

BOOL st_pop(STPERSON * pSt, PERSON_ST ** pOutput){
    	if (TRUE != pSt->is_inited){
    		printf("the stuck is not initialed yet\n");
    		return FALSE;
    	}
    
    	if (TRUE == st_is_empty(pSt)){
    		printf("the stuck is empty!\n");
    		return FALSE;
    	}
    
    	*pOutput = pSt->phead->pnext; //ptop
    	pSt->phead->pnext = (*pOutput)->pnext;
    
    	pSt->len--;
    	return TRUE;
    }

### 5.10 清空栈函数 BOOL st\_clear (STPERSON \* pSt) ###

注意这里是清空栈,  并不是销毁栈, 所以并不会释放栈本身的内存和栈成员的内存, 只是释放栈里所有有效节点的内存.

有人问, 直接让phead的尾部指针指向pbuttom 就ok了?

的确, 这个栈就成为1个空栈, 但是那些存放有效数据的节点很容易就找回来, 造成内存泄露

所以我在这个函数里会释放掉这些存放有效数据节点的内存.

BOOL st_clear(STPERSON * pSt){
    	if (TRUE != pSt->is_inited){
    		printf("the stuck is not initialed yet\n");
    		return FALSE;
    	}
    
    	PERSON_ST * pnode = pSt->phead;
    	PERSON_ST * pAfter = pnode->pnext;
    	//free(pnode); do not free phead;
    	while (pSt->pbuttom != pAfter){ //do not free the pbuttom
    		pnode=pAfter;
    		printf("free pnode which id is %d\n",pnode->id);
    		pAfter=pnode->pnext;
    		free(pnode);
    	}
    
    	//free(pSt); do not free the stuck
    	pSt->phead->pnext = pSt->pbuttom;
    	pSt->len=0;
    	return TRUE;
    }

### 5.11 清空栈函数 BOOL st\_free (STPERSON \* pSt) ###

这个函数跟上面的很类似, 只不过这个函数还会释放栈本身的内存.

释放栈本身内存之前, 要释放栈里面指针成员的内存 ,  我相信会更加安全:

代码如下:

BOOL st_free(STPERSON * pSt){
    	st_clear(pSt);
    
    	free(pSt->phead);
    	free(pSt->pbuttom);
    
    	free(pSt);
    	pSt=NULL;
    	return TRUE;
    }

这样我在头文件里声明的函数都写完了.  下面会测试一下

### 5.12 写1个测试的小程序. ###

当然这个测试程序会引用上面的头文件, 会新建1个栈, 还会尝试出栈, 入栈动作.

代码如下:

int stuck_1(){
    	PERSON_ST * pnode = person_st_new(1,"Jasonabc1234567890111111110");
    	person_st_print(pnode);
    	free(pnode);
    
    	STPERSON * pst1 = st_create();
    	st_push(pst1,person_st_new(1, "Jason"));
    	st_push(pst1,person_st_new(2, "Cindy"));
    	st_push(pst1,person_st_new(3, "Gateman"));
    	st_push(pst1,person_st_new(4, "Fiana"));
    	st_print(pst1);
    
    	printf("top twice\n\n");
    	st_pop(pst1, &pnode);
    	person_st_print(pnode);
    	free(pnode);
    
    	st_pop(pst1, &pnode);
    	person_st_print(pnode);
    	free(pnode);
    
    	printf("top done\n\n");
    
    	st_print(pst1);
    
    	st_clear(pst1);
    	st_free(pst1);
    	printf("stuck_1 done\n");
    	return 0;
    }

输出:

![444127020130414140941019.png][]

## 6. 栈的一些实际应用 ##

### 6.1 函数调用 ###

假如代码中定义了1个函数 f(),   f()调用了函数g(),  g()里面又调用了函数k(),

那么调用时首先会放f()压入栈执行,  同时会将f()里面的变量及对应地址压入栈.

当f()里面调用g()时. 再将g()压入栈执行,

当g() 里面再调用k() 时, 会再将k()压入栈执行.

当k() 执行完时, 里面的变零和相关地址会释放, 就会把k()的相关信息移除出栈, 相当于出栈.

出栈同时返回地址,  那么g()就知道 k()执行完成, 那么g()继续执行

g()执行完时, 也会出栈.... f()继续执行

大概就是这个道理.

### 6.2 表达式求值 ###

### 6.3 内存分配 ###

### 6.4 缓冲处理 ###

### 6.5 走迷宫 ###

上面的有点困难,  以后有机会再另外讲..

[E6_A0_88.JPG]: http://jpkc.onlinesjtu.com/fckUpload/%E6%A0%88.JPG
[444127020130414000823044.png]: http://img142.poco.cn/mypoco/myphoto/20130414/00/444127020130414000823044.png
[444127020130414001000063.png]: http://img142.poco.cn/mypoco/myphoto/20130414/00/444127020130414001000063.png
[444127020130414001116025.png]: http://img142.poco.cn/mypoco/myphoto/20130414/00/444127020130414001116025.png
[444127020130414001222034.png]: http://img142.poco.cn/mypoco/myphoto/20130414/00/444127020130414001222034.png
[444127020130414000613012.png]: http://img142.poco.cn/mypoco/myphoto/20130414/00/444127020130414000613012.png
[c_]: http://blog.csdn.net/nvd11/article/details/8749395
[444127020130414140941019.png]: http://img142.poco.cn/mypoco/myphoto/20130414/14/444127020130414140941019.png