数据结构复习ya--栈与队列

一.栈

// 1)顺序栈的基本操作：
typedef struct{
	int data[Max];
	int top;	//指向最后一位的下标 
	int stacksize;
}Stack;
//初始化
int initStack(Stack *S){
	S->top=-1;
	S->stacksize=Max; 
	return 1;
}
//	入栈
int pushstack(Stack *S,int a){
	if(S->top+1==S->stacksize){
		printf("栈满，入栈失败n");
		return 0;
	}
	S->data[++S->top]=a;
	return 1;
} 
//	创建
int creatstack(Stack *S){
	int m,a,i;
	initStack(S);
	printf("请输入要创建的数目n");
	scanf("%d",&m);
	for(i=0;itop==-1){
		printf("栈空，出栈失败n");
		return 0;
	}
	a=S->data[S->top];
	S->top--;
	return 1;
}
//	取得栈顶元素（注意top变量的取值）
int gettopstack(Stack S){
	if(S.top==-1){
		printf("获得栈顶失败n");
		return 0;
	}
	return S.data[S.top];
}
//	判栈空
int emptystack(Stack S){
	if(S.top==-1)	return 1;
	else return 0;
}
//	判栈满
int fullstack(Stack S){
	if(S.top+1==S.stacksize)	return 1;
	else return 0;
}
//	遍历
int travelstack(Stack S){
	int i;
	if(emptystack(S)){
		printf("栈空n");	return 0;
	}
	for(i=0;i<=S.top;i++)
		printf("%d	",S.data[i]);
	return 1;
}
// 2)链栈的基本操作：
typedef struct snode{
	int data;
	struct snode *next;
}Snode,*Linkstack;
//	初始化
int initlinkstack(Linkstack *L){
	*L=NULL;
	return 1;
} 
//	入栈
int pushlinkstack(Linkstack *L,int e){
	Linkstack s;
	s=(Linkstack)malloc(sizeof(snode));
	if(s==NULL)	return 0;
	s->data=e;
	s->next=*L;
	*L=s;
	return 1;
}
//	创建
int creatlinkstack(Linkstack *L){
	int m,n;
	initlinkstack(L);
	printf("请输入要创建的数目n");
	scanf("%d",&m);
	for(int i=0;idata;
	(*L)=(*L)->next;
	free(p);
	return 1;
}
//	判栈空
int emptylinkstack(Linkstack L){
	if(L==NULL)	return 1;
	else return 0;
}
//	遍历
int travellinkstack(Linkstack L){
	Linkstack p=L;
	while(p!=NULL){
		printf("%d	",p->data);
		p=p->next;
	}
	return 1;
	
}

二.队列
 

// 3)循环队列的基本操作：
typedef struct {
	int data[Max];
	int rear,front,maxsize;
}squeue;
//初始化
int initsqueue(squeue *Q){
	Q->front=Q->rear=0;
	Q->maxsize=Max;
	return 1;
} 
//	入队
int pushsqueue(squeue *Q,int e){
	if((Q->rear+1)%Q->maxsize==Q->front)	return 0;
	Q->data[Q->rear]=e;
	Q->rear=(Q->rear+1)%Q->maxsize;
	return 1;
}
//	创建
int creatsqueue(squeue *Q){
	int m,n;
	initsqueue(Q);
	printf("请输入要创建的数目n");
	scanf("%d",&m);
	for(int i=0;ifront==Q->rear)	return 0;
	*e=Q->data[Q->front];
	Q->front=(Q->front+1)%Q->maxsize;
	return 1;
}
//	队空
int emptysqueue(squeue Q){
	if(Q.front==Q.rear)	return 1;
	else return 0;
}
//队满的判定条件
int fullsqueue(squeue Q){
	if((Q.rear+1)%Q.maxsize==Q.front)	return 1;
	else return 0;
}
//	求队列长度
int lengthsqueue(squeue Q){
	return (Q.rear-Q.front+Q.maxsize)%Q.maxsize;
}
//	遍历
int travelsqueue(squeue Q){
	int i;
	for(i=Q.front;ifront=S->rear=(linksqueue)malloc(sizeof(Snode));
	if(S->front==NULL)	return 0;
	S->front->next=NULL;
	return 1;
} 
//	入队
int pushsqueuelink(squeuelink *S,int e){
	linksqueue p=(linksqueue)malloc(sizeof(Snode));
	if(p==NULL)	return 0;
	p->data=e;
	p->next=NULL;
	S->rear->next=p;
	S->rear=p;
	return 1;
} 
//	创建
int creatsqueuelink(squeuelink *S){
	int m,n;
	initsqueuelink(S);
	printf("请输入要创建的数目n");
	scanf("%d",&m);
	for(int i=0;ifront==S->rear)	return 0;
	*e=S->front->next->data;
	p=S->front->next;
	S->front->next=p->next;
	if(p==S->rear)		//原队列中只有一个元素
		S->rear=S->front; 
	free(p);		 
	return 1; 
}
//	队空
int empttysqueuelink(squeuelink S){
	if(S.front==S.rear)	return 1;
	else return 0;
}
//	遍历
int travelsqueuelink(squeuelink S){
	linksqueue p=S.front->next;
	while(p){
		printf("%d	",p->data);
		p=p->next; 
	}
	return 1;
}