【数据结构】栈

小王不头秃

发布于 2024-06-19 15:25:47

1640

发布于 2024-06-19 15:25:47

栈

定义

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

顺序栈

概括

设计的栈结构中包括数据数组以及top坐标，这里top指向的栈顶元素的位置，初始top为-1，代表栈为空

数据结构

typedef struct{
     int data[MAXSIZE];
     //采用top指针指向栈顶元素的方式 初始为-1
     int top;
} MStack;

初始化栈

//初始化栈
void initStack(MStack *mStack){
    mStack->top=-1;
}

入栈

入栈首先需要判断栈是否满了，这里设置栈大小为20，由0下标开始，即top指向19时就代表栈满了然后进行top自增并添加数据

//入栈
void add(MStack *mStack,int data){
    if(mStack->top==19){
            //栈已满
        return;
    }
    mStack->data[++(mStack->top)]=data;
}

出栈

出栈的操作并没有修改栈中的数据的内容，只是移动了top的值出栈需要先判断栈是否为空出栈的同时将栈顶元素赋值给data

//出栈
void pop(MStack *mStack,int *data){
     if(mStack->top==-1){
            //栈是空的
        return;
    }
    *data=mStack->data[(mStack->top)--];
}

共享栈

再分配栈大小时，太小会导致数据存储不下，而太大可能又会造成大量的空间被浪费，因此采用共享栈的思想，主要思想就是一个top，默认值为-1，一个down，默认存储栈的最大存储数据量-1。如下图所示

入栈 down向下移动，top向上移动出栈 down向上移动，top向下移动 判断共享栈是否满了 down-1等于top时就说明栈满了

数据结构

typedef struct{ int data[MAXSIZE]; int top; int down; } ShareStack;

初始化

需要同时对top和down进行初始化

void initShareStack(ShareStack *mStack){
    mStack->top=-1;
    mStack->down=20;
}

入栈

void addTop(ShareStack *mStack,int data){
    if(mStack->top==(mStack->down-1)){
            //栈已满
        return;
    }
    mStack->data[++(mStack->top)]=data;
}

void addDown(ShareStack *mStack,int data){
    if(mStack->top==(mStack->down-1)){
            //栈已满
        return;
    }
    mStack->data[--(mStack->down)]=data;
}

出栈

//top端出栈
void popTop(ShareStack *mStack,int *data){
     if(mStack->top==-1){
            //栈是空的
        return;
    }
    *data=mStack->data[(mStack->top)--];
}

//down端出栈
void popDown(ShareStack *mStack,int *data){
     if(mStack->down==20){
            //栈是空的
        return;
    }
    *data=mStack->data[(mStack->down)++];
}

总代码

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAXSIZE 20
typedef struct
{
    int data[MAXSIZE];
    //采用top指针指向栈顶元素的方式 初始为-1
    int top;
} MStack;

//初始化栈
void initStack(MStack *mStack)
{
    mStack->top=-1;
}

//入栈
void add(MStack *mStack,int data)
{
    if(mStack->top==19)
    {
        //栈已满
        return;
    }
    mStack->data[++(mStack->top)]=data;
}

//出栈
void pop(MStack *mStack,int *data)
{
    if(mStack->top==-1)
    {
        //栈是空的
        return;
    }
    *data=mStack->data[(mStack->top)--];
}
void forEach(MStack mStack)
{
    for(int i=mStack.top; i>-1; i--)
    {
        printf("%d\n",mStack.data[i]);
    }
}
/**
共享栈
**/
typedef struct
{
    int data[MAXSIZE];
    int top;
    int down;
} ShareStack;


void initShareStack(ShareStack *mStack)
{
    mStack->top=-1;
    mStack->down=20;
}

void addTop(ShareStack *mStack,int data)
{
    if(mStack->top==(mStack->down-1))
    {
        //栈已满
        return;
    }
    mStack->data[++(mStack->top)]=data;
}

//出栈
void popTop(ShareStack *mStack,int *data)
{
    if(mStack->top==-1)
    {
        //栈是空的
        return;
    }
    *data=mStack->data[(mStack->top)--];
}


void addDown(ShareStack *mStack,int data)
{
    if(mStack->top==(mStack->down-1))
    {
        //栈已满
        return;
    }
    mStack->data[--(mStack->down)]=data;
}

//出栈
void popDown(ShareStack *mStack,int *data)
{
    if(mStack->down==20)
    {
        //栈是空的
        return;
    }
    *data=mStack->data[(mStack->down)++];
}

void forEachTop(ShareStack mStack)
{
    for(int i=mStack.top; i>-1; i--)
    {
        printf("%d\n",mStack.data[i]);
    }
}
void forEachDown(ShareStack mStack)
{
    for(int i=mStack.down; i<20; i++)
    {
        printf("%d\n",mStack.data[i]);
    }
}
void main()
{
    MStack mStack;
    ShareStack sStack;
    initShareStack(&sStack);
    initStack(&mStack);
    for(int i=0; i<25; i++)
    {
        addTop(&sStack,i);
        addDown(&sStack,i);
    }
    forEachTop(sStack);
    forEachDown(sStack);
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-06-19，如有侵权请联系 cloudcommunity@tencent.com 删除

void

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度