栈的顺序存储结构

小灰灰 2022-06-15 10:49 178阅读 0赞

栈的顺序存储是将数组下标为0的一端作为栈底。

**一、结构**

#define MAXSIZE 20//存储空间初始化分配量
    typedef int SElemType;//此处可能是个结构体，练习使用int型足够了
    typedef struct
    {
             SElemType data[MAXSIZE];//数组存储数据元素，最大存储量MAXSIZE
             int top;//用于栈顶指针
    }SqStack;

示例：若现有一个栈，StackSize是5，则普通情况、空栈和满栈的情况如下图所示

![Center][]

**二、栈顺序存储进栈操作**

**![Center 1][]**

**算法思路：**

1.      检查是否是满栈，如果满栈返回；

2.      将数据元素加入栈顶；

3.      栈顶位置计数加一；

**三、栈顺序存储出栈操作**

**算法思路：**

1.      检查是否是空栈，空栈则返回；

2.      获取栈顶元素，删除；

3.      栈顶位置减一；

**四、时间复杂度**

没有任何循环，时间复杂度都是O(1)。

**五、代码示例**

#include <stdio.h>
    #include <string.h>
    
    #define ERROR -1
    #define OK 0
    
    #define MAXSIZE 20//存储空间初始化分配量
    typedef int SElemType;//此处可能是个结构体，练习使用int型足够了
    typedef struct
    {
    	SElemType data[MAXSIZE];//数组存储数据元素，最大存储量MAXSIZE
    	int top;//用于栈顶指针
    }SqStack;
    
    //初始化操作，建立一个空栈S
    void InitStack(SqStack *S);
    //若栈存在，则销毁它,因为是数组，置成空栈即可
    int DestroyStack(SqStack *S);
    //将栈清空
    void ClearStack(SqStack *S);
    //若栈为空，返回true，否则返回false
    int StackEmpty(SqStack S);
    //若栈存在且非空，用e返回S的栈顶元素
    int GetTop(SqStackS,SElemType *e);
    //若栈存在，插入新元素e到栈S中并成为栈顶元素
    int Push(SqStack *S,SElemType e);
    //删除S中栈顶元素，并用e返回其值
    int Pop(SqStack *S,SElemType *e);
    //返回栈S的元素个数
    int StackLength(SqStack S);
    //打印栈
    int StackPrint(SqStack S);
    
    
    //初始化操作，建立一个空栈S
    void InitStack(SqStack *S)
    {
    	memset(S,0,sizeof(SqStack));
    	S->top = -1;//置成空栈
    }
    //若栈存在，则销毁它,因为是数组，置成空栈即可
    int DestroyStack(SqStack *S)
    {
    	if(S->top == -1)
    	{
    		return ERROR;
    	}
    	InitStack(S);
    	return OK;
    }
    
    //将栈清空
    void ClearStack(SqStack *S)
    {
    	InitStack(S);
    }
    
    //若栈为空，返回true，否则返回false
    int StackEmpty(SqStack S)
    {
    	if(S.top == -1)
    	{
    		return ERROR;
    	}
    	return OK;
    }
    
    //若栈存在且非空，用e返回S的栈顶元素
    int GetTop(SqStackS,SElemType *e)
    {
    	if(S.top == -1)
    	{
    		return ERROR;
    	}
    	*e = S.data[S.top];
    	return OK;
    }
    
    
    //若栈存在，插入新元素e到栈S中并成为栈顶元素
    int Push(SqStack *S,SElemType e)
    {
    	if(S->top == MAXSIZE - 1)//栈满
    	{
    		return ERROR;
    	}
    	S->top++;//栈顶指针加一
    	S->data[S->top] = e;//将新元素压栈
    	return OK;
    }
    
    //删除S中栈顶元素，并用e返回其值
    int Pop(SqStack *S,SElemType *e)
    {
    	if(S->top == -1)
    	{
    		return ERROR;
    	}
    	*e = S->data[S->top];//将要删除的栈顶元素赋值给e
    	S->top--;//栈顶指针减一
    	return OK;
    }
    
    //返回栈S的元素个数
    int StackLength(SqStack S)
    {
    	return S.top+1;//加一的原因是计数从0开始的
    }
    
    //打印栈
    int StackPrint(SqStack S)
    {
    	if(S.top == -1)
    	{
    		return ERROR;
    	}
    	while(S.top != -1)
    	{
    		printf("位置:%d 元素:%d\n",S.top,S.data[S.top]);
    		S.top--;
    	}
    	return OK;
    }
    
    int main()
    {
    inti = 0;
    	SElemType e = 0;
    SqStack S;
    	printf("\n=======初始化操作=========\n");
    InitStack(&S);
    	printf("\n=======是否为空栈=========\n");
    	if(ERROR == StackEmpty(S))//空栈
    	{
    		printf("空栈插入元素\n");
    		for(i = 1;i< 10;i++)
    		{
    			Push(&S,i);
    		}
    	}
    	printf("\n======打印栈信息=========\n");
    	StackPrint(S);
    
    	printf("\n=======获取栈长度========\n");
    	printf("栈长度:%d\n",StackLength(S));
    	printf("\n=====获取栈顶元素========\n");
    	GetTop(S,&e);
    	printf("栈顶元素:%d\n",e);
    
    	printf("\n=====删除栈顶元素========\n");
    	Pop(&S,&e);
    	printf("删除栈顶元素:%d\n",e);
    	printf("\n======打印栈信息=========\n");
    	StackPrint(S);
    
    	printf("\n=====清空并销毁栈========\n");
    	ClearStack(&S);
    	DestroyStack(&S);
    	if(ERROR == StackEmpty(S))//空栈
    	{
    		printf("空栈\n");
    	}
    return 0;
    }

[Center]: /images/20220615/55b38e5d79754af9a400dec26d370b61.png
[Center 1]: /images/20220615/afe983108b9d470d984cb94c9f451b60.png