数据结构-栈

基于C/C++顺序栈和链栈的构建与操作。

---

顺序栈

---

栈的结构

#define MaxSize 50
typedef int ElemType;

//顺序栈结构
typedef struct{
    ElemType data[MaxSize];
    int top;    //栈的栈顶
} SeqStack;

栈的操作

进栈

//进栈
bool SeqStack_Push(SeqStack *S, ElemType x)
{
    if (S->top >= MaxSize - 1)//若栈满，拒绝入栈
        return false;
    S->data[++S->top] = x; //先移动指针。再赋值
    return true;
}

出栈

//出栈,返回出栈元素值
bool SeqStack_Pop(SeqStack *S)
{
    if (S->top == -1) //若空栈，返回
        return false;
    ElemType x = S->data[S->top--];//取得出栈元素后，top指针下移
    S->data[S->top + 1] = NULL;//将要删除的元素删除
    printf("ELm %d has been out\n", x);
    return true;
}

自动建栈

//自动建栈
SeqStack *Create_SeqStack()
{
    SeqStack *S; //定义栈
    S = (SeqStack *)malloc(sizeof(SeqStack));
    S->top = -1; //初始化栈顶指针
    for (int i = 0; i < 10; i++)
    {
        SeqStack_Push(S, i);
    }
    return S;
}

遍历打印

// 从栈顶遍历顺序栈元素
void Print_SeqStack_FromTop(SeqStack *S)
{
    if (S->top == -1)
        printf("NULL");
    for (int x = S->top; x > -1; x--)
    {
        printf("%d ", S->data[x]);
    }
    printf("\n");
}

···

---

### 链栈

---

栈的结构

typedef int ElemType;

// 链式栈的结点
typedef struct SNode{
    ElemType data;
    struct SNode *next;
} SNode;

//链式栈的结构
typedef struct LinkedStack{
    SNode *top;  //栈顶指针
    int count;  //链式栈的结点数
} LinkedStack;

栈的操作

进栈

// 进栈
bool LinkedStack_Push(LinkedStack *S, ElemType x)
{
    SNode *p = (SNode*)malloc(sizeof(SNode));//申请新结点内存
    p->data = x;//赋值
    p->next = S->top;//p得后继指针指向原来的栈顶
    S->top = p;//将栈顶指针移动到新结点
    S->count++;//增加结点数
    return true;
}

出栈

// 出栈
bool LinkedStack_Pop(LinkedStack *S)
{
    if (!S->top)//判定是否为空
        return false;
    ElemType x = S->top->data;//得到出栈元素
    SNode *p = S->top;//辅助指针指向栈顶
    S->top = S->top->next;//移动栈顶指针到原栈顶指针的后继
    free(p);//释放掉原栈顶
    S->count--;//结点数-1
    printf("Elem %d has been out of stack\n",x);
    return true;
}

自动建栈

//自动建栈
LinkedStack *Create_LinkedStack()
{
    LinkedStack *S;
     S = (LinkedStack*)malloc(sizeof(SNode));//申请内存
    S->count = 0;//初始化结点数
    S->top = NULL;//初始化栈顶指针
    for (int x = 0; x < 10; x++)
    {
        LinkedStack_Push(S, x);//进栈操作
    }
    return S;
}

遍历打印

//遍历打印
void Print_LinkedStack_FromTop(LinkedStack *S)
{
    SNode *p = S->top;
    while (p)//当栈顶指针不为空
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

···

---

### 测试源码

---

链式栈源码，请点击这里获取



顺序栈源码，请点击这里获取

---

随时补充

---