数据结构——栈和队列（栈的顺序存储结构和链式存储结构）

 栈的定义

• 栈是一种重要的线性结构，可以这样讲，栈是前面讲过的线性表的一种具体形式。
• 就像我们刚才的例子，栈这种后进先出的数据结构应用是非常广泛的。在生活中，例如我们的浏览器，每次点击一次“后退”都是退回到最近的一次浏览网页。
• 例如我们Word，Photoshop等的“撤销”功能也是如此。再例如我们C语言的函数，也是利用栈的基本原理实现的。

官方定义

栈（stack）是一个后进先出（Last in first out，LIFO）的线性表，它要求只在表尾进行删除和插入操作。

所谓的栈，其实也就是一个特殊的线性表（顺序表、链表），但是他在操作上有一些特殊的要求和限制：

——栈的元素必须“后进先出”。

——栈的操作只能在这个线性表的表尾进行。

——注：对栈来说，这个表尾称为栈的栈顶（top），相应的表头称为栈底（bottom）。

栈的插入操作

栈的插入操作（Push），叫做进栈，也称为压栈，入栈。类似子弹放入弹夹的动作。

栈的删除操作

栈的删除操作（Pop），叫做出栈，也称为弹栈。如同弹夹中的子弹出夹。

栈的顺序存储结构

• 因为栈的本质是一个线性表，线性表有两种存储形式，那么栈也有分为栈的顺序存储结构和栈的链式存储结构。
• 最开始栈中不含有任何数据，叫做空栈，此时栈顶就是栈底，然后数据从栈顶进入，栈顶和栈底分离，整个栈的当前容量变大。数据出栈时从栈顶弹出，栈顶下移，整个栈的当前容量变小。

typedef int ElemType;
typedef struct
{
	ElemType* base;
	ElemType* top;
	int stackSize;
}sqStack;

• 这里定义了一个顺序存储的栈，它包含了三个元素：base，top，stackSize。其中base是指向栈底的指针变量，top是指向栈顶的指针变量，stackSize指示栈的当前可使用的最大容量。

创建一个栈

#define STACK_INIT_SIZE 100
initStack(sqStack* s)
{
	s->base = (ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));//申请一块空间
	if (!s->base)
		exit(0);
	s->top = s->base; 
	s->stackSize = STACK_INIT_SIZE;
}

malloc函数向内存申请一块连续可用的空间，如果开辟成功，则返回一个指向这个开辟好空间的起始地址 ，开辟失败，则返回一个NULL指针，因此malloc的返回值一定要做检查!

 入栈操作

• 入栈操作又叫做压栈操作，就是向栈中存放数据。
• 入栈操作要在栈顶进行，每次向栈中压入一个数据，top指针就要+1，直到栈满为止。

#define STACKINCREMENT 10 //每次追加空间的大小
Push(sqStack* s, ElemType e)
{
	//如果栈满，追加空间
	if (s->top - s->base >= s->stackSize)
	{
		s->base = (ElemType*)realloc(s->base,(s->stackSize+STACKINCREMENT)*sizeof(ElemType));
 
		if (!s->base)
			exit(0);
 
		s->top = s->base + s->stackSize;//设置栈顶 栈底+新的栈容量
		s->stackSize = s->stackSize + STACKINCREMENT;//设置栈的最大容量，原来的容量+追加的容量
	}
	*(s->top) = e; //给栈底存入数据
	s->top++; //指向栈顶的指针+1
}

realloc函数事实上也是调用malloc函数，在内存中开辟类外一个空间出来，将原来的内容拷贝到新的内存当中，要使用这个函数的话要加入头文件。

出栈操作 

•  出栈操作就是在栈顶取出数据，栈顶指针随之下移的操作。
• 每当从栈内弹出一个数据，栈的当前容量就-1。

Pop(sqStack* s, ElemType* e)
{
	if (s->top == s->base) //栈空了，没有数据存放，此时可以进行返回
		return;
	*e = *--(s->top); //先栈顶指针-1，然后再取出数据赋值
}

注意：top指针指向的栈顶是没有数据存放的，所以要先指向-1，再进行取值操作。

 清空一个栈

• 所谓清空一个栈，就是将栈中的元素全部作废，但栈本身物理空间并不发生改变（不是销毁）。
• 这里原理跟高级格式化只是单纯地清空文件列表而没有覆盖硬盘的原理是一样的。

ClearStack(sqStack* s)
{
	s->top = s->base;  //栈顶指针指向栈底，但原来的数据还是存在，但是我们看不到
}

销毁一个栈

• 销毁一个栈与清空一个栈不同，销毁一个栈是要释放掉该栈所占据的物理内存空间，因此不要把销毁一个栈和清空一个栈这两种操作混淆。

DestroyStack(sqStack* s)
{
	int i, len;
	len = s->stackSize;
	for (i = 0; i < len; i++)
	{
		free(s->base);  //利用栈底指针一个一个数据释放掉
		s->base++;
	}
	s->base = s->top = NULL;  //栈顶和栈底指针都指向NULL
	s->stackSize = 0;  //最后栈容量大小清零
}

计算栈的当前容量

• 计算栈的当前容量也就是计算栈中元素的个数，因此只要返回s->top - s->base即可。
• 注意，栈的最大容量是指该栈占据内存空间的大小，其值是s->stackSize，它与栈的当前容量不是一个概念。

int StackLen(sqStack *s)
{
    return (s->top-s->s->base);
}

实例分析

• 题目：利用栈的数据结构特点，将二进制转化为十进制数。

#include 
#include 
#include 
 
#define STACK_INIT_SIZE 20 //初始最大容量
#define STACKINCREMENT  10 //栈满时每次追加的容量
typedef char ElemType;
typedef struct  //定义一个栈结构
{
	ElemType* base;
	ElemType* top;
	int stackSize;
}sqStack;
/*初始化一个栈*/
void InitStack(sqStack* s)
{
	s->base = (ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));
	if (!s->base)
		exit(0);
	s->top = s->base;
	s->stackSize = STACK_INIT_SIZE;
}
/*压栈/入栈*/
void Push(sqStack* s, ElemType e)
{
	if (s->top - s->base >= s->stackSize)
	{
		s->base = (ElemType*)realloc(s->base,(s->stackSize+STACKINCREMENT)*sizeof(ElemType));
		if (!s->base)
			exit(0);
	}
	*(s->top) = e;
	s->top++;
}
/*出栈/弹栈*/
void Pop(sqStack* s, ElemType* e)
{
	if (s->top == s->base)
	{
		return;
	}
	*e = *--(s->top);
}
 
int StackLen(sqStack s)
{
	return (s.top - s.base);//指针相减不是将地址相减，而是将指针指向的元素他们之间的元素差 中间隔了多少个元素
}
int main()
{
	ElemType c;
	sqStack s;
	int len, i, sum = 0;
	InitStack(&s);
	printf("请输入二进制数，输入#符号表示结束！\n");
	scanf_s("%c",&c);
	while (c != '#')
	{
		Push(&s,c);
		scanf_s("%c",&c);
	}
	getchar();
	len = StackLen(s);
	printf("栈的当前容量是：%d\n",len);
	
	for (i = 0; i < len; i++)
	{
		Pop(&s,&c);
		sum = sum + (c - 48) * pow(2, i);
	}
	printf("转化为十进制数是：%d\n",sum);
 
	return 0;
}

运行结果：

 栈的链式存储结构

• 栈的链式存储结构，简称栈链。（通过我们用的都是栈的顺序存储结构存储，链式存储我们作为一个知识点，了解即可）
• 栈因为只是栈顶来做插入和删除操作，所以比较好的方法就是将栈顶放在单链表的头部，栈顶指针和单链表的头指针合二为一。

栈顶相当于单链表的表头，栈底相当于单链表的表尾。

typedef struct StackNode
{
	ElemType data; //存放栈的数据
	struct StackNode* next;
}StackNode,*LinkStackPtr;
 
typedef struct LinkStack
{
	LinkStackPtr top;//top指针
	int count;       //栈元素计数器
}LinkStack;

进栈操作

• 对于栈链的Push操作，假设元素值为e的新结点是s，top为栈顶指针，我们可以得到如下代码：

typedef struct StackNode
{
	ElemType data; //存放栈的数据
	struct StackNode* next;
}StackNode,*LinkStackPtr;
 
typedef struct LinkStack
{
	LinkStackPtr top;//top指针
	int count;       //栈元素计数器
}LinkStack;
 
Status Push(LinkStack* s, ElemType e)
{
	LinkStackPtr p = (LinkStackPtr)malloc(sizeof(StackNode));
	p->data = e;
	p->next = s->top;
	s->top = p;
	s->count++;
	return OK;
}

出栈操作

• 至于栈链的出栈Pop操作，假设变量p用来存储要删除的栈顶指针，将栈顶指针下移一位，最后释放p即可。

/*弹栈/出栈*/
Status Pop(LinkStack* s, ElemType* e)
{
	LinkStackPtr p;
	if (StackEmpty(*s)) //判断是否为空栈
		return ERROR;
	*s = s->top->data;
	p = s->top;
	s->top = s->top->next;
	free(p);
	s->count--;
	return OK;
}

注意：使用纸笔进行画图更有助于理清逻辑。

终极实践

逆波兰表达式

对于（1-2）*（4+5），如果用逆波兰表达法，应该是这样：1 2 - 4 5 + *

• 数字1和2进栈，遇到减号运算符则弹出两个元素进行运算并把结果入栈。
• 4和5入栈，遇到加号运算符，4和5弹出栈，相加后将结果9入栈。
• 然后又遇到乘法运算符，将9和-1弹出栈进行乘法计算，此时栈空并无数据压栈，-9为最终运算结果。

逆波兰计算器

• 实现对逆波兰输入的表达式进行计算。
• 支持带小数点的数据。
• 正常的表达式--->逆波兰表达式   
•  a+b--->a b +            a+(b-c)--->a b c - +       
•  a+(b-c)*d--->a b c - d * +

        正常的式子我们叫做中缀表达式，它方便人类的阅读计算，但计算机处理中序表达式（中缀表达式）非常复杂。计算机处理后缀表达式非常简便，因为计算机普遍采用的内存结构是栈式结构，遵循后入先出的原则。只需入栈和出栈两个操作就可以实现逆波兰表达式的计算。如果遇到数字就入栈，如果遇到符号就将栈顶的两个元素出栈并作相应的运算，之后将结果入栈，最终栈中剩下的那个数字就是最终结果。

代码：

#include
#include
#include
 
#define STACK_INIT_SIZE 20
#define STACK_DILA_SIZE 10
 
typedef double elemtype;
 
typedef struct
{
	elemtype * base;
	elemtype * top;
	int stacksize;
}sqstack;
 
void initstack(sqstack*s)
{
	s->base = (elemtype*)malloc(STACK_INIT_SIZE * sizeof(elemtype));
	if (!s->base)
	{
		exit(0);
	}
	s->top = s->base;
	s->stacksize = STACK_INIT_SIZE;
}
 
void push(sqstack*s, elemtype x)
{
	if (s->top - s->base >= s->stacksize)
	{
		s->base = (elemtype*)realloc(s->base, (STACK_DILA_SIZE + STACK_INIT_SIZE) * sizeof(elemtype));
		if (!s->base)
		{
			exit(0);
		}
		s->top = s->base + STACK_INIT_SIZE;
		s->stacksize += STACK_DILA_SIZE;
	}
	*(s->top) = x;
	s->top++;
}
 
void pop(sqstack*s, elemtype*x)
{
	if (s->base == s->top)
	{
		return;
	}
	s->top--;
	*x = *s->top;
}
 
int stacklen(sqstack*s)
{
	return (s->top - s->base);
}
 
int main()
{
	sqstack*s = (sqstack*)malloc(sizeof(sqstack));
	initstack(s);
	char c;
	char str[10] = { '0' };//设置输入单个数字的缓冲区
	int i = 0;
	elemtype a, b, x;
	scanf_s("%c", &c,sizeof(c));
	while (c != '#')
	{
		while (isdigit(c)||c=='.')//过滤数字
		{
			str[i]=c;
			i++;
			scanf_s("%c", &c, sizeof(c));
			if (c == ' ')
			{
				x = atof(str);//将字符型转为double型
				push(s, x);
				i = 0;
				break;
			}
		}
		switch (c)
		{
		case '+':
			pop(s, &a);
			pop(s, &b);
			push(s, a + b);
			break;
		case '-':
			pop(s, &a);
			pop(s, &b);
			push(s, b - a);
			break;
		case '*':
			pop(s, &a);
			pop(s, &b);
			push(s, a*b);
			break;
		case '/':
			pop(s, &a);
			pop(s, &b);
			push(s, b / a);
			break;
		}
		scanf_s("%c", &c, sizeof(c));
	}
	pop(s, &x);
	printf("%f", x);
 
	return 0;
}