栈的顺序存储实现（C语言）(数据结构与算法）

• 栈的顺序存储实现通常使用数组来完成。实现方法包括定义一个固定大小的数组，以及一个指向栈顶的指针。当元素入栈时，指针加一并将元素存储在相应位置；当元素出栈时，指针减一并返回相应位置的元素。

1. 顺序栈定义

#define MaxSize 10 	//定义栈中元素的最大个数
typedef struct
{ElemType data[MaxSize] 	//静态数组存放栈中元素int top;			//栈顶指针
}SqStack;//初始化栈
void InitStack(SqStack &S)
{S.top = -1;  //初始化栈顶指针
}//判断栈空
bool StackEmpty(SqStack S)
{if(S.top == 1) 	//栈空return true;else			//不空return false; 
}void testStack()
{SqStack S;		//声明一个顺序栈（分配空间）//.....后续操作......（增删改查）
}

1.1 进栈操作

#define MaxSize 10 	//定义栈中元素的最大个数
typedef struct
{ElemType data[MaxSize] 	//静态数组存放栈中元素int top;			//栈顶指针
}SqStack;//新元素入栈
bool Push(SqStack &S, ElemType x)
{if(S.top == MaxSize-1)  //栈满 报错  S.top = 9 栈满return false;//下面两句等价于：S.data[++S.top] = x;S.top = S.top+1;     //栈顶指针先+1 , 让指针从-1变为0S.data[S.top] = x;   //新元素入栈 return true;
}

1.2 出栈操作

#define MaxSize 10 	//定义栈中元素的最大个数
typedef struct
{ElemType data[MaxSize] 	//静态数组存放栈中元素int top;			//栈顶指针
}SqStack;//出栈操作
bool Pop(SqStack &S, ElemType &x)
{if(S.top = -1)		//栈空， 报错return false;x = S.data[S.top];   //栈顶元素先出栈， 存储在x中，然后栈顶指针下移一位S.top = S.top -1;	//指针减一，其实只是逻辑上被删除了，栈顶指针向下移动了一位而已return true;
}


1.3 读取栈顶元素

//出栈操作
bool Pop(SqStack &S, ElemType &x)
{if(S.top = -1)		//栈空， 报错return false;//以下两行，等价于x = S.data[S.top--];  //先出栈，指针再减一x = S.data[S.top];   //栈顶元素先出栈， 存储在x中，然后栈顶指针下移一位S.top = S.top -1;	//指针减一，其实只是逻辑上被删除了，栈顶指针向下移动了一位而已    与出栈操作的唯一区别return true;
}//读栈操作
bool GetTop(SqStack S, ELemType &x)
{if(S.top == -1)return false;x = S.data[S.top];  //x纪录栈顶元素  只是将此时top指针指向的数据元素，用x返回，并没有top--操作return true;
}

2. 另一种方式

让top刚开始指向 0，判断栈是否为空，就变成了看S.top是否为0

#define MaxSize 10 	//定义栈中元素的最大个数
typedef struct
{ElemType data[MaxSize] 	//静态数组存放栈中元素int top;			//栈顶指针
}SqStack;//初始化栈
void InitStack(SqStack &S)
{S.top = 0;		//初始化栈顶指针
}void testStck()
{SqStack S; //声明一个顺序栈 InitStack(S);//后续操作.......
}//判空操作
bool StackEmpty(SqStack S)
{if(S.top == 0)   //栈空 return true;else		//不空return false;
}