栈的顺序存储结构-蒲公英云

栈的顺序存储结构

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

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

一、结构

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

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

Center

二、栈顺序存储进栈操作

算法思路：

检查是否是满栈，如果满栈返回；
将数据元素加入栈顶；
栈顶位置计数加一；

三、栈顺序存储出栈操作

算法思路：

检查是否是空栈，空栈则返回；
获取栈顶元素，删除；
栈顶位置减一；

四、时间复杂度

没有任何循环，时间复杂度都是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;
}