数据结构（C语言）-线性表之栈（顺序栈、链式栈）-学习笔记03

• 1. 基本介绍
• 2. 顺序栈
• • 2.1 定义：
  • 2.2 创建栈
  • 2.3 入栈
  • 2.4 出栈
  • 2.5 查看栈顶
  • 2.6 清空数据
  • 2.7 释放栈内存
  • 2.8 判断栈是否为空
  • 2.9 判断栈是否已满
• 3. 链式栈
• • 3.1 创建栈
  • 3.2 入栈
  • 3.3 出栈
  • 3.4 查找栈顶
  • 3.5 查找栈底

• 栈是限制在一端进行插入操作和删除操作的线性表
• 允许进行操作的一端称为栈顶
• 另一端固定端称为栈底
• 当没有元素的时候称为空栈
• 后进先出
  

typedef int data_t;
typedef struct{
	data_t *data;
	int maxlen;
	int top; //栈顶的位置
}sqstack;

sqstack *create(int len){
	sqstack *s;
	if ((s=(sqstack *)malloc(sizeof(sqstack))) == NULL){
		printf("malloc sqstack failed");
		return NULL;
	}
	if ((s->data = (data_t *)malloc(len *sizeof(data_t))) == NULL){
		printf("malloc data failed");
		return NULL;
	}
	memset(s->data, 0, len*sizeof(data_t));
	s->maxlen = len;
	s->top = -1;
	return s;
}

int push(sqstack *s, int value){
	if (s == NULL){
		printf("s is NULLn");
		return -1;
	}
	if (s->top == s->maxlen-1){
		printf("stack is fulln");
		return -1;
	}
	s->top++;
	s->data[s->top] = value;
	return 0;
}

data_t pop(sqstack *s){
	int pop_data;
	pop_data = s->data[s->top];
	s->data[s->top] = 0;
	s->top--;
	return pop_data;
}

data_t top(sqstack *s){
	if (s == NULL){
		printf("s is NULLn");
		return -1;
	}
	return s->data[s->top];
}

int clear(sqstack *s){
	if (s == NULL){
		printf("s is NULLn");
		return -1;
	}
	s->top = -1;
	return 0;
}

int stack_free(sqstack *s){
	if (s == NULL){
		printf("s is NULLn");
		return -1;
	}
	if (s->data != NULL)
		free(s->data);
	free(s);
	return 0;
}

int empty(sqstack *s){
	if (s == NULL){
		printf("s is NULLn");
		return -1;
	}
	return s->top == -1?1:0;
}

int full(sqstack *s){
	if (s == NULL){
		printf("s is NULLn");
		return -1;
	}
	return (s->top == s->maxlen-1?1:0);
}

• 插入操作和删除操作均在链表头部进行，链表尾部就是栈底，栈顶指针就是头指针
  

linkstack create(){
	linkstack s;

	s = (linkstack)malloc(sizeof(listnode));
	if (s == NULL){
		printf("malloc failedn");
		return NULL;
	}
	s->data = 0;
	s->next = NULL;
	return s;
}

int push(linkstack s, int value){
	linkstack p;
	p = (linkstack)malloc(sizeof(listnode));
	if (s == NULL){
		printf("malloc failedn");
		return -1;
	}
	p->data = value;
	p->next = s->next;
	s->next = p;

	return 0;
}

data_t pop(linkstack s){
	linkstack p;
	data_t data;

	data = s->next->data;
	p = s->next;
	s->next = p->next;

	free(p);
	p = NULL;
	return data;
}

data_t top(linkstack s){
	return s->next->data;
}

int stack_free(linkstack s){
	int data;
	while(!empty(s)){
		data = pop(s);
		printf("free: %dn", data);
	}
	free(s);
	return 0;
}

int empty(linkstack s){
	if (s == NULL){
		printf("s is NULLn");
		return 0;
	}
	return s->next==NULL ? 1 : 0;
}