← 数据结构基础

数据结构-栈

栈(Stack)是一种只能在一端进行插入删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶(Top),另一端称为栈底(Bottom)。当栈中没有数据元素时,称为空栈。栈的插入操作通常称为进栈或入栈(Push),栈的删除操作通常称为退栈或出栈(Pop)。栈的进栈和出栈操作的时间复杂度均为O(1)。
栈顶的当前位置是动态的,由一个称为栈顶指针的位置指示器来指示。栈的主要特点是「后进先出」,即后进栈的元素先出栈。所以栈也被称为后进先出表

顺序栈

顺序栈是栈的顺序存储结构,把元素按照其进栈顺序依次存储到从计算机存储器中指定存储位置开始的一块连续的存储空间中。
顺序栈的四个要素:
  • 栈空条件:s->top == -1
  • 栈满条件:s->top == MaxSize - 1
  • 进栈操作:s->top++;并将要进栈的元素e放在s->top
  • 出栈操作:从s->top处取出要出栈的元素e ,并且s->top--;
栈空时仍进行出栈操作,称为下溢。栈满时仍进行进栈操作,称为上溢

类型定义

#define ElemType int               // 元素类型#define MaxSize 10                 // 最大长度typedef struct{    ElemType data[MaxSize];    int top;                       // 栈顶指针} SqStack;

基本运算

初始化顺序栈

建立一个新的空栈s,将栈顶指针指向 − 1。
// 初始化顺序栈void initStack(SqStack *&s){    s = (SqStack *) malloc(sizeof(SqStack));    s->top = -1;    // 将栈顶指针置为-1}

销毁顺序栈

// 销毁顺序栈void destroyStack(SqStack *&s){    free(s);}

判断是否为空栈

// 判断是否为空栈bool isEmpty(SqStack *s){    return s->top == -1;    // 栈顶指针指向-1表示栈为空}

进栈

在栈不满的条件下,先将栈指针增1,然后在该位置上插入元素e
// 进栈bool push(SqStack *&s, ElemType e){    if (s->top == MaxSize - 1) return false;    // 栈满的情况, 即栈上溢出    s->top++;                                   // 栈顶指针增1    s->data[s->top] = e;                        // 元素e放在栈顶指针处    return true;}

出栈

在栈不为空的条件下,先将栈顶元素赋给e,然后将栈指针减1。
// 出栈bool pop(SqStack *&s, ElemType &e){    if (s->top == -1) return false;     // 栈为空的情况, 即栈下溢出    e = s->data[s->top];                // 取栈顶指针元素的元素    s->top--;                           // 栈顶指针减1    return true;}

获取栈顶元素值

在栈不为空的条件下,将栈顶元素赋给e
// 获取栈顶元素bool getTop(SqStack *s, ElemType &e){    if (s->top == -1) return false;     // 栈为空的情况, 即栈下溢出    e = s->data[s->top];                // 取栈顶指针处的元素    return true;}

链栈

栈的链式存储结构称为链栈,采用单链表实现。链栈的优点是不存在栈满上溢的情况。这里规定栈的所有操作都是在单链表的表头进行的。用带头结点的单链表表示链栈,第一个数据结点是栈顶结点,最后一个结点是栈底结点
栈中元素自栈顶到栈底依次是a1, a2, …an
链栈的四个要素:
  • 栈空条件:s->next == NULL
  • 栈满条件:不考虑
  • 进栈操作:将包含e的结点插入到头结点之后
  • 出栈操作:取出头结点之后结点的元素并删除

类型定义

#define ElemType int        // 元素类型typedef struct LStNode{    ElemType data;          // 数据域    struct LStNode *next;   // 指针域} LinkStNode;

基本运算

初始化链栈

建立一个空栈s。实际上是创建链栈的头结点,并将其next域置为NULL
image-20210108182508790
// 初始化链栈void initStack(LinkStNode *&s){    s = (LinkStNode *) malloc(sizeof(LinkStNode));    s->next = NULL;}

销毁链栈

// 销毁链栈void destroyStack(LinkStNode *&s){    LinkStNode *pre = s, *p = s->next;    while (p != NULL)   // 遍历子节点并释放其空间    {        free(pre);        pre = p;        p = pre->next;    }    free(pre);          // 此时p指向尾结点, 释放其空间}
image-20210108183028094

判断是否为空栈

// 判断是否为空栈bool isEmpty(LinkStNode *s){    return s->next == NULL;    // 头结点之后无子结点表示栈为空}

进栈

将新数据结点插入到头结点之后。
image-20210108184213931
// 进栈void push(LinkStNode *&s, ElemType e){    LinkStNode *p = (LinkStNode *) malloc(sizeof(LinkStNode));    p->data = e;        // 将要进栈的元素e放入新建结点p的数据域中    p->next = s->next;  // 将结点p插入到表头    s->next = p;}

出栈

在栈不为空的条件下,将头结点的后继(栈顶)结点的数据域赋给e,然后将其删除。
image-20210108184723799
// 出栈bool pop(LinkStNode *&s, ElemType &e){    if (s->next == NULL) return false;  // 栈空的情况    LinkStNode *p = s->next;            // p指向表头栈顶结点    e = p->data;    s->next = p->next;                  // 删除p结点    free(p);                            // 释放p结点    return true;}

获取栈顶元素

在栈不为空的条件下,将头结点后继(栈顶)结点的数据域赋给e
image-20210108185208519
// 获取栈顶元素bool getTop(LinkStNode *s, ElemType &e){    if (s->next == NULL) return false;  // 栈空的情况    e = s->next->data;    return true;}

Nobelium is built with ♥ and ⚛ Next.js. Proudly deployed on ▲Vercel.

© Ashinch 2021 桂ICP备18011166号-1