栈的基本概念

栈（Stack）：是只允许在一端进行插入或删除操作的线性表。

栈顶（Top）：线性表允许进行插入和删除的那一端。
栈底（Bottom）：固定的，不允许进行插入和删除的另一端。
空栈：不含任何元素的空表。

栈的实现

顺序栈的实现

顺序栈：利用数组存放自栈底到栈顶的数据元素，并设top指针指向当前栈顶元素的位置。

// 顺序栈的实现
#define MaxSize 50      //定义栈中元素的最大个数
typedef int ElemType;	//typedef：类型重命名

typedef struct{
	ElemType data[MaxSize];		//存放栈中元素
	int top;					//栈顶指针
}SeqStack;


// 初始化栈
void InitStack(SeqStack& s)
{
	s.top = -1;		//初始化栈顶指针
	//s.top=0;		//初始化栈顶指针指向栈底第一个位置
}

// 判空
bool StackEmpty(SeqStack& s)
{
	//若定义s.top=0;则栈空的条件：s.top==0; 
	if (s.top == -1)		//栈空
		return true;
	else
		return false;		//不空
}

// 进栈
bool PushStack(SeqStack& s, ElemType x)
{
	// 若定义s.top=0;则栈满的条件:top==MaxSize
	if (s.top == MaxSize - 1)	//栈满，报错
		return false;
		
	// 若定义s.top=0; 则s.data[s.top++]=x;
	s.data[++s.top] = x;	//	指针先加1，再入栈

	return true;
}

// 出栈
bool PopStack(SeqStack& s, ElemType& x)
{
	//若定义s.top=0;则栈空的条件：s.top==0;
	if (s.top == -1)	//栈空，报错
		return false;
	
	// 若定义s.top=0;则x=s.data[--s.top];
	x = s.data[s.top--];	//先出栈，再指针减1

	return true;
}

// 读取栈顶元素
bool GetTop(SeqStack& s, ElemType& x)
{
	//若定义s.top=0;则栈空的条件：s.top==0;
	if (s.top == -1)	//栈空，报错
		return false;
		
	x = s.data[s.top];	//x记录栈顶元素
	return true;
}

链栈的实现（不带头结点）

链栈：采用单链表存储，所有操作在单链表的表头进行。

// 链栈的实现(不带头结点)
typedef int ElemType;
typedef struct LinkNode{
	ElemType data;			//数据域
	struct LinkNode* next;	//指针域
}*LinkStack;

// 初始化
bool InitStack(LinkStack& s)
{
	s = NULL;	//空表，防止脏数据
	return true;
}

// 判空
bool StackEmpty(LinkStack& s)
{
	return (s == NULL);
}

// 入栈(头插法)
bool PushStack(LinkStack& s, ElemType x)
{
	LinkNode* newnode = (LinkNode*)malloc(sizeof(LinkNode));
	if (newnode == NULL)	//内存分配失败
		return false;

	newnode->data = x;
	newnode->next = s;	//前插节点
	
	s = newnode;	//s指向新节点
	return true;
}

// 出栈(头删法)
bool PopStack(LinkStack& s, ElemType& x)
{
	if (s == NULL)	//栈空，报错
		return false;

	x = s->data;	//x记录栈顶元素

	LinkNode* p=s;
	s = s->next;
	free(p):	//释放栈顶节点

	return true;
}

// 读取栈顶元素
bool GetTop(LinkStack& s, ElemType& x)
{
	if (s == NULL)	//栈空，报错
		return false;

	x = s->data;
	return true;
}

链栈的实现（带头节点）

// 链栈的实现（带头节点）
typedef int ElemType;
typedef struct LinkNode{
	ElemType data;			//数据域
	struct LinkNode* next;	//指针域
}*LinkStack;

// 初始化栈（带头结点）
bool InitStack(LinkStack& s)
{
	s = (LinkNode*)malloc(sizeof(LinkNode));
	if (s == NULL)	//内存不足，分配失败
		return false;

	s->next = NULL;	//头结点之后暂时没有节点
	return true;
}

// 判空
bool StackEmpty(LinkStack& s)
{
	return (s->next == NULL);
}

// 入栈（头插法）
bool PushStack(LinkStack& s, ElemType x)
{
	LinkNode* newnode = (LinkNode*)malloc(sizeof(LinkNode));
	if (newnode == NULL)	//内存分配失败
		return false;

	newnode->data = x;

	newnode->next = s->next;	//新节点插入到头结点之后
	s->next = newnode;

	return true;
}

// 出栈（头删法）
bool PopStack(LinkStack& s, ElemType& x)
{
	if (s->next == NULL)	//栈空，报错
		return false;

	x = s->next->data;	//x记录栈顶元素

	LinkNode* p = s->next;	//p指向栈顶节点
	s->next = p->next;		
	free(p);	//释放栈顶元素

	return true;
}

// 读取栈顶元素
bool GetTop(LinkStack& s, ElemType& x)
{
	if (s->next == NULL)	//栈空，报错
		return false;

	x = s->next->data;	//x记录栈顶元素
	return true;
}