手机版
你好,游客 登录 注册
背景:
阅读新闻

C语言 栈(顺序栈)

[日期:2019-08-02] 来源:Linux社区  作者:lanhaicode [字体: ]

栈是一种运算受限的线性表,是一种先进后出的数据结构,限定只能在一端进行插入和删除操作,允许操作的一端称为栈顶,不允许操作的称为栈底

顺序栈(顺序结构)

顺序栈:用一段连续的存储空间来存储栈中的数据元素,比较常见的是用数组来实现顺序栈

顺序存储结构:1.元素所占的存储空间必须连续(这里的连续是指的逻辑连续,而不是物理连续)

       2.元素在存储空间的位置是按逻辑顺序存放的

 
顺序栈的实现一般包括如下部分

代码声明部分

#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 *bottom;        /* 栈底指针 */
    int stack_size;        /* 栈的最大容量 */
}stack;
stack Push (stack p);        /* 入栈 */
void DisplyStack (stack p);    /* 遍历栈中元素 */
stack Pop (stack p);        /* 出栈 */
stack InitStack (stack p);    /* 初始化栈 */
int StackEmpty (stack p);    /* 判断栈是否为空 */
int StackFull (stack p);    /* 判断栈是否为满 */

一、栈的声明

第一种:

1 typedef struct sta
2 {
3    int stack[SIZE];    /* 存放栈中元素的一维数组 */
4    int top;            /* 存放栈顶元素的下标 */
5 }stack;

(这里只用了一个top来指向栈顶的位置,也可以用两个变量base、top来分别指向栈空间栈底位置和栈顶位置)

第二种:(本篇随笔是使用的第二种声明方式)

1 typedef struct sta
2 {
3    int *top;            /* 栈顶指针 */
4    int *bottom;        /* 栈底指针 */
5    int stack_size;        /* 栈的最大容量 */
6 }stack;

二、栈的初始化

/* Function:栈的初始化 */
stack InitStack (stack p)
{
    p.bottom = (int *)malloc(p.stack_size * sizeof(int));
    if (p.bottom == NULL)
    {
        printf("初始化栈失败\n");
        exit(0);
    }
    p.top = p.bottom;
    p.stack_size = MAX_SIZE;

    return p;
}

三、入栈(压栈)

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

    return p;
}

四、出栈

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

    return p;
}

(栈顶指针指向的位置是栈顶指针的后一个元素,所以在出栈时需要p.top--,才能指向出栈的元素)

五、判断栈是否为空

/* Function:判断栈是否为空 */
int StackEmpty (stack p)
{
    if (p.top == p.bottom)
    {
        return Empty;
    }
    else
    {
        return Avail;
    }
}

六、判断栈是否为满

/* Function:判断栈是否为满 */
int StackFull (stack p)
{
    if (p.top - p.bottom == p.stack_size)
    {
        return Full;
    }
    else
    {
        return Avail;
    }
}

七、遍历栈中的元素

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

顺序栈实现--完整代码

#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 *bottom;        /* 栈底指针 */
    int stack_size;        /* 栈的最大容量 */
}stack;
stack Push (stack p);        /* 入栈 */
void DisplyStack (stack p);    /* 遍历栈中元素 */
stack Pop (stack p);        /* 出栈 */
stack InitStack (stack p);    /* 初始化栈 */
int StackEmpty (stack p);    /* 判断栈是否为空 */
int StackFull (stack p);    /* 判断栈是否为满 */

int main()
{
    stack p;
    char ch;
   
    p.stack_size = MAX_SIZE;
    p = InitStack (p);    /* 初始化栈 */
    printf("Do you want to push to stack?(Y/N)");
    scanf(" %c", &ch);
    while (ch == 'Y' || ch == 'y')
    {
        p = Push (p);    /* 入栈 */
        DisplyStack (p);/* 打印栈中元素 */
        printf("Do you want to push to stack?(Y/N)");
        scanf(" %c", &ch);
    }
    printf("Do you want to pop (Y/N)");
    scanf(" %c", &ch);
    while (ch == 'Y' || ch == 'y')
    {
        p = Pop (p);
        DisplyStack (p);
        printf("Do you want to pop (Y/N)");
        scanf(" %c", &ch);
    }

    return 0;
}
/* Function:判断栈是否为空 */
int StackEmpty (stack p)
{
    if (p.top == p.bottom)
    {
        return Empty;
    }
    else
    {
        return Avail;
    }
}
/* Function:判断栈是否为满 */
int StackFull (stack p)
{
    if (p.top - p.bottom == p.stack_size)
    {
        return Full;
    }
    else
    {
        return Avail;
    }
}
/* Function:入栈 */
stack Push (stack p)
{
    int data;
    if (StackFull(p) == Full)
    {
        printf("栈空间已满,无法入栈");
        return p;
    }
    printf("Please input data");
    scanf("%d", &data);
    *p.top = data;
    p.top++;

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

    return p;
}
/* Function:栈的初始化 */
stack InitStack (stack p)
{
    p.bottom = (int *)malloc(p.stack_size * sizeof(int));
    if (p.bottom == NULL)
    {
        printf("初始化栈失败\n");
        exit(0);
    }
    p.top = p.bottom;
    p.stack_size = MAX_SIZE;

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

栈顶指针的指向有两种方式,一种是指向栈顶元素的后一元素(本文使用的就是这种),另一种是指向栈顶元素,两者在判断栈为空和满的条件、入栈、出栈时栈顶指针的移动有一些差异。

Linux公社的RSS地址https://www.linuxidc.com/rssFeed.aspx

本文永久更新链接地址https://www.linuxidc.com/Linux/2019-08/159764.htm

linux
相关资讯       C语言栈  顺序栈 
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款