• 整理数据结构学习笔记
• 基于C++

---

一、栈的相关定义

• 栈(stack)：是限定仅在表尾进行插入或删除操作的线性表。
• 栈顶(top)：栈的表尾元素
• 栈底(bottom)：栈的表头元素
• 空栈：不含元素的空表
• 入栈（push）：在线性表尾部（栈顶）后新增一个元素
• 出栈（pop）：把线性表尾部（栈顶）的元素取出并从表中删除
• 可见，最后入栈的元素最先出栈，这种特性称为后进先出（LIFO）
  

二、栈的表示和实现

1、链式栈

（1）定义

链式栈是使用单链表结构实现的栈，其操作是单链表操作的特例，在此不加赘述。结构示意如下

2、顺序栈

（1）定义

• 顺序栈利用一组连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top和bottom指示栈顶和栈底的位置。
• 由于栈的大小不确定，通常使用动态申请数组来实现顺序栈
• 注意*top指针这里要指向真正栈顶的再上一个元素，这样处理比较方便，空栈判据为top==base
  

（2）数据结构

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

typedef struct
{
	int *base;//指向最下面元素 
	int *top;//指向真正顶部再上一个 
	int stacksize;
}SqStack;

（3）基本操作

1、初始化栈 bool InitStack(SqStack &s)

• 申请空间，设置stacksize
• 令top=base（空栈判据）

//1 初始化
bool InitStack(SqStack &s)
{
	s.base = (int *)malloc(STACK_INIT_SIZE*sizeof(int));
	if(!s.base)
		exit(OVERFLOW);		
	s.top=s.base;
	s.stacksize=STACK_INIT_SIZE;
	return OK;
}

2、销毁栈 bool DestroyStack(SqStack &s)

• 释放空间
• top、base指针设NULL

//2 销毁栈
bool DestroyStack(SqStack &s)
{
	s.top=NULL;
	free(s.base);
	s.base=NULL;
	s.stacksize=0;
	return OK;
}

3、置空 bool ClearStack(SqStack &s)

• top=base
• 不需要释放空间，也不用对原有的栈中数据做任何操作

//3 置空
bool ClearStack(SqStack &s)
{
	s.top=s.base;
	return OK;
}

4、判空 bool StackEmpty(SqStack s)

• 判断top和base是否相等

//4 判空
bool StackEmpty(SqStack s)
{
	if(s.top==s.base)
		return true;
	else
		return false;
}

5、返回栈长度 int StackLength(SqStack s)

• length=top-base

//5 栈长度
int StackLength(SqStack s)
{
	return s.top-s.base;
}

6、栈顶元素 bool GetTop(SqStack s,int &e)

• 判断不是空栈
• 取top位置上一个元素

//6 栈顶元素
bool GetTop(SqStack s,int &e)
{
	if(StackEmpty(s))
		return ERROR;
	e=*(s.top-1);
	return OK;
}

7、入栈 bool push(SqStack &s,int e)

• 先判断空间是否足够，若不够要动态申请
• top位置赋值入栈的元素，后移top指针

//7 入栈
bool push(SqStack &s,int e)
{
	if(s.top-s.base>=s.stacksize)
	{
		s.base=(int *)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(int));
		if(!s.base)
			exit(OVERFLOW);	
		
		s.top=s.base+s.stacksize;
		s.stacksize+=STACKINCREMENT;	
	}
	
	*s.top=e;
	s.top++; 
	return OK;
}

8、出栈 bool pop(SqStack &s,int &e)

• 先判断栈非空
• 取栈顶元素，移动top指针

//8 出栈
bool pop(SqStack &s,int &e)
{
	if(s.top==s.base)
		return ERROR;
	e=*(s.top-1);
	s.top--;
	return OK;
}

9、遍历栈 bool StackTraverse(SqStack s,bool (*visit)(int a))

//9 遍历栈
bool StackTraverse(SqStack s,bool (*visit)(int a))
{
	for(int *p=s.base;p<s.top;p++)
		if(visit(*p)==ERROR)
			return ERROR;
	return OK;
	
}

bool Visit(int a)
{
	cout<<a<<" ";
	return OK;
}