C语言高级-4栈

14天阅读挑战赛

目录

一、栈的原理

1、栈的定义

2、栈的应用

（1）选课问题

（2）旅游：怎么样把每个城市去且仅去一遍？

（3）栈的使用场景

（4）思考：栈为什么要有限制，后进先出？

（5）栈的应用-表达式求值

二、顺序栈

1、顺序栈定义

2、创建栈

3、清空栈:

4、判断栈是否空 

5、判断栈是否满

6、进栈 

7、出栈 

8、取栈顶元素

9、释放

10、定义测试函数

三、链式栈原理及实现

1、定义

2、创建栈

3、入栈

4、出栈

5、是否空栈

6、取栈顶指针的值

7、清空栈

8、栈是否满

9、释放栈内存

---

一、栈的原理

1、栈的定义

• 栈是限制在一端进行插入操作和删除操作的线性表（俗称堆栈）
• 允许进行操作的一端称为“栈顶”
• 另一固定端称为“栈底”
• 当栈中没有元素时称为“空栈”。
• 特点 ：后进先出（LIFO）。

2、栈的应用

（1）选课问题

如上图，加入我们学习计算机课程，有些课程需要建立在先行课程基础上才能学习，那么我们该如何选择呢？

上图中，我们发现，如果我们像学习一门课程，我们就需要把它放到栈底，然后找到它的前驱课程，然后一直类推找前驱课程，直到一个没有前驱课程的课程，就是栈顶，当我们学习完一门课程就是出栈，利用栈这个模型就解决了我们选课的问题。

（2）旅游：怎么样把每个城市去且仅去一遍？

选一个方向，到头后原路返回。再去访问另一个分支。

如果用递归也可以解决，但是比较容易出错

（3）栈的使用场景

• 语法检查，符号成对出现。在我们日常编程中，括号都是成对出现的，比如“()”“[]”“{}”“<>”这些成对出现的符号。
• 数制转换。比如100的八进制，100首先除以8商12余4,4首先进栈，然后12除以8商1余4，第二个余数4进栈接着1除以8，商0余1，第三个余数1进栈，最后将三个余数出栈，就得到了100的八进制数144。
• 浏览器的前进后退

（4）思考：栈为什么要有限制，后进先出？

把一个非线性的问题，线性化。把前驱课程放在底入栈，没有之后再把其他课程放进去，一层一层转换为线性问题。

（5）栈的应用-表达式求值

• 建立操作数栈和运算符栈。运算符有优先级。
• 自左至右扫描表达式，凡是遇到操作数一律进操作数栈。
• 当遇到运算符时，如果它的优先级比运算符栈栈顶元素的优先级高就进栈。反之，取出栈顶运算符和操作数栈栈顶的连续两个操作数进行运算，并将结果存入操作数栈，然后继续比较该运算符与栈顶运算符的优先级。
• 左括号一律进运算符栈，右括号一律不进运算符栈，取出运算符栈顶运算符和操作数栈顶的两个操作数进行运算，并将结果压入操作数栈，直到取出左括号为止。

 

二、顺序栈

1、顺序栈定义

它是顺序表的一种，具有顺序表同样的存储结构，由数组定义，配合用数组下标表示的栈顶指针top（相对指针）完成各种操作。

定义sqstack.h文件

typedef  int  data_t ; /*定义栈中数据元素的数据类型*/
typedef struct {        
    data_t  *data ;  /*用指针指向栈的存储空间*/         如果用data[]数组，必须提前设定好数组长度，用指针可以让用户自定义
    int  maxlen; /*当前栈的最大元素个数*/       
    int  top ;  /*指示栈顶位置(数组下标)的变量*/  
} sqstack;   /*顺序栈类型定义*/
 
sqstack * stack_create(int len);           
int stack_push(sqstack * s, data_t value);
int stack_empty(sqstack *s);
int stack_full(sqstack *s);
data_t stack_pop(sqstack *s);
data_t stack_top(sqstack *s);
int stack_clear(sqstack *s);
int stack_free(sqstack *s);       

2、创建栈

接下来实现sqstack.c

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

malloc，第一次是结构体，第二次是结构体里数据，用户传进来的值。

3、清空栈:

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

4、判断栈是否空 

/*
 *@ret 1-empty
 * */
int stack_empty(sqstack *s) {
	if (s == NULL) {
		printf("s is NULL\n");
		return -1;
	}
	return (s->top == -1 ? 1 : 0);
}

5、判断栈是否满

/*
 * @ret 1-full
 * */
int stack_full(sqstack *s) {
	if (s == NULL) {
		printf("s is NULL\n");
		return -1;
	}
	return  (s->top == s->maxlen-1 ? 1 : 0);
}

6、进栈 

int stack_push(sqstack * s, data_t value) {
	if (s == NULL) {
		printf("s is NULL\n");
		return -1;
	}
 
	if (s->top == s->maxlen-1) {
		printf("stack is full\n");
		return -1;
	}
 
	s->top++;
	s->data[s->top] = value;
 
	return 0;
}

7、出栈 

data_t stack_pop(sqstack *s) {
	s->top--;
	return (s->data[s->top+1]);
}

8、取栈顶元素

data_t stack_top(sqstack *s) {
	return (s->data[s->top]);
}

9、释放

需要先释放后申请的空间，再去释放前面申请的空间

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

10、定义测试函数

#include 
#include "sqstack.h"
 
int main(int argc, const char *argv[])
{
	sqstack *s;
 
	s = stack_create(100);
	if (s == NULL) 
		return -1;
 
	stack_push(s, 10);  //入栈
	stack_push(s, 20);
	stack_push(s, 30);
	stack_push(s, 40);
 
	while (!stack_empty(s)) {
		printf("pop: %d \n", stack_pop(s) );
	}
	
	stack_free(s);
 
	return 0;
}

三、链式栈原理及实现

1、定义

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

typedef int data_t;
 
typedef struct node {
	data_t data;
	struct node *next;
}listnode, *linkstack;
 
linkstack stack_create();
int stack_push(linkstack s, data_t value);
data_t stack_pop(linkstack s);
int stack_empty(linkstack s);
data_t stack_top(linkstack s);
linkstack stack_free(linkstack s);

2、创建栈

接下来实现linkstack.c

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

3、入栈

int stack_push(sqstack * s, data_t value) {
	if (s == NULL) {
		printf("s is NULL\n");
		return -1;
	}
 
	if (s->top == s->maxlen-1) {
		printf("stack is full\n");
		return -1;
	}
 
	s->top++;
	s->data[s->top] = value;
 
	return 0;
}

4、出栈

data_t stack_pop(sqstack *s) {
	s->top--;
	return (s->data[s->top+1]);
}

5、是否空栈

/*
 *@ret 1-empty
 * */
int stack_empty(sqstack *s) {
	if (s == NULL) {
		printf("s is NULL\n");
		return -1;
	}
	return (s->top == -1 ? 1 : 0);
}

6、取栈顶指针的值

data_t stack_top(sqstack *s) {
	return (s->data[s->top]);
}

7、清空栈

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

8、栈是否满

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

9、释放栈内存

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