顺序栈的基本操作C/C++代码实现

客官°小女子只卖身不卖艺 2023-02-14 13:29 146阅读 0赞

## 顺序栈结构： ##

![在这里插入图片描述][2020060311294156.png]  
设顺序栈为S,需要注意的如下：

## 入栈： ##

栈满时 S.top-S.base==S.stacksize

## 出栈： ##

栈空时 S.top == S.base

## 取栈顶元素： ##

\++会改变自身值，而-1不会改变，故返回\*(S.top-1);

## 顺序栈特点： ##

由于顺序栈和顺序表一样， 受到最大空间容量的限制， 虽然可以在 “满员” 时重新分配空间扩大容量， 但工作量较大，因此在应用程序无法预先估计栈可能达到的最大容量时，应该尽量避免使用顺序栈。

## 代码如下： ##

#include<stdio.h>
    #include<stdlib.h>
    
    #define MAXSIZE 100
    typedef int SElemType;
    
    //顺序栈的存储结构
    typedef struct
    {
        
    	SElemType *base;
    	SElemType *top;
    	int stacksize;			//可用最大容量
    }SqStack;
    
    //初始化
    void InitStack(SqStack &S)
    {
        
    	S.base = new SElemType[MAXSIZE];
    	if (!S.base) exit;	
    	S.top = S.base;
    	S.stacksize = MAXSIZE;
    }
    
    //入栈
    int Push(SqStack &S, SElemType e)
    {
        
    	if (S.top - S.base == S.stacksize) return 0;	//栈满
    
    	*S.top = e;
    	S.top++;
    	return 1;
    }
    
    //出栈
    int Pop(SqStack &S, SElemType &e)
    {
        
    	if (S.top == S.base) return 0;    //栈空
    
    	S.top--;
    	e = *S.top;
    	return 1;
    }
    
    //取栈顶元素
    SElemType GetTop(SqStack S)
    {
        
    	if (S.top != S.base)	 //非栈空时返回
    		return *(S.top-1);   //++会改变指针自身值，而-1不会改变
    }
    
    //遍历输出栈
    void printStack(SqStack S)
    {
        
    	printf("栈底：");
    	SElemType *p = S.base;
    	while (p!=S.top)
    	{
        
    		printf("%d ", *p);
    		p++;
    	}
    	printf("\n");
    }
    
    int main()
    {
        
    	SqStack S;
    	int e;
    	InitStack(S);
    	printf("请输入一个要入栈的元素（-1表示结束）：");
    	scanf("%d",&e);
    	while (e!=-1)
    	{
        
    		Push(S,e);
    		printf("请输入一个要入栈的元素（-1表示结束）：");
    		scanf("%d", &e);
    	}
    	printStack(S);
    	printf("出栈测试：");
    	Pop(S, e);
    	printStack(S);
    
    	printf("取栈顶元素测试：");
    	e=GetTop(S);
    	printf("取出的栈顶元素为：%d\n",e);
    }

## 运行结果： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]

[2020060311294156.png]: https://img-blog.csdnimg.cn/2020060311294156.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200603113821290.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70