数据结构——栈总结
本文最后更新于315 天前,其中的信息可能已经过时,如有错误请发送邮件到echobydq@gmail.com

顺序栈

表示

#define MAXSIZE 100
typedef struct {
    SElemType *base; //栈底指针(表头端)
    SelemType *top;  //栈顶指针(表尾端)
    int stacksize;   //栈可用最大容量
}SqStack;

 

初始化

Status InitStack(SqStack &S) {
    //构造一个空栈
    S.base = (SElemType*)malloc(MAXSIZE*sizeof*(SElemType));
    if (!S.base) 
        exit (OVERFLOW);  //存储分配失败
    
    S.top = S.base;       //栈顶指针等于栈底指针
    S.stacksize = MAXSIZE;
    return OK;
}

 

判断是否为空

Status StackEmpty(SqStack S) {
    if (S.top == S.base)   //栈为空标志:S.top == S.base
        return TRUE;
    else
        return FALSE;
}

 

清空

Status ClearStack(SqStack &S) {
    if (S.base)
        S.top = S.base;
    return OK;
}

 

销毁

Status Destroy(SqStack &S) {
    if (S.base){
        free S.base;
        S.stacksize = 0;
        S.base = S.top = NULL;
    }
}

 

入栈

Status Push(SqStack &S, SElemType e) {
    if (S.top - S.base == S.stacksize) //栈满
        return ERROR;
    *S.top++ = e;   //*S.top = e; S.top++;
    return Ok;
}

 

出栈

Status Pop(SqStack &S, SElemType &e) {
    if (S.top == S.base)   //栈为空
        return ERROR;
    e = *--S.top;  //--S.top; e = *S.top
    return OK;
}

 

获取栈顶元素值

Status GetTop(SqStack S, SElemType &e) {
    if (S.top == S.base)
        return ERROR;
    e = *(S.top-1);
    return OK;
}

 

 

链栈

表示

  1. 链表的头指针就是栈顶
  2. 不需要头结点
  3. 基本不存在栈满的情况
  4. 空栈相当于头指针指向空
  5. 插入和删除仅在栈顶出执行
typedef struct StackNode {
    SElemType data;
    struct StackNode *next;
}StackNode, *LinkStack;
LinkStack S;

 

初始化

void InitStack(LinkStack &S) {
    S = NULL; //空栈,栈顶指针置空
    return OK;
}

 

判断是否为空

Status StackEmpty(LinkStack S) {
    if (S == NULL)
        return TRUE;
    else
        return FALSE;
}

 

入栈

Status Push(LinkStack &S, SElemType e) {
    StackNode *p;
    p->data = e;    //将新结点数据域置为 e
    p->next = S;    //将新结点插入栈顶
    S = p;          //修改栈顶指针
    return OK;
}

 

出栈

Status Pop(LinkStatck &S, SElemType e) {
    if (S == NULL)
        return ERROR;
    e = S->data;
    p = S;
    S = S->next;
}

 

C语言实现代码

顺序栈

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 5    /* 栈最大容量 */
#define Empty 0        /* 空 */
#define Full 1        /* 满 */
#define Avail -1    /* 可用 */

typedef struct sta
{
    int *top;            /* 栈顶指针 */
    int *base;        /* 栈底指针 */
    int stacksize;        /* 栈的最大容量 */
}SqStack;

SqStack InitStack (SqStack p);    // 初始化栈
SqStack Push (SqStack p);        //入栈
SqStack Pop (SqStack p);        // 出栈
void DisplyStack (SqStack p);    // 遍历栈中元素
int StackEmpty (SqStack p);    // 判断栈是否为空
int StackFull (SqStack p);    // 判断栈是否为满

int main()
{
    SqStack p;
    char ch;

    p.stacksize = MAX_SIZE;
    p = InitStack (p);    /* 初始化栈 */

    //入栈
    printf("你想要添加元素吗到栈吗? (Y/N)\n");
    scanf(" %c", &ch);
    while (ch == 'Y' || ch == 'y')
    {
        p = Push (p);    /* 入栈 */
        DisplyStack (p);/* 打印栈中元素 */
        printf("你想要添加元素吗到栈吗?(Y/N)\n");
        scanf(" %c", &ch);
    }

    //出栈
    printf("你想出栈吗?(Y/N)\n");
    scanf(" %c", &ch);
    while (ch == 'Y' || ch == 'y')
    {
        p = Pop (p);
        DisplyStack (p);
        printf("你想出栈吗?(Y/N)\n");
        scanf(" %c", &ch);
    }
    return 0;
}

//初始化
SqStack InitStack (SqStack p)
{
    p.base = (int *)malloc(p.stacksize * sizeof(int));
    if (p.base == NULL)
    {
        printf("初始化栈失败\n");
        exit(0);
    }
    p.top = p.base;
    p.stacksize = MAX_SIZE;

    return p;
}

//入栈
SqStack Push (SqStack p)
{
    int data;
    if (StackFull(p) == Full)
    {
        printf("栈空间已满,无法入栈");
        return p;
    }
    printf("输入数字:");
    scanf("%d", &data);
    *p.top = data;
    p.top++;      //*p.top++ = data

    return p;
}

//出栈
SqStack Pop (SqStack p)
{
    int data;
    if (StackEmpty(p) == Empty)
    {
        printf("栈为空栈,无法出栈 ");
        return p;
    }
   // p.top--;
   // printf("出栈元素为:%d\n", *p.top);
     data = *--p.top;
     printf("出栈元素为:%d\n",data);
    return p;
}

//判断栈是否为空
int StackEmpty (SqStack p)
{
    if (p.top == p.base)
    {
        return Empty;
    }
    else
    {
        return Avail;
    }
}

//判断栈是否为满
int StackFull (SqStack p)
{
    if (p.top - p.base == p.stacksize)
    {
        return Full;
    }
    else
    {
        return Avail;
    }
}

//遍历栈中元素,从栈顶到栈底
void DisplyStack (SqStack p)
{
    if (StackEmpty(p) == Empty)
    {
        printf("栈为空栈,无法遍历\n");
        return;
    }
    printf("栈中元素为:\n");
    printf("顶端      [");
    while (p.top != p.base)
    {
        //p.top--;
        //printf("%d",*p.top);
        printf("%d", *--p.top);
    }
    printf("]       底端\n");
}

 

链栈

#include <stdio.h>
#include <stdlib.h>

typedef struct lineStack {
    int data;
    struct StackNode *next;
}StackNode, *LineStack;

LineStack push(LineStack S, int a);  //入栈
LineStack pop(LineStack S);            //出栈

int main() {
    LineStack S = NULL;
    S = push(S, 1);
    S = push(S, 2);
    S = push(S, 3);
    S= push(S, 4);
    S = pop(S);
    S = pop(S);
    S= pop(S);
    S = pop(S);
    S = pop(S);
    return 0;
}


//入栈
LineStack push(LineStack S, int a) {
    //创建存储新元素的节点
    StackNode* line = (LineStack)malloc(sizeof(StackNode*));
    line->data = a;
    //新节点与头节点建立逻辑关系
    line->next = S;
    //更新头指针的指向
    S = line;
    return S;
}

//出栈
LineStack pop(LineStack S) {
    if (S) {
        //声明一个新指针指向栈顶节点
        StackNode* p = S;
        //更新头指针
        S = S->next;
        printf("出栈元素:%d ", p->data);
        if (S) {
            printf("新栈顶元素:%d\n", S->data);
        }
        else {
            printf("栈已空\n");
        }
        free(p);
    }
    else {
        printf("栈内没有元素(空栈)");
        return S;
    }
    return S;
}

 

 

觉得有帮助可以投喂下博主哦~感谢!
作者:Echo
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0协议
转载请注明文章地址及作者哦~

评论

  1. k
    2 年前
    2022-10-23 13:46:55

    你好,麻烦问一下这里面的代码块是在怎么插入,问什么我的wordpress文章编辑器里面插入的代码块,不是这样显示😳

    来自吉林
    • 2 年前
      2022-10-23 13:54:49

      点击 +,然后选择 代码, 然后复制到里面就行了,你可以发下你的网站,我看看效果

      来自江苏
    • 2 年前
      2022-10-23 13:55:25

      发送评论下拉可以添加你的网站链接

      来自江苏
      • k
        秃头baby(管理员)
        已编辑
        2 年前
        2022-10-23 13:56:29

        https://kedaofx.com/2022/05/47/ 是按加号设置的,但是显示不是你这样。

        来自吉林
        • 2 年前
          2022-10-23 14:00:52

          方面发下你文章的编辑页面吗,邮箱是 big_fw@foxmail.com

          来自江苏
          • k
            秃头baby(管理员)
            2 年前
            2022-10-23 14:01:14

            好的

            来自吉林

发送评论(请正确填写邮箱地址,否则将会当成垃圾评论处理) 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇