目录

一、栈的基本概念

1.定义

2.几个重要术语

二、顺序栈的表示

三 、顺序栈的基本操作

1.栈的初始化操作

2.栈的判空操作

3.进栈操作

4.出栈操作

5.取栈顶元素

一、栈的基本概念

1.定义

栈是一种只允许在一端进行插入和删除的特殊线性表。

2.几个重要术语

①栈顶：表中允许进行插入、删除操作的一端叫做栈顶
②栈底：固定的，不允许进行插入和删除的另一端
③空栈：不任何元素
④栈的操作特性：先进后出(FILO)
⑤栈的数学性质：n个不同元素进栈，出栈元素不同排列的个数为1/(n+1)*C2n(n)--卡特兰数(Catalan) 

二、顺序栈的表示

typedef int ElemType;
#define MaxSize 50            //定义栈中元素的最大个数
typedef struct {
	ElemType  data[MaxSize];  //存放栈中的元素
	int top;                  //栈顶指针
}SqStack;

三 、顺序栈的基本操作

栈空条件：pastack.top == -1;
栈满条件：pastack.top == MaxSize-1;
栈的长度：pastack.top+1;

1.栈的初始化操作

void InitStack(SqStack* pastack)
{
	pastack->top = -1; //初始化栈顶指针
}

2.栈的判空操作

bool EmptyStack(SqStack pastack)
{
	if (pastack.top = -1)  //栈空
	{
		return true;
	}
	else
		return false;     //栈不空
}

3.进栈操作

bool Push(SqStack* pastack, ElemType e)
{
	if (pastack->top == MaxSize - 1)   //栈满，报错
	{
		return false;
	}
	pastack->top++;                    //栈顶指针加1
	pastack->data[pastack->top] = e;   //元素进栈
	return true;
}

4.出栈操作

bool Pop(SqStack* pastack, ElemType* e)
{
	if (pastack->top == -1)            //栈空，报错
	{
		return false;
	}
	*e = pastack->data[pastack->top]; //将栈顶元素赋个e
	pastack->top--;                   //栈顶指针减一
	return true;
}

5.取栈顶元素

bool GetTopElem(SqStack pastack, ElemType* e)
{
	if (pastack.top == -1)            //栈空，报错
	{
		return false;
	}
	*e = pastack.data[pastack.top];   //将栈顶元素赋给e
	return true;
}

A soul without imagination is like an observatory without a telescope.