学习随记三——顺序栈和链栈的定义和基本运算

顺序栈和链栈的定义和基本运算

1. 顺序栈和链栈的区别

   （1）、顺序栈是事先确定好大小的，链栈是动态的，它们的区别类似于数组和链表

   （2）、存储空间不同，顺序栈是一块连续的存储空间，链栈是不连续的存储空间，也类似于数组和链表

   顺序栈和链栈更像是运算受限制的数组和链表

2. 顺序栈的定义和基本运算

#include<stdio.h>
const int StackSize=100;	//确定栈的大小
typedef struct Stack{
	int data[StackSize];		//数据域 
	int top;		//指示栈顶位置 
}Stack;
//顺序栈的基本运算
//置栈空，判栈空，判栈满，进栈，退栈，取栈顶元素 
void InitStack(Stack*s){		//置栈空 
	s->top=-1;
} 
int StackEmpty(Stack*s){		//判栈空
	return s->top==-1; 
}
int StackFull(Stack*s){			//判栈满
	return s->top==StackSize-1;
}
int Push(Stack*s,int x){				//进栈
	if(StackFull(s)){
		printf("The stack is overflow\n");
		return 0;
	} else{
		s->data[++s->top]=x;	//s->top先自加然后存入变量x
	}
	return 1;	//返回1代表函数正常调用
}
int Pop(Stack*s){				//退栈 
	if(StackEmpty(s)){
		printf("The stack is empty\n");
		return 0;
	}else
	return s->data[s->top--];	//返回data[s->top]然后s->top减一
}
int StackTop(Stack*s){			//取栈顶元素
	if(StackEmpty(s)){
		printf("The stack is empty\n");
		return 0;
	} else
	return s->data[s->top];
}
int main(void){
}
           

1. 链栈的定义和基本运算

#include<stdio.h>
#include<stdlib.h>
typedef struct StackNode{
	int data;		//数据域
	struct StackNode *next;		//指针域
}Stack;
typedef struct LinkStack{	//再命名一个结构体是为了方便使用栈顶指针，可以在这个结构体中加一个计数变量来记录位置
	struct StackNode* top;	//栈顶指针
}LinkStack;
void InitStack(LinkStack*s){		//置栈空
	s->top=NULL;
}
int StackEmpty(LinkStack*s){		//判栈空
	return s->top==NULL; 
}
int Push(LinkStack*s,int x){			//进栈
	 Stack *p=(Stack*)malloc(sizeof(Stack));
	 p->data=x;
	 p->next=s->top;
	 s->top=p;
}
int Pop(LinkStack*s){				//退栈
	if(StackEmpty(s)){
		printf("Stack underflow\n");
		return 0;
	} 
	Stack*p=s->top;		//保存栈顶指针的地址
	int x=p->data;		//保存data中的数据
	s->top=p->next;		//删除栈顶
	free(p);			//释放不需要的结点
	return x;			//返沪栈顶数据
}
int StackTop(LinkStack*s){			//取栈顶元素
	if(StackEmpty(s)){
		printf("the stack is empty\n");
		return 0;
	} 
	return s->top->data;
}
int main(void){
}