文章目录
【 1. 基本原理 】
【 2. 动态链表栈 】 2.1 双结构体实现 2.1.0 栈的节点设计 2.1.1 入栈 2.1.2 出栈 2.1.3 遍历 2.1.4 实例
2.2 单结构体实现 2.2.0 栈的节点设计 2.2.1 入栈 2.2.2 出栈 2.2.3 实例
【 3. 顺序栈 】
【 1. 基本原理 】
栈(Stack) 是一个线性的数据结构:
栈只能从表的一端存取数据,另一端是封闭的; 在栈中,无论是存数据还是取数据,都必须遵循"先进后出"的原则,即最先进栈的元素最后出栈。 栈的开口端被称为 栈顶 ,栈顶元素指的就是距离栈顶最近的元素;封口端被称为 栈底 ,栈底元素指的是位于栈最底部的元素。 栈的的应用
栈的分类
栈分为数组栈和链表栈:
顺序栈(数组栈) 采用顺序存储结构,使用数组进行功能的模拟,实现较为快速和便利。链表栈(链栈) 采用链式存储结构,实现较为麻烦,但是其稳定不易出错。在链表栈中又分为静态链表栈 和 动态链表栈:
静态链表栈 给定栈的空间大小 ,不允许超过存储超过给定数据大小的元素。动态链表栈 使用的是 自动创建空间 的方法进行创建,只要符合机器的硬件要求以及编译器的控制,其理论上是极大的。
【 2. 动态链表栈 】
我们以链表栈的动态链表栈为例子,进行栈的设计,在后文直接以栈一名字称呼动态链表栈,这也是各类语言标准模板中栈的实现方式。
2.1 双结构体实现
2.1.0 栈的节点设计
我们可以设计出两个结构体:
一个结构体Node表示结点,其中包含有一个data域和next指针。其中data表示数据,其可以是简单的类型(如int,double等等),也可以是复杂的结构体(struct类型);next指针表示,下一个的指针,其指向下一个结点,通过next指针将各个结点链接。 额外添加的另一个结构体,其包括了一个永远指向栈头的指针top和一个计数器count记录元素个数,(也可以设计成一个指针top和一个指针bottom分别指向栈头和栈尾)其主要功效就是设定允许操作元素的指针以及确定栈何时为空(count的方法是当count为0时为空,top和bottom方法就是两者指向同一个空间时为栈为空)。 采用的 top 和 count 组合的方法,C 实现:
typedef struct node
{
int data;
struct node * next;
} Node;
typedef struct stack
{
Node * top;
int count;
} Link_Stack;
2.1.1 入栈
入栈(push)操作时,我们只需要找到top所指向的空间,创建一个新的结点,将新的结点的next指针指向我们的top指针指向的空间,再将top指针转移,指向新的结点,即是入栈操作。 C 实现:
Link_Stack * Push_stack ( Link_Stack * p, int elem)
{
if ( p == NULL )
return NULL ;
Node * temp;
temp= ( Node* ) malloc ( sizeof ( Node) ) ;
temp-> data = elem;
temp-> next = p-> top;
p-> top = temp;
p-> count++ ;
return p;
}
2.1.2 出栈
出栈(pop)操作,是在栈不为空的情况下(注意一定要进行判空操作),将栈顶的元素删除,同时top指针,next向下进行移动即可的操作。 C 实现:
Link_Stack * Pop_stack ( Link_Stack * p)
{
Node * temp;
temp = p-> top;
if ( p-> top == NULL )
{
printf ( "错误:栈为空" ) ;
return p;
}
else
{
p-> top = p-> top-> next;
free ( temp) ;
p-> count-- ;
return p;
}
}
2.1.3 遍历
栈的遍历,由于栈的特殊性质,其只允许在一端进行操作,所以我们的遍历操作永远都是逆序的,其过程为:在栈不为空的情况下,一次从栈顶元素向下访问,直到指针指向空(即到栈尾)为结束。 C 实现:
int show_stack ( Link_Stack * p)
{
Node * temp;
temp = p-> top;
if ( p-> top == NULL )
{
printf ( "" ) ;
printf ( "错误:栈为空" ) ;
return 0 ;
}
while ( temp != NULL )
{
printf ( "%d\t" , temp-> data) ;
temp = temp-> next;
}
printf ( "\n" ) ;
return 0 ;
}
2.1.4 实例
# include <stdio.h>
# include <stdlib.h>
typedef struct node
{
int data;
struct node * next;
} Node;
typedef struct stack
{
Node * top;
int count;
} Link_Stack;
Link_Stack * Creat_stack ( )
{
Link_Stack * p;
p= ( Link_Stack* ) malloc ( sizeof ( Link_Stack) ) ;
if ( p== NULL ) {
printf ( "创建失败,即将退出程序" ) ;
exit ( 0 ) ;
}
p-> count = 0 ;
p-> top = NULL ;
return p;
}
Link_Stack * Push_stack ( Link_Stack * p, int elem)
{
if ( p == NULL )
return NULL ;
Node * temp;
temp= ( Node* ) malloc ( sizeof ( Node) ) ;
temp-> data = elem;
temp-> next = p-> top;
p-> top = temp;
p-> count++ ;
return p;
}
Link_Stack * Pop_stack ( Link_Stack * p)
{
Node * temp;
temp = p-> top;
if ( p-> top == NULL )
{
printf ( "错误:栈为空" ) ;
return p;
}
else
{
p-> top = p-> top-> next;
free ( temp) ;
p-> count-- ;
return p;
}
}
int show_stack ( Link_Stack * p)
{
Node * temp;
temp = p-> top;
if ( p-> top == NULL )
{
printf ( "" ) ;
printf ( "错误:栈为空" ) ;
return 0 ;
}
while ( temp != NULL )
{
printf ( "%d\t" , temp-> data) ;
temp = temp-> next;
}
printf ( "\n" ) ;
return 0 ;
}
int main ( )
{
Link_Stack * p;
p = Creat_stack ( ) ;
int n = 5 ;
int input[ 6 ] = { 10 , 20 , 30 , 40 , 50 , 60 } ;
for ( int i= 0 ; i< n; i++ ) {
Push_stack ( p, input[ i] ) ;
}
show_stack ( p) ;
Pop_stack ( p) ;
show_stack ( p) ;
return 0 ;
}
2.2 单结构体实现
使用单结构体实现链表:
在实现数据"入栈"操作时,需要将数据从链表的头部插入(单链表的头插法); 在实现数据"出栈"操作时,需要删除链表头部的首元节点;
2.2.0 栈的节点设计
typedef struct lineStack {
int data;
struct lineStack * next;
} lineStack;
2.2.1 入栈
将元素 1、2、3、4 依次入栈,等价于将各元素采用头插法依次添加到链表中,每个数据元素的添加过程如图所示: C实现:
typedef struct lineStack {
int data;
struct lineStack * next;
} lineStack;
lineStack* push ( lineStack * stack, int a) {
lineStack * line= ( lineStack* ) malloc ( sizeof ( lineStack) ) ;
line-> data= a;
line-> next= stack;
stack= line;
return stack;
}
2.2.2 出栈
若要将元素 3 出栈,根据"先进后出"的原则,要先将元素 4 出栈,也就是从链表中摘除,然后元素 3 才能出栈: C 实现:
lineStack * pop ( lineStack * stack) {
if ( stack) {
lineStack * p= stack;
stack= stack-> next;
printf ( "出栈元素:%d " , p-> data) ;
if ( stack) {
printf ( "新栈顶元素:%d\n" , stack-> data) ;
} else {
printf ( "栈已空\n" ) ;
}
free ( p) ;
} else {
printf ( "栈内没有元素" ) ;
return stack;
}
return stack;
}
2.2.3 实例
# include <stdio.h>
# include <stdlib.h>
typedef struct lineStack {
int data;
struct lineStack * next;
} lineStack;
lineStack* push ( lineStack * stack, int a) {
lineStack * line= ( lineStack* ) malloc ( sizeof ( lineStack) ) ;
line-> data= a;
line-> next= stack;
stack= line;
return stack;
}
lineStack * pop ( lineStack * stack) {
if ( stack) {
lineStack * p= stack;
stack= stack-> next;
printf ( "弹栈元素:%d " , p-> data) ;
if ( stack) {
printf ( "栈顶元素:%d\n" , stack-> data) ;
} else {
printf ( "栈已空\n" ) ;
}
free ( p) ;
} else {
printf ( "栈内没有元素" ) ;
return stack;
}
return stack;
}
int main ( ) {
lineStack * stack= NULL ;
stack= push ( stack, 1 ) ;
stack= push ( stack, 2 ) ;
stack= push ( stack, 3 ) ;
stack= push ( stack, 4 ) ;
stack= pop ( stack) ;
stack= pop ( stack) ;
stack= pop ( stack) ;
stack= pop ( stack) ;
stack= pop ( stack) ;
return 0 ;
}
【 3. 顺序栈 】
我们通过顺序表(底层实现是数组)模拟顺序栈/数组栈。思路为:在顺序表中设定一个实时指向栈顶元素的变量(一般命名为 top),top 初始值为 -1,表示栈中没有存储任何数据元素,及栈是"空栈"。一旦有数据元素进栈,则 top 就做 +1 操作;反之,如果数据元素出栈,top 就做 -1 操作。
3.1 入栈
比如,模拟栈存储 {1,2,3,4} 的过程。最初,栈是"空栈",即数组是空的,top 值为初始值 -1: 首先向栈中添加元素 1,我们默认数组下标为 0 一端表示栈底,因此,元素 1 被存储在数组 a[0] 处,同时 top 值 +1: 采用以上的方式,依次存储元素 2、3 和 4,最终,top 值变为 3: C 实现:
int push ( int * a, int top, int elem) {
a[ ++ top] = elem;
return top;
}
3.2 出栈
将上图中的元素 2 出栈,则需要先将元素 4 和元素 3 依次出栈。当有数据出栈时,要将 top 做 -1 操作。因此,元素 4 和元素 3 出栈的过程分别如图所示: 上图中数组中元素的消失仅是为了方便初学者学习,其实,这里只需要对 top 值做 -1 操作即可,因为 top 值本身就表示栈的栈顶位置,因此 top-1 就等同于栈顶元素出栈。并且后期向栈中添加元素时,新元素会存储在类似元素 4 这样的旧元素位置上,将旧元素 覆盖 。 C 实现:
int pop ( int * a, int top) {
if ( top== - 1 ) {
printf ( "空栈" ) ;
return - 1 ;
}
printf ( "弹栈元素:%d\n" , a[ top] ) ;
top-- ;
return top;
}
3.3 实例
# include <stdio.h>
int push ( int * a, int top, int elem) {
a[ ++ top] = elem;
return top;
}
int pop ( int * a, int top) {
if ( top == - 1 ) {
printf ( "空栈" ) ;
return - 1 ;
}
printf ( "弹栈元素:%d\n" , a[ top] ) ;
top-- ;
return top;
}
int main ( ) {
int a[ 100 ] ;
int top = - 1 ;
top = push ( a, top, 3 ) ;
top = push ( a, top, 1 ) ;
top = push ( a, top, 4 ) ;
top = push ( a, top, 5 ) ;
top = pop ( a, top) ;
top = pop ( a, top) ;
top = pop ( a, top) ;
top = pop ( a, top) ;
top = pop ( a, top) ;
return 0 ;
}
# include <stdio.h>
# include <stdlib.h>
# include <string.h>
# define maxn 10000
typedef struct stack {
int data[ maxn] ;
int top;
} stack;
stack * init ( ) {
stack * s= ( stack * ) malloc ( sizeof ( stack) ) ;
if ( s== NULL ) {
printf ( "分配内存空间失败" ) ;
exit ( 0 ) ;
}
memset ( s-> data, 0 , sizeof ( s-> data) ) ;
s-> top= 0 ;
return s;
}
void push ( stack * s, int data) {
s-> data[ s-> top] = data;
s-> top++ ;
}
void pop ( stack * s) {
if ( s-> top!= 0 ) {
s-> data[ s-> top] = 0 ;
s-> top-- ;
}
}
void print_stack ( stack * s) {
for ( int n= s-> top- 1 ; n>= 0 ; n-- ) {
printf ( "%d\t" , s-> data[ n] ) ;
}
printf ( "\n" ) ;
}
int main ( ) {
stack * s= init ( ) ;
int input[ 5 ] = { 11 , 22 , 33 , 44 , 55 } ;
for ( int i= 0 ; i< 5 ; i++ ) {
push ( s, input[ i] ) ;
}
print_stack ( s) ;
pop ( s) ;
print_stack ( s) ;
return 0 ;
}