数据结构-栈

时间:2022-01-24作者:klpeng分类:IT综合浏览:407评论:0

目录

栈是什么

一  、顺序存储栈

二、共享栈

三、链式栈


栈是什么

        栈是一种只能在一端进行插入和删除操作的线性表,具有“后进先出”的特点,只允许在一端进行插入和删除数据。栈有很多应用,比如软件中的返回上一页等

数据结构-栈

 一 、顺序存储栈

       顺序栈采用的是像线性表一样分配了一块连续空间来存储栈中的数据,就是用数组来存储数据,另外有一个下标来记录栈顶指针所指向的位置。用来存储数据的数组可以是整型也可以是字符型。每次压入栈中的元素在实际存储位置上是正常的从下标为0开始的,但是我们通过控制栈顶的移动来实现逻辑上的只对栈顶进行删除(出栈)从而达到后进先出的原理。

首先定义一个结构体顺序栈:

#define MaxSize 1000
typedef int ElemType;
typedef struct
{
    //用一个data数组要存储栈内的元素(数组下标从0开始)
    ElemType data[MaxSize]; //压入栈的元素 
    
    //用一个整型变量top记录栈顶的位置
    int top; //栈顶的位置(当前数组元素的最大下标)
}SqStack;

 接下来实现栈的基本功能:

1.顺序栈初始化

//初始化栈
void InitStack(SqStack *&s) //创建一个空栈
{
    s = (SqStack *)malloc(sizeof(SqStack)); //分配一个栈的空间

    s->top = -1; //初始化是栈顶为-1
}

2.顺序栈销毁

//销毁栈
void DestroyStack(SqStack &s )
{
    free(s); //释放栈的空间
}

3.顺序栈判空
 

//判断栈是否为空
bool StackEmpty(SqStack *S)
{
    
    //栈为空的话,就是栈内没有元素,s->top为-1
      return s->top==-1;

}

4.顺序栈进栈

 把元素压入栈需要判断栈是否满,能否压入

bool Push(SqStack *&s,ElemType e) //将e压入栈中
{

    //入栈之前先判断能否压入
    if(s->top == MaxSize-1) //判断栈满
    {
        return false;
    }
    s->top++ ; //因为空栈设置为-1,则每次需要先移动栈指针在将元素压入对应的空间中
    s->data[top] = e ;//每次入栈的元素所表示的数组下标就是栈顶
    return true;

}

5.顺序栈出栈

  出栈的就需要判断栈内是否有元素可以弹出,也就是说当栈为空的话就不能出栈了,也就是判空

bool Pop(SqStack *&s,ElemType &e) //出栈,并且将出栈的元素赋值给e
{
    if(s->top==-1)
    {
        return false;//如果栈为空就无法出栈
    }
    e = s->data[top]; //记录出栈的元素
    s->top--; //相关于覆盖e在栈中的值,使其无法访问e元素

}

6.取栈顶元素 

bool GetTop(SqStack *s , ElemType &e) //将栈顶元素赋值给 形参e
{
    if(s->top == -1) //判空,如果栈为空则无法在栈中取元素
    {
        return false;
    }
    e = s->data[top];
    return true;    
}

 栈需要注意的要素:

  1. 判断栈内为空的条件 : s->top == -1 ; (存储元素从0开始)

  2. 判断栈内为满的条件:  s->top == MaxSize-1(data数组里的最大下标); 

 顺序栈的应用:将10进制的数转换成n进制

二、共享栈

        前面讲述的顺序栈是采用了一个数组来存储栈中的元素,有这样的一种情况,定义了一个栈,里面存储的元素只有一个,而定义的MaxSize是1000,也就是说有1000个空间的数组栈只存储了一个数据。现在需要定义另外一个栈,存储999个元素,那么假如是顺序栈的话,就又需要定义一个栈的结构体,开辟1000个int大小的内存(不止),来存储这999个元素。又假设1000为n,n为无穷大。那么第一个声明的栈所浪费的空间就很大。但是一个顺序栈又无法存储两个名字不一样的栈。那么针对这个需求,共享栈就可以解决。

       之所以叫共享栈,就是在栈容量足够的情况下一个栈可以存储两个栈的数据。之所以说栈是只允许一端插入删除,也就是没有局限于前后,常规的栈顶指针是指向了-1,每次入栈栈顶指针就会++,那么我们就新增加一个栈顶指针指向MaxSize。每次入栈的话就会--。两个不同的栈进行操作的话,就只需要控制其中一个栈顶指针就可以了。

       对应的top1的栈,每次入栈都要top1++,出栈top--

       对应的top2的栈,每次入栈都要top2--,出栈top2++

#define MaxSize 1000
typedef struct
{
    int data[MaxSize];

    int top1,top2;
}SStack;

1.共享栈初始化

//初始化栈
void InitStack(SStack *&s) //创建一个空栈
{
    s = (SStack *)malloc(sizeof(SStack)); //分配一个栈的空间

    s->top1 = -1; //初始化是栈顶为-1
    s->top2 = MaxSize;
}

  2.共享栈判空.

  当栈为空时返回true 否则返回false.

  栈空的话就是top1==-1并且top2==MaxSize 

//判空的条件
bool isEmpty(SStack *&s)
{

    return top1==-1&&top2==MaxSize;

}

  栈满的条件:top1==top2-1。

  共享栈的应用:  在一个数组中实现两个栈

 三、链式栈

        上述的顺序栈,共享栈,基本能够表示一个有限长度的栈,那么当要存储一个大于了MaxSize大小的栈,又该如何实现呢 ? 答案就是链式栈,接下来就是链式栈的实现。

 栈使用链式存储的话,假设按照顺序栈的思路来实现链式栈,那么每次找到栈顶都需要从头遍历一遍才能找到,链式存储的弊端就是无法快速的通过索引查找。所以,将采用头插法来存储元素,每次入栈元素   都会是s->next->data;就是说每次都是在头结点插入。(带头结点)

1.链式栈的声明

typedef struct LinkStack
{
    int data;
    strcut LinkStack *next;
}LinkStack;

2.链式栈的初始化

void initStack(LinkStack *&s)
{
    s = (LinkStack *)malloc(sizeof(LinkStack));
    
    s->next = NULL; //栈顶初始为空

}

3.链式栈入栈

每次入栈都是使用头插法,使栈顶每次都指向第一个结点,这样方便找到栈顶指针并且方便插入和删除。

void pushStack(LinkStack*& s, int elem)
{
       //因为是链式栈,不需要判断栈满
        LinkStack *k;
        k = (LinkStack *)malloc(sizeof(LinkStack));
        k->data = elem;
        
        //头插法
        k->next  =  s->next;
        s->next  =  k;



}

4.链式栈判空

bool isEmpty(LinkStack *s)
{

    return s->next==NULL;

}

5.链式栈出栈

就是将

int elem = s->next->data;

s->next = s->next->next;

打赏
文章版权声明:除非注明,否则均为彭超的博客原创文章,转载或复制请以超链接形式并注明出处。
相关推荐

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

猜你喜欢