#数据结构（二）

栈和队列

一.栈的顺序存储结构

特点：先进后出

栈是一种只能在一端进行插入或删除操作的线性表。

表中允许插入删除操作的一端为栈顶（top），表的另一端为栈底（bottom），

1 结构体的定义

#include <stdio.h>
typedef int ElemType;
#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE]; // 用于存储栈中的元素
    int top; // 栈顶指针，指向栈顶元素的索引
} SqStack;

2 初始化栈

栈顶指针赋值为-1

void InitStack(SqStack *&s) {
    s = (SqStack *) malloc(sizeof(SqStack));//申请一个顺序栈空间
    s->top = -1;//栈顶指针赋值为-1
}

3 销毁栈

释放节点空间

void DestroyStack(SqStack *&s) {
    free(s);
}

4 判断栈是否为空

指针为-1

bool StackEmpty(SqStack *&s) {
    return (s->top == -1);
}

5 进栈

先判断栈是否为满

注意先将指针++，再对栈顶元素进行赋值

bool PushStack(SqStack *&s, ElemType e) {
    if (s->top == MAX_SIZE - 1) {//栈满的情况
        return false;
    }
    s->top++;
    s->data[s->top] = e;//先加再赋值(s-data[++s->top])
    return true;
}

6 出栈

先对栈元素赋值，再将指针--

bool Pop(SqStack *&s, ElemType &e) {
    if (s->top == -1) {//栈空的情况
        return false;
    }
    e=s->data[s->top];
    s->top--;
    return true;
}

7 获取栈顶元素

bool GetTop(SqStack *s,ElemType &e){
    if (s->top==-1)
        return false;
    e=s->data[s->top];
    return true;
}

补充：共享栈

1. 顺序栈采用一个数组存放栈中的元素。如果需要用到两个类型相同的栈，这时若为它们各自开辟一个数组空间，极有可能出现这样的情况：第一个栈已经满了，再进栈就溢出了，而另一个栈还有许多的空间。
2. 共享栈是为了更有效地利用存储空间，两个栈的空间相互调节，只有在整个存储空间被占满时才会发生上溢。其存储数据的时间复杂度均为O(1),所以对存取效率没有什么影响。
3. 栈空条件：栈0空为top==-1;栈1空为top1==MaxSize.
4. 栈满条件：top==top1-1
5. 元素进栈操作：进栈0操作为top0++；data[top0]=x;进栈1操作为top1--；data[top1]=x
6. 元素出栈操作：出栈0操作为x=data[top0];top0--；出栈1操作为x=data[top1]；top1++
7. 在上述操作中，data数组表示共享栈的存储空间，top0和top1分别为两个栈的栈顶指针，这样该共享栈通过data,top0和top1来标识，也可以将他们设计为一个结构体类型。

二.栈的链式存储结构

栈中的数据元素的逻辑关系呈线性关系，所以栈可以像线性表一样采用链式存储结构

原文地址：https://blog.csdn.net/2302_79847831/article/details/143059816

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！