顺序栈与链栈

栈：先进后出，后进先出，那么该如何创建一个栈呢，下面我们将讲述顺序栈与链栈的创建 

【问题描述】

设一个顺序栈，进行出栈和入栈 *** 作。
【输入形式】

输入若干个整数（不超过1000），依次入栈；（提示：scanf("%d",&e)==1来作为输入判断）
【输出形式】

依次出栈并输出元素值，以空格分隔。
【样例输入】

23 45 67 14 -9 20 100 89 45 30
【样例输出】

30 45 89 100 20 -9 14 67 45 23

目录

一、顺序栈 

1.1 初始化顺序栈 

1.2 判断是否空栈

1.3 入栈

1.4 出栈

1.5 获取栈顶元素

1.6 代码实现

1.6.1 完整代码

1.6.2 运行结果

二、链栈 

2.1 初始化链栈

2.2 判断是否空栈

2.3 入栈

2.4 出栈

2.5 获取栈顶元素

2.6 代码实现

2.6.1 完整代码

2.6.2 运行结果

三、总结

---

 

一、顺序栈 

  顺序栈主要运用顺序表实现，我们需要一个指向栈底的指针和一个指向栈顶的指针。

1.1 初始化顺序栈 

#include
#include
#define SIZE 10
#define INCREAM 10
typedef struct stack{
	int *base;         //栈底指针
	int *top;          //栈顶指针
	int size;          //初始空间大小
}stack,*Pstack;
void Init_stack(Pstack s){
	s->base=(int *)malloc(sizeof(int)*SIZE);
	s->top=s->base;    //初始化栈顶指针在栈底位置
	s->size=SIZE;
}

1.2 判断是否空栈

int Empty_stack(Pstack s){
	if(s->base==s->top)   //当栈顶指针在栈底时，栈空
	return 1;
	else
	return 0;
}

1.3 入栈

void Push_stack(Pstack s,int x){
	if(s->top-s->base>=s->size){    //首先要判断栈满，栈满要重新开辟空间
		s->base=(int *)realloc(s->base,(s->size+INCREAM)*sizeof(int));
		s->top=s->base+s->size; 
		s->size+=INCREAM;
	}
	*s->top=x;      //压栈
	s->top++;       //栈顶指针加一
}

1.4 出栈

void Pop_stack(Pstack s,int *x){
	if(s->base==s->top){     //出栈要先判断栈是否为空，空栈无法出栈
		return ;
	}
	s->top--;                //先让栈顶指针指向最后一个压进去的值
	*x=*s->top;              //然后再输出这个值
}

1.5 获取栈顶元素

void Get_top_stack(Pstack s,int *x){
	if(s->base==s->top){
		return ;
	}
	*x=*(s->top-1);
}

1.6 代码实现 1.6.1 完整代码

#include
#include
#define SIZE 10
#define INCREAM 10
typedef struct stack{
	int *base;
	int *top;
	int size;
}stack,*Pstack;
void Init_stack(Pstack s){
	s->base=(int *)malloc(sizeof(int)*SIZE);
	s->top=s->base;
	s->size=SIZE;
}
int Empty_stack(Pstack s){
	if(s->base==s->top)
	return 1;
	else
	return 0;
}
void Push_stack(Pstack s,int x){
	if(s->top-s->base>=s->size){
		s->base=(int *)realloc(s->base,(s->size+INCREAM)*sizeof(int));
		s->top=s->base+s->size;
		s->size+=INCREAM;
	}
	*s->top=x;
	s->top++;
}
void Pop_stack(Pstack s,int *x){
	if(s->base==s->top){
		return ;
	}
	s->top--;
	*x=*s->top;
}
void Get_top_stack(Pstack s,int *x){
	if(s->base==s->top){
		return ;
	}
	*x=*(s->top-1);
}
int main(){
	int x;
	stack s;
	Init_stack(&s);
	while(scanf("%d",&x)==1){
		Push_stack(&s,x);
	}
	while(!Empty_stack(&s)){
		Pop_stack(&s,&x);
		printf("%d ",x);
	}
	return 0;
}

1.6.2 运行结果

二、链栈 

  链栈就相当于带头结点单链表的头插法，入栈就是每次都在头结点后面插入一个新元素，出栈就是每次让头结点的指针域指向第一个有效结点后面一个结点。

2.1 初始化链栈

#include
#include
#include
#include
typedef struct Stack{
	int data;
	struct Stack *next;
}Stack,*PStack;
PStack Init_Stack(){                 //就是初始化一个带头结点的单链表
	PStack S=(PStack)malloc(sizeof(Stack));
	S->next=NULL;  
	return S;
}

2.2 判断是否空栈

int Empty_Stack(PStack S){
	if(!S->next) return 1;
	else return 0; 
}

2.3 入栈

void Push_Stack(PStack S,int e){
	PStack Pnew;
	Pnew=(PStack)malloc(sizeof(Stack));
	Pnew->next=NULL;
	Pnew->data=e;   
	Pnew->next=S->next;     //入栈就是头插法
	S->next=Pnew;
}

2.4 出栈

void Pop_Stack(PStack S,int *e){
	if(S->next){               //先判断是否栈空
	    *e=S->next->data;      //出栈就是头结点指针域指向第一个有效结点后面的结点
	    S->next=S->next->next;		//相当于每次出栈都是删除掉第一个有效结点
	}else{
		return ;
	}
}

2.5 获取栈顶元素

void Get_Stack(PStack S,int *e){  //获取栈顶元素方法不用删除结点
	if(S->next){
		*e=S->next->data;
	}else{
		return ;
	}
}

2.6 代码实现 2.6.1 完整代码

#include
#include
#include
#include
typedef struct Stack{
	int data;
	struct Stack *next;
}Stack,*PStack;
PStack Init_Stack(){
	PStack S=(PStack)malloc(sizeof(Stack));
	S->next=NULL;
	return S;
}
int Empty_Stack(PStack S){
	if(!S->next) return 1;
	else return 0; 
}
void Push_Stack(PStack S,int e){
	PStack Pnew;
	Pnew=(PStack)malloc(sizeof(Stack));
	Pnew->next=NULL;
	Pnew->data=e;
	Pnew->next=S->next;
	S->next=Pnew;
}
void Pop_Stack(PStack S,int *e){
	if(S->next){
	    *e=S->next->data;
	    S->next=S->next->next;		
	}else{
		return ;
	}
}
void Get_Stack(PStack S,int *e){
	if(S->next){
		*e=S->next->data;
	}else{
		return ;
	}
}
void Print_Stack(PStack S){
	PStack p=S->next;
	while(p){
		printf("%d ",S->data);
		p=p->next;
	}
	printf("\n");
}
int Match_Stack(PStack S,char ch[]){
	int i,e;
	for(i=0;i

2.6.2 运行结果

 

三、总结

1.顺序栈是个顺序表，需要指向栈底的指针和一个时刻指向栈顶的指针

2.链栈我用的是带头结点的单链表，这样方便出栈（删除结点），也可以用不带头结点的单链表

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/3002609.html