MENU

数据结构 - 栈

March 24, 2021 • Read: 233 • 数据结构

定义

栈(stack)是只允许在一端进行插入或删除操作的线性表

Stack:整齐的一堆;

重要的术语:栈顶、栈底、空栈

image-20210321140902021

进栈顺序:a1->a2->a3->a4->a5

出栈顺序:a5->a4->a3->a2->a1

特点:后进先出

Last In First Out(LIFO)

和普通的线性表相比,逻辑结构相同,数据的运算:插入、删除操作有区别;

基本操作

InitStack(&s)初始化栈。构造一个空栈S,分配内存空间

DestoryStack(&L):销毁栈。销毁并释放栈S所占用的内存空间

Push(&S,x):进栈。若栈未满,则将x加入使之成为新栈顶

Pop(&S,&x):出栈。若栈非空,则弹出栈元素,并用x返回

删除栈顶元素

GetTop(S,&x):读栈顶元素。若栈S非空,则用x返回栈顶元素

不删除栈顶元素

其他常用操作:

StackEmpty(S):判断一个S是否为空,若为空返回true,否则返回false

关于出栈顺序的问题:

n个不同元素进栈,出栈元素不同排列的个数为$$\frac{1}{n+1}C_{2n}^{n}$$

上述公式称为卡特兰(Catalan)数

储存结构

顺序栈

定义

typedef struct {    
    int data[MaxSize]; // 静态数组存放栈中元素
    int top;        // 栈顶指针
}SqStack;

// 顺序存储:给各个数据元素分配练习的存储空间大小为
// MaxSize*sizeof(ElemType)的空间

初始化

// 初始化栈
void InitStack(SqStack &S) {
    S.top = -1;    // 初始化栈顶指针,
    // 同理也可以设置top的值为0,这个时候top指针指向栈顶上的一个元素
}

判断栈为空

// 判断栈空
bool StackEmpty(SqStack S) {
    if (S.top == -1) {
        return true; // 栈空
    }
    else {
        return false; // 不空
    }
}

入栈操作

// 新元素入栈
bool Push(SqStack &S, int x) {
    if (S.top == MaxSize - 1) { // 栈满,报错
        return false;
    }
    S.top = S.top + 1;    // 指针先加1
    S.data[S.top] = x;    // 新元素入栈
    // 以上的两行代码等价:S.data[++S.top]=x;
    return true;
}

出栈操作

// 出栈操作
bool Pop(SqStack &S, int &x) {
    if (S.top == -1) {
        return false;    // 栈空,报错
    }
    x = S.data[S.top];    // 栈顶元素先出栈
    S.top = S.top - 1;  // 栈顶指针-1
    // 以上两行代码等价:x=S.data[S.top--];

    return true;
}

读取栈顶元素

// 读取栈顶元素的操作
bool GetTop(SqStack S, int &x) {
    if (S.top == -1) {
        return false;    // 栈空,报错
    }
    x = S.data[S.top];    // x记录栈顶元素
    return true;
}

链式栈

定义


typedef struct Stack
{
    int data; // 数据域
    struct Stack *next;// 指针域
}LinkStack;   //链栈结点类型

初始化链栈

// 初始化链栈
bool InitList(LinkStack *S) {
    S = NULL;
    return true;
}

判断栈空

// 判断栈空
bool  StackEmpty(Stack * top) {
    
    if (top = NULL) {
        return true;  // 当top指针为NULL,表示栈为空
    }
    else {
        return false;
    }
}

入栈操作

// 入栈操作
LinkStack * Push(LinkStack *top,int e) {
    LinkStack *p;
    p = (LinkStack*)malloc(sizeof(LinkStack));    // 构建一个节点
    p->data = e;        // 设置新节点的值
    p->next = top;        // 将新元素插入栈中
    top = p;            // 将新元素设置为栈顶
    return top;
}

出栈操作

// 出栈操作
LinkStack * Pop(LinkStack *top) {
    LinkStack *p;
    if (!top) {
        printf("链栈是空的");
        return NULL;
    }
    p = top;            // 指向被删除的栈顶
    top = top->next;    // 修改栈顶指针
    free(p);
    return top;
}

获取栈顶元素

// 获取栈顶元素
int GetTop(LinkStack * top) {
    if (!top) {
        printf("链表为空");
        return 0;
    }
    return top->data;
}

版权声明:文章转载请注明来源,如有侵权请联系删除!

Last Modified: April 12, 2021
Archives QR Code Tip
QR Code for this page
Tipping QR Code