07、数据结构和算法 - 实战：栈和队列（1）

栈

定义

栈Stack是一种后进先出（LIFO) 的数据结构，是线性表的一种具体形式，要求只在表尾进行删除pop和插入push的操作。
插入操作：push，进栈。
删除操作：pop，出栈

顺序存储结构

顺序存储结构：最开始栈中不含有任何数据，叫做空栈，此时栈顶就是栈底。数据从栈顶进入，容量变大，数据出栈时从栈顶弹出，整个栈的容量变小。

栈的代码定义

typedef int ElemType;
typedef struct
{
   
     
	ElemType *base; //指向栈底
	ElemType *top;  //指向栈顶
	int stackSize;
}sqStack;

创建一个栈

#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;
}

入栈操作

#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 ++;
}

出栈操作

在栈顶取出数据，栈顶指针随之下移，容量–

Pop(sqStack *s, ElemType e)
{
   
     
	//判断是否为空栈
	if(s->top == s->base )
		return;
	*e = * --(s->top);//先减一再取出内容
}

清空栈

将栈的元素作废，但是本身物理空间并不发生改变。
将s->top的内容赋值为s->basw，表明为空，类似于格式化只是单纯的清空文件列表但是没有覆盖硬盘的道理。
代码也十分简单

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;
	s->stackSize = 0;
}

计算栈的当前容量

只需要计算元素的个数
注意：在这里，栈的当前容量与最大容量stackSize不同，并不是一个概念.

int StackLen(sqStack s)
{
   
     
	//两个地址相减得到的是元素（要除以地址的大小）
	return (s.top - s.base);
}

例题

利用栈的数据结构特点，将二进制转换为十进制数
提示：转换公式为
XnXn-1…X3X2X1 = X1 *20 + X2 *21 + … + Xn *2(n-1)

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

#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;
}

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 ++;
}

Pop(sqStack *s, ElemType e)
{
   
     
	//判断是否为空栈
	if(s->top == s->base )
		return;
	*e = * --(s->top);//先减一再取出内容
	s->stackSize --;
}

int StackLen(sqStack s)
{
   
     
	//两个地址相减得到的是元素（要除以地址的大小）
	return (s.top - s.base);
}

int main()
{
   
     
	ElemType c;
	sqStack s;
	int len, i ,sum = 0;
	printf("请输入二进制数，（#结束）:\n");
	scanf("%c",&c);
	while( c!= '#')
	{
   
     
		Push( &s,c);
		scanf("%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;
	int count; //栈元素计数器
};

进栈操作

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;
}

出栈操作

Status Pop(LinkStack * s, ElemType e)
{
   
     
	LinkStackPtr p;
	if(StackEmpty(*s))
		return false;
	*e = 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进栈，遇到-弹出，运算之后进去，变成-1。之后4和5进去，遇到+弹出来计算，变成9放进去。之后又是×，弹出-1和9，计算之后为-9。-9为最终计算结果。