顺序栈

顺序栈是利用一组地址连续的存储单元依次存放数据元素从栈底到栈顶，栈底位置固定不变，栈顶位置随着入栈和出栈操作而变化，类似于一维数组，那既然是数组，我们就既可以用下标，也可以用指针来操作它

*对顺序栈，我们要实现的操作有:

1 .顺序栈的初始化 Initstack，

2 .顺序栈的入栈(压栈) Push，

3 .顺序栈的出栈(弹栈) Pop,

4 .取栈顶元素GetTop *
1. 数值下标
#include <iostream>
using namespace std;

#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MAXSIZE 100

typedef int Status;
typedef int SElemtype;

既然要用数组下标，那我们就直接在栈中声明一个数组
typedef struct {
 SElemtype elem[MAXSIZE]; //存放栈元素的数组 
 SElemtype top;  //存放栈顶元素的下标 
 int stacksize;  //栈的长度 
}SqStack; 

1.栈的初始化:
Status Initstack(SqStack &s){
 s.top = -1;    //栈的初始化,如果栈顶指针 top 等于-1 则栈为空栈
 s.stacksize = MAXSIZE;  //stacksize置为栈的最大容量MAXSIZE 
 return OK;
}

栈中，当top等于-1时，则该栈就是空栈，所以初始化栈时，我们直接把top=-1即可
2.栈的压栈
Status Push(SqStack &s , SElemtype e){
 if(s.top == s.stacksize - 1)
  return ERROR; //栈满 
 s.elem[s.top++] = e;  //将元素e压入栈，top下移 
 return OK;
}


压栈时，首先验证栈是否满了，如果栈满则无法压栈。

当下标top等于stacksize-1时则栈满，
3.弹栈
Status Pop(SqStack &s, SElemtype &e){
 if(s.top == -1)
  return ERROR; //栈空
 e = s.elem[--s.top];  //top指针下移，将值赋给e
 return OK; 
}

弹栈时需注意的是，如果栈为空，那么你弹栈就会发生错误,所以需先判断栈是否为空
4.获取栈顶元素
SElemtype GetTop(SqStack &s){
 if(s.top != -1) //非空 
  return s.elem[s.top - 1]; //获取栈顶元素 
}

获取栈顶元素同样需要判断栈是否为空，如果栈为空，那么你获取的栈顶元素就不是你需要的，也是无意义的
数组下标介绍完了，那就在看下指针操作吧，读者在看的时候，只需理解其一就行，因为两种方法的思路是一样的，只是代码不同

用指针
同样，头文件，宏定义，取别名与上面的一样,那就直接看实现函数吧
typedef struct {
 SElemtype *base; //栈底指针  
 SElemtype *top;  //栈顶指针 
 int stacksize;  //栈的长度 
}SqStack;

1.初始化
Status Initstack(SqStack &s){
 s.base = new SElemtype[MAXSIZE];  //为顺序栈动态分配最大容量为MAXSIZE的数组空间
 if(!s.base)
  exit(OVERFLOW);    //存储空间分配失败 
 s.top = s.base;       //top初始化为base，此时为空栈 
 s.stacksize = MAXSIZE;  //stacksize置为栈的最大容量MAXSIZE 
 return OK;
}  

这里是用指针base开辟空间，作用与数组是一样的
2.压栈
Status Push(SqStack &s , SElemtype e){
 if(s.top - s.base == s.stacksize)
  return ERROR;  //栈满
 *(s.top++) = e;    //将原素e压入栈底，top上移
 return OK; 
}

这里判断栈满的用法是，两个指针的差值是否等于s.stacksize，

*(s.top++) = e;其实就是

*(s.top) = e;

s.top = s.top++;
3.弹栈
Status Pop(SqStack &s, SElemtype &e){
 if(s.base == s.top)
  return ERROR;  //栈空
 e = *(--s.top); //top指针下移，将值赋给e   
 return OK;
} 

这里判断栈是否为空看着有些奇怪，如果不明白就看初始化函数中 s.top = s.base; 这句，相信聪明的你已经明白了
4.去栈顶元素
SElemtype GetTop(SqStack &s){
 if(s.top != s.base)  //栈非空 
  return *(s.top - 1); //返回栈顶元素，不修改top指针 
}

这个注释就很明白了
下面看一些测试结果

当然这里是用int型数据测试的，读者也可以把 typedef int SElemtype;中的int修改为其他类型测试一下

栈——顺序栈
栈的定义
栈的表示和实现
顺序栈的定义
顺序栈的模块说明
栈基本操作部分算法描述

栈的定义
栈：是限定仅在表尾进行插入和删除操作的线性表，又称为后进先出的线性表（简称LIFO结构）。

栈顶：线性表的表尾。

栈底：线性表的表头。

空栈：不含元素的栈。
栈的表示和实现
和线性表类似，栈也有两种存储表示方法：顺序栈和链栈。
顺序栈：栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，通常附设指针top指示栈顶元素在顺序栈中的位置。
顺序栈的定义
typedef struct{
	SElemType *base;	//栈底指针
	SElemType *top;		//栈顶指针
	int stacksize;		//栈的最大容量
}SqStack;

顺序栈的模块说明
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

typedef struct{
    int *base;
    int *top;
    int stacksize;
}SqStack;

Status InitStack(SqStack &S);				//构造一个空栈S
Status DestroyStack(SqStack &S);			//销毁栈S
Status ClearStack(SqStack &S);				//清除栈S
Status StackEmpty(SqStack S);				//若栈S为空栈，则返回TRUE，否则返回FALSE
int StackLength(SqStack S);					//返回栈S的长度
Status GetTop(SqStack S, SElemType &e);		//若栈S不为空，则用e返回S的栈顶元素，并返回OK，否则返回ERROR
Status Push(SqStack &S, SElemType e);		//插入元素e为新的栈顶元素
Status Pop(SqStack &S, SElemType &e);		//若栈S不为空，弹出栈顶元素，用e返回，并返回OK，否则返回ERROR
Status StackTraverse(SqStack S, Status (*visit)());		//从栈底到栈顶依次对栈中每一个元素调用visit()。一旦visit()失败，则操作失败

栈基本操作部分算法描述
Status InitStack(SqStack &S){
//构造一个空栈S
    S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
    if(!S.base)
        exit(OVERFLOW);
    S.top = S.base;
    S.stacksize = STACK_INIT_SIZE;
    return OK;
}

Status GetTop(SqStack S, SElemType e){
//若栈S不为空，则用e返回S的栈顶元素，并返回OK，否则返回ERROR
	if(S.top == S.base)
		return ERROR;
	e = *(S.top - 1);
	return OK;
}

Status Push(SqStack &S, SElemType e){
//插入元素e为新的栈顶元素
    if(S.top - S.base >= S.stacksize){
        S.base = (SElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType));
        if(!S.base)
            exit(OVERFLOW);
            
        S.top = S.base + S.stacksize;
        S.stacksize += STACKINCREMENT;
    }
    *S.top++ = e;
    return OK;
}

Status Pop(SqStack &S, SElemType &e){
//若栈S不为空，弹出栈顶元素，用e返回，并返回OK，否则返回ERROR
    if(S.top == S.base)
        return ERROR;
    e = * --S.top;
    return OK;
}

Status StackEmpty(SqStack S){
//若栈S为空栈，则返回TRUE，否则返回FALSE
	if(S.top == S.base)
		return TRUE;
	return FALSE;
}

主要操作函数如下：

    InitStack(SqStack &s) 参数：顺序栈s 功能：初始化  时间复杂度O(1)
	
    Push(SqStack &s,SElemType e) 参数：顺序栈s,元素e 功能：将e入栈 时间复杂度:O(1)
	
    Pop(SqStack &s,SElemType &e) 参数：顺序栈s,元素e 功能：出栈,e接收出栈元素值 时间复杂度O(1)
	
    GetTop(SqStack s,SElemType &e) 参数：顺序栈s,元素e 功能：得到栈顶元素 时间复杂度O(1)
	
    注意：严蔚敏版没有判断栈空函数，在入栈、出栈函数里面判断栈是否空，与王道的不同 尤其是top指针在base之上(有元素时）另外，严蔚敏版 59页取栈顶有误
	
/*
    Project: sequence_stack (数据结构-顺序栈)
    Date:    2018/09/14
    Author:  Frank Yu
	InitStack(SqStack &s) 参数：顺序栈s 功能：初始化  时间复杂度O(1)
	Push(SqStack &s,SElemType e) 参数：顺序栈s,元素e 功能：将e入栈 时间复杂度:O(1)
	Pop(SqStack &s,SElemType &e) 参数：顺序栈s,元素e 功能：出栈,e接收出栈元素值 时间复杂度O(1)
	GetTop(SqStack s,SElemType &e) 参数：顺序栈s,元素e 功能：得到栈顶元素 时间复杂度O(1)
	注意：严蔚敏版没有判断栈空函数，在入栈、出栈函数里面判断栈是否空，与王道的不同 尤其是top指针在base之上(有元素时)
	      另外，严蔚敏版 59页取栈顶有误
	
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
#define Status int
#define SElemType int
#define MaxSize 100
//栈数据结构
typedef struct Stack
{
	SElemType *base;//栈底指针 不变
	SElemType *top;//栈顶指针 一直在栈顶元素上一个位置
	int stacksize;//栈可用的最大容量
}SqStack;
//**************************************基本操作函数************************************//
//初始化函数
Status InitStack(SqStack &s)
{
	s.base=new SElemType[MaxSize];//动态分配最大容量
	if(!s.base)
	{
		printf("分配失败\n");
		return 0;
	}
	s.top=s.base;//栈顶指针与栈底相同 王道上top起初在base下面，感觉很别扭，top应该高于或等于base
	s.stacksize=MaxSize;
	return 1;
}
//入栈
Status Push(SqStack &s,SElemType e)
{
	if(s.top-s.base==s.stacksize) return 0;//栈满
	*(s.top++)=e;//先入栈，栈顶指针再上移 注意与王道上的不同，具体问题具体分析
	return 1;	
}
//出栈 用e返回值
Status Pop(SqStack &s,SElemType &e)
{
	if(s.top==s.base) return 0;//栈空
	e=*--s.top;//先减减 指向栈顶元素，再给e
	return 1;	
}
//得到栈顶元素，不修改指针
bool GetTop(SqStack s,SElemType &e) //严蔚敏版59页有问题，应该用e去获得，函数返回bool类型去判断
{
	if(s.top==s.base) return false;//栈空			
	else e=*--s.top;
	return true;
		
}
//********************************功能实现函数**************************************//
//菜单
void menu()
{
   printf("********1.入栈      2.出栈*********\n");
   printf("********3.取栈顶    4.退出*********\n");
}
//入栈功能函数 调用Push函数
void PushToStack(SqStack &s)
{
	int n;SElemType e;int flag;
	printf("请输入入栈元素个数(>=1)：\n");
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
	 printf("请输入第%d个元素的值:",i+1);
	 scanf("%d",&e);
	 flag=Push(s,e);
	 if(flag)printf("%d已入栈\n",e);
	 else {printf("栈已满！！！\n");break;}
	}
}
//出栈功能函数 调用Pop函数
void PopFromStack(SqStack &s)
{
	int n;SElemType e;int flag;
	printf("请输入出栈元素个数(>=1)：\n");
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
	 flag=Pop(s,e);
	 if(flag)printf("%d已出栈\n",e);
	 else {printf("栈已空！！！\n");break;}
	}
}
//取栈顶功能函数 调用GetTop
void GetTopOfStack(SqStack &s)
{
	SElemType e;bool flag; 
	flag=GetTop(s,e);
	if(flag)printf("栈顶元素为:%d\n",e);
	else printf("栈已空！！！\n");
}
//主函数
int main()
{
 SqStack s;int choice;
 InitStack(s);
 while(1)
 {
  menu();
  printf("请输入菜单序号：\n");
  scanf("%d",&choice);
  if(choice==4) break;
  switch(choice)
  {
  case 1:PushToStack(s);break;
  case 2:PopFromStack(s);break;
  case 3:GetTopOfStack(s);break;
  default:printf("输入错误！！！\n");
  }
 }
 return 0;
}


	

	


	
----------------------------------------回复lena512.bmp（20200427）------------------------------------
	



 从图中可以看到地址及地址内存的数据。

------------------------------------------取栈顶的统一回复(20200920)-------------------------------------

传参有多种，可分为参数修改后对原变量进行修改和不修改。对于需要修改的，我们可以使用&或指针，对参数的修改会反应到原来的变量；对于不需要修改的，你可以继续使用&或指针，不做修改那很好，做了修改但是没有回溯(即忘记再反操作回原来的数值)那就不好了，为了防止自己忘记回溯，博主对于get、print等获取数据而不修改的函数使用传值方式，你可以去查看下方专栏的图相关内容，对于图的建立，传参是&G，而遍历则是G。

建议您先复制代码运行一下，没有问题再思考原理，出了问题再评论，好记性不如烂笔头，动手才是王道！

本人b站账号:lady_killer9

更多数据结构实现：数据结构严蔚敏版的实现（含全部代码）

有问题请下方评论，转载请注明出处，并附有原文链接，谢谢！如有侵权，请及时联系。如果您感觉有所收获，自愿打赏，可选择支付宝18833895206（小于），您的支持是我不断更新的动力。