当前位置:   article > 正文

顺序栈 C语言 进栈 出栈 遍历

出栈


前言

是限定仅在表尾进行插入和删除操作的线性表


概述栈

1、栈的定义

栈(stack)是限定仅在表尾进行插入和删除操作的线性表。

我们把允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom),不汉人和数据元素的栈称为空栈。栈有称为后进先出(Last In Fast Out)的现行表,简称LIFO结构。


理解栈的含义需要注意:

首先它是一个线性表,也就是说,栈元素具有线性关系,即前驱后继关系。只不过它是一种特殊的线性表而已。定义中说是在线性表的表尾进行插入和删除操作,这里表尾是指栈顶,而不是栈底。

栈的插入操作,叫做进栈,也称压栈、入栈。 类似子弹入弹夹,若左下图所示。

栈的删除操作,叫做出栈,有的也叫做弹栈。 如同单价找那个的子弹出夹,如右下图所示。

请添加图片描述


2、进栈出栈变化形式

最先进栈的元素,是不是就只能是最后出栈呢?

答案是不一定的,要看什么情况。栈对线性表的插入和删除的位置进行了限制,并没有对元素近处的时间进行限制,也就是说,在不是所有元素都进栈的情况下,事先进去的元素也可以出栈,只要保证是栈顶元素出栈就可以。


举例来说,如果我们现在是有3个整型数字元素1、2、3依次出栈,会有哪些出战次序呢?

第一种:1、2、3进,再3、2、1出。这是最简单最好理解的一种,出战次序为3、2、1。

第二种:1进,1出,2进,2出,3进,3出。也就是进一个出一个,出栈次序为1、2、3。

第三种:1进,2进,2出,1出,3进,3出。出战次序为2、1、3。

第四种:1进,1出,2进,3进,3出,2出。出栈次序为1、3、2。

第五种:1进,2进,2出,3进,3出,1出。出栈次序为2、3、1。


有没有可能是3、1、2这样的次序出现呢?

肯定不会。

因为3先出栈,就意味着,3曾经进栈,既然3都进栈了,那也就意味着,1和2已经进栈了,此时,2一定是在1的上面,就是更接近栈顶,那么出栈只可能是3、2、1,不然不满足1、2、3依次进栈的要求,所以此时不会发生1比2先进栈的情况。


代码实现

1、构建顺序栈结构

构建一个顺序栈,需要用到结构体,定义如下

/* 顺序栈结构 */
typedef struct
{
        SElemType data[MAXSIZE];
        int top; /* 用于栈顶指针 */
}SqStack;
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

2、构造一个空栈

构造空栈我们可以使用到malloc也可以用到top指针指向-1

/*  构造一个空栈S */
Status InitStack(SqStack *S)
{ 
        /* S.data=(SElemType *)malloc(MAXSIZE*sizeof(SElemType)); */
        S->top=-1;
        return OK;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

3、把整个栈变为空栈

置为空栈,那么就是直接让top指针指向-1(即最底部即可)

/* 把S置为空栈 */
Status ClearStack(SqStack *S)
{ 
        S->top=-1;
        return OK;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

4、判断栈是否为空

/* 若栈S为空栈,则返回TRUE,否则返回FALSE */
Status StackEmpty(SqStack S)
{ 
        if (S.top==-1)
                return TRUE;
        else
                return FALSE;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

5、返回栈中的元素个数,即栈的长度

/* 返回S的元素个数,即栈的长度 */
int StackLength(SqStack S)
{ 
        return S.top+1;
}
  • 1
  • 2
  • 3
  • 4
  • 5

6、用e返回栈顶元素,并返回OK;否则返回ERROR

/* 若栈不空,则用e返回S的栈顶元素,并返回OK;否则返回ERROR */
Status GetTop(SqStack S,SElemType *e)
{
        if (S.top==-1)
                return ERROR;
        else
                *e=S.data[S.top];
        return OK;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

7、插入元素e为新的栈顶元素

/* 插入元素e为新的栈顶元素 */
Status Push(SqStack *S,SElemType e)
{
        if(S->top == MAXSIZE -1) /* 栈满 */
        {
                return ERROR;
        }
        S->top++;				/* 栈顶指针增加一 */
        S->data[S->top]=e;  /* 将新插入元素赋值给栈顶空间 */
        return OK;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

8、删除栈顶元素,用e返回其值,并返回OK;否则返回ERROR

/* 若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR */
Status Pop(SqStack *S,SElemType *e)
{ 
        if(S->top==-1)
                return ERROR;
        *e=S->data[S->top];	/* 将要删除的栈顶元素赋值给e */
        S->top--;				/* 栈顶指针减一 */
        return OK;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

9、遍历

/* 从栈底到栈顶依次对栈中每个元素显示 */
Status StackTraverse(SqStack S)
{
        int i;
        i=0;
        while(i<=S.top)
        {
                visit(S.data[i++]);
        }
        printf("\n");
        return OK;
}
Status visit(SElemType c)
{
        printf("%d ",c);
        return OK;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

整体代码

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

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status; 
typedef int SElemType; /* SElemType类型根据实际情况而定,这里假设为int */

/* 顺序栈结构 */
typedef struct
{
        SElemType data[MAXSIZE];
        int top; /* 用于栈顶指针 */
}SqStack;

Status visit(SElemType c)
{
        printf("%d ",c);
        return OK;
}

/*  构造一个空栈S */
Status InitStack(SqStack *S)
{ 
        /* S.data=(SElemType *)malloc(MAXSIZE*sizeof(SElemType)); */
        S->top=-1;
        return OK;
}

/* 把S置为空栈 */
Status ClearStack(SqStack *S)
{ 
        S->top=-1;
        return OK;
}

/* 若栈S为空栈,则返回TRUE,否则返回FALSE */
Status StackEmpty(SqStack S)
{ 
        if (S.top==-1)
                return TRUE;
        else
                return FALSE;
}

/* 返回S的元素个数,即栈的长度 */
int StackLength(SqStack S)
{ 
        return S.top+1;
}

/* 若栈不空,则用e返回S的栈顶元素,并返回OK;否则返回ERROR */
Status GetTop(SqStack S,SElemType *e)
{
        if (S.top==-1)
                return ERROR;
        else
                *e=S.data[S.top];
        return OK;
}

/* 插入元素e为新的栈顶元素 */
Status Push(SqStack *S,SElemType e)
{
        if(S->top == MAXSIZE -1) /* 栈满 */
        {
                return ERROR;
        }
        S->top++;				/* 栈顶指针增加一 */
        S->data[S->top]=e;  /* 将新插入元素赋值给栈顶空间 */
        return OK;
}

/* 若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR */
Status Pop(SqStack *S,SElemType *e)
{ 
        if(S->top==-1)
                return ERROR;
        *e=S->data[S->top];	/* 将要删除的栈顶元素赋值给e */
        S->top--;				/* 栈顶指针减一 */
        return OK;
}

/* 从栈底到栈顶依次对栈中每个元素显示 */
Status StackTraverse(SqStack S)
{
        int i;
        i=0;
        while(i<=S.top)
        {
                visit(S.data[i++]);
        }
        printf("\n");
        return OK;
}

int main()
{
        int j;
        SqStack s;
        int e;
        if(InitStack(&s)==OK)
                for(j=1;j<=10;j++)
                        Push(&s,j);
        printf("栈中元素依次为:");
        StackTraverse(s);
        Pop(&s,&e);
        printf("弹出的栈顶元素 e=%d\n",e);
        printf("栈空否:%d(1:空 0:否)\n",StackEmpty(s));
        GetTop(s,&e);
        printf("栈顶元素 e=%d 栈的长度为%d\n",e,StackLength(s));
        ClearStack(&s);
        printf("清空栈后,栈空否:%d(1:空 0:否)\n",StackEmpty(s));
        
        return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家小花儿/article/detail/458131
推荐阅读
相关标签
  

闽ICP备14008679号