数据结构（c语言版）第三章栈和队列

栈(栈的表示和实现）：

抽象数据栈的定义：

栈（stack）栈是限定仅在表尾进行插入或删除操作的线性表，因此表尾对栈有着特殊的含义，称为栈顶（top),相应表头成为栈底（bottom)，不含元素的空表称为空栈。

因为栈的进出都是从表尾进行插入和删除，于是又叫后进先出（last in first out)也能叫先进后出。

线性表类似，对于栈来说，也有两种存储结构（1）顺序栈（2）链式栈

（1）顺序栈：

顺序栈的结构结构体单位我们一般有两个指针和一个整型数据，其中整型数据代表此时栈的总空间大小，其中一个指针始终指向栈底，另一个指针始终指向栈顶。

当两个指针指向同一个位置时，那么此时就是空栈。

栈的结构的实现

struct stacks{
	int *base;
	int *top;
	int stacksize;
};

开辟一个栈

void creatstack(struct stacks *s,int size){
	s->base = (int*)malloc(size*sizeof(int));
	if(!s->base)exit(0);
	s->top = s->base;
	s->stacksize = size;
}

向栈中压入元素

void push(struct stacks *s,int elements){
	if(s->top-s->base>=s->stacksize){
		s->base = (int*)realloc(s->base,(s->stacksize+1)*sizeof(int));
		if(!s->base)exit(0);
		*(s->top) = elements;
		s->top = s->base + s->stacksize+1;
		s->stacksize ++;
	}else{
		*(s->top) = elements;
		s->top ++;
		s->stacksize ++;
	}
}

将栈顶的元素取出

void pop(struct stacks *s){
	if(s->base!=s->top){
		s->stacksize --;
		int *x = s->top;
		s->top --;
	}else{
		exit(0);
	}
		
}

判断一个栈是不是空栈

int emptys(struct stacks *s){
	if(s->base==s->top)return 1;
	else return 0;
}

完整的代码

#include <stdio.h>
#include <stdlib.h>
struct stacks{
	int *base;
	int *top;
	int stacksize;
};
void creatstack(struct stacks *s,int size){
	s->base = (int*)malloc(size*sizeof(int));
	if(!s->base)exit(0);
	s->top = s->base;
	s->stacksize = size;
}
void push(struct stacks *s,int elements){
	if(s->top-s->base>=s->stacksize){
		s->base = (int*)realloc(s->base,(s->stacksize+1)*sizeof(int));
		if(!s->base)exit(0);
		*(s->top) = elements;
		s->top = s->base + s->stacksize+1;
		s->stacksize ++;
	}else{
		*(s->top) = elements;
		s->top ++;
		s->stacksize ++;
	}
}
int emptys(struct stacks *s){
	if(s->base==s->top)return 1;
	else return 0;
} 
void pop(struct stacks *s){
	if(s->base!=s->top){
		s->stacksize --;
		int *x = s->top;
		s->top --;
	}else{
		exit(0);
	}
		
}
void printstack(struct stacks *s){
	for(int *i = s->base;i < s->top;i ++){
		printf("%d ",*i);
	}
}
int main(){
	struct stacks s;
	creatstack(&s,10);
	for(int i = 1;i <= 4;i ++){
		int x;
		scanf("%d",&x);
		push(&s,x);
	}
	pop(&s);
	printstack(&s);
	pop(&s);
	pop(&s);
	pop(&s);
	printf("\n%d",emptys(&s));
}