【数据结构之旅】顺序栈的定义、初始化、空栈判断、入栈、出栈操作

说明：

    往前学习数据结构，想运行一个完整的顺序栈的程序都运行不了，因为书上给的都是一部分一部分的算法，并没有提供一个完整可运行的程序，听了实验课，自己折腾了一下，总算可以写一个比较完整的顺序栈操作的小程序，对于栈也慢慢开始有了感觉。下面我会把整个程序拆开来做说明，只要把这些代码放在一个文件中，用编译器就可以直接编译运行了。

一、实现

1.程序功能

  关于栈操作的经典程序，首当要提及进制数转换的问题，利用栈的操作，就可以十分快速地完成数的进制转换。

2.预定义、头文件导入和类型别名

    代码如下：


1

2

3

4

5

6

7

8

9

10

#include<stdio.h>

#include<stdlib.h>

#define OVERFLOW -1

#define ERROR 0

#define FALSE 0

#define TRUE 1

#define OK 1

 

typedef int ElemType;

typedef int Status;

    除了两个头文件的导入是必须的之外，下面做两点说明：

（1）其余的常量定义都是可选的，为的就是在下面的代码书写过程中可以尽量使用英文来表达程序的意思，而不是在代码的实现过程中直接使用数字，依个人喜欢，也可以直接使用数字；

（2）使用typedef做类型的别名也仅仅是为了程序中代码的意思更加清晰明了而已，实际也可以不这样使用；

3.顺序栈的定义

    代码如下：


1

2

3

4

5

6

typedef struct{

    ElemType *elem;     //存储空间的基址

    int top;            //栈顶元素的下一个元素，简称栈顶位标

    int size;           //当前分配的存储容量，作用看入栈操作就可以知道

    int increment;      //扩容时，增加的存储容量，作用看入栈操作就可以知道

} SqStack;                  //顺序栈名称

4.栈的初始化

    代码如下：


1

2

3

4

5

6

7

8

Status InitStack_Sq(SqStack &S, int size, int inc){     //接受3个参数，&S是对结构体的引用

    S.elem = (ElemType*)malloc(size*sizeof(ElemType));  //分配存储空间

    if(S.elem == NULL) return OVERFLOW;     //判断上一步分配存储空间是否成功

    S.top = 0;            //置S为空栈，S.top为0即表示栈为空栈

    S.size = size;        //栈的空间初始容量值

    S.increment = inc;    //栈的空间初始增量值（如果需要扩容）

    return OK;       //上面的执行正常，返回OK

}

5.空栈的判断

    代码如下：


1

2

3

4

5

6

7

8

Status StackEmpty_Sq(SqStack S){

    if(S.top == 0)

        return TRUE;

    else

        return FALSE;

}

//空栈的决断是，如果栈为空就返回1，否则就返回0，当然可以不这样规定；

//至于为什么要做空栈的判断，自然是有原因的，下面再看程序的代码时就可以知道了。

6.入栈

    代码如下：


1

2

3

4

5

6

7

8

9

10

11

12

13

14

Status Push_Sq(SqStack &S, ElemType e){    //将元素e压入栈，这里e只是一个形参而已

    ElemType *newbase;        //定义中间变量

    if(S.top>= S.size){        //S.top如果指向最后一个不存储元素的地址时，即S.top大于

        newbase = (ElemType*)realloc(S.elem, //等于S.size时，就表示栈满了

    (S.size + S.increment)*sizeof(ElemType)); //通过realloc动态扩容

     

    if(NULL == newbase) return OVERFLOW; //判断扩容是否成功

    S.elem = newbase;      //扩容成功后才将中间变量的值指向S.elem，防止扩容失败时，

    S.size = S.size + S.increment;     //S.elem指向一个不是原来的位置

    }

    S.elem[S.top] = e;    //将e元素入栈

    S.top++;              //使S.top加1，表示指向的是栈顶位标

    return OK;            //上面操作正常后返回1

}

7.出栈

    代码如下：


1

2

3

4

5

Status Pop_Sq(SqStack &S, ElemType &e){    //栈顶元素出栈，赋给元素e

    if(0 == S.top) return ERROR;    

    e = S.elem[--S.top];    //e出栈，并将S.top减1

    return OK;

}

8.进制转换的函数

    其实上面的步骤操作都是为了创建一个顺序栈和定义顺序栈的操作而已，并对可能出现的各种情况做一些相应的举措，完毕后，下面就要使用上面创建的顺序栈以及栈的操作接口了，即在数制转换函数（这里是十进制转八进制）中使用上面的操作接口，代码如下：


1

2

3

4

5

6

7

8

9

10

11

12

13

14

void Converstion(int N){

    SqStack S;

    ElemType e;

    InitStack_Sq(S, 10, 5);    //栈S的初始容量置为10，每次扩容容量为5

     

    while(N != 0){

        Push_Sq(S, N%8);   //将N除以8的余数入栈

        N /= 8;            //N取值为其除以8的商

    }                          //理论基础为除8取余法

     

    while(StackEmpty_Sq(S) == FALSE){

        Pop_Sq(S, e);    //依次输出栈中的余数，并赋给元素e

        printf("%d", e); //打印元素

    }

9.main函数

    进制转换函数调用栈操作的接口函数，以实现在数制转换过程中栈的操作；main函数调用数制转换函数，以实现数制的转换，代码如下：


1

2

3

4

5

int main(void){

    printf("Enter a number:");scanf("%d",&num);

    Converstion(num);

    printf("\n");

}

二、执行

    有了上面的代码后，就可以在编译器中编译执行了，这里我是用c free 5来进行程序代码的编译：


（1）输入的数为1348时的结果：


（2）输入的数为2526时的结果：

三、完整的代码

    下面把代码都放在一起：


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

#include<stdio.h>

#include<stdlib.h>

#define OVERFLOW -1

#define ERROR 0

#define FALSE 0

#define TRUE 1

#define OK 1

 

typedef int ElemType;

typedef int Status;

 

typedef struct{

    ElemType *elem;

    int top;

    int size;

    int increment;

} SqStack;

 

Status InitStack_Sq(SqStack &S, int size, int inc){

    S.elem = (ElemType*)malloc(size*sizeof(ElemType));

    if(S.elem == NULL) return OVERFLOW;

    S.top = 0;

    S.size = size;

    S.increment = inc;

    return OK;

}

 

Status StackEmpty_Sq(SqStack S){

    if(S.top == 0)

        return TRUE;

    else

        return FALSE;

}

 

Status Push_Sq(SqStack &S, ElemType e){

    ElemType *newbase;

    if(S.top>= S.size){

        newbase = (ElemType*)realloc(S.elem,

    (S.size + S.increment)*sizeof(ElemType));

     

    if(NULL == newbase) return OVERFLOW;

    S.elem = newbase;

    S.size = S.size + S.increment;

    }

    S.elem[S.top] = e;

    S.top++;

    return OK;

}

 

Status Pop_Sq(SqStack &S, ElemType &e){

    if(0 == S.top) return ERROR;

    e = S.elem[--S.top];

    return OK;

}

 

void Converstion(int N){

    SqStack S;

    ElemType e;

    InitStack_Sq(S, 10, 5);

     

    while(N != 0){

        Push_Sq(S, N%8);

        N /= 8;

    }

     

    while(StackEmpty_Sq(S) == FALSE){

        Pop_Sq(S, e);

        printf("%d", e);

    }

}

 

int main(void){

    int num;

    printf("Enter a number:");scanf("%d",&num);

    Converstion(num);

    printf("\n");

}
时间： 2024-10-02 02:11:35

【数据结构之旅】顺序栈的定义、初始化、空栈判断、入栈、出栈操作的相关文章

【数据结构之旅】顺序栈入门操作

说明:     书中已有关于顺序栈的类型定义.栈初始化.入栈操作,显然这些都是比较理论的算法,书中并没有给出一个完整可以执行的例子,这对初学者学习在理解上会有一定的难度,因此,需要编写一个简单的例子来理解栈的最基本操作. 1.程序功能     通过使用栈来编写一个程序,实现两个数的交换. 2.程序代码及注释     代码及注释如下: 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 3

N个数依次入栈，出栈顺序有多少种？

对于每一个数来说,必须进栈一次.出栈一次.我们把进栈设为状态'1',出栈设为状态'0'.n个数的所有状态对应n个1和n个0组成的2n位二进制数.由于等待入栈的操作数按照1‥n的顺序排列.入栈的操作数b大于等于出栈的操作数a(a≤b),因此输出序列的总数目=由左而右扫描由n个1和n个0组成的2n位二进制数,1的累计数不小于0的累计数的方案种数. 在2n位二进制数中填入n个1的方案数为C(2n,n),不填1的其余n位自动填0.从中减去不符合要求(由左而右扫描,0的累计数大于1的累计数)的方案数即为所

剑指offer：栈的压入弹出序列

剑指offer上的第22题,九度OJ上AC. 题目描述: 输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序.假设压入栈的所有数字均不相等.例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列. 输入: 每个测试案例包括3行: 第一行为1个整数n(1<=n<=100000),表示序列的长度. 第二行包含n个整数,表示栈的压入顺序. 第三行包含n个整数,表示栈的弹出顺序

android中Activity的singletask模式弹出栈的问题

问题描述 android中Activity的singletask模式弹出栈的问题 07-14 17:48:53.218: E/First(8272): onDestroy 07-14 17:48:53.226: E/Second(8272): onDestroy 07-14 17:48:53.226: E/Third(8272): onPause 07-14 17:48:53.250: E/MAIN(8272): onRestart 07-14 17:48:53.250: E/MAIN(8272

小菜一步一步学数据结构之(五)顺序栈

定义 只能在表的一端(栈顶)进行插入和删除运算的线性表 逻辑结构 一对一关系 存储结构 用顺序栈或链栈存储均可,但以顺序栈更常见 运算规则 只能从栈顶运算,且访问结点时依照后进先出(LIFO)或后进后出(FILO)的原则 实现方法 关键是编写入栈和出栈函数,具体实现依顺序栈或链栈的不同而不同 基本操作 入栈 出栈 读栈顶元素值 建栈 判断栈满 栈空 栈与一般线性表的区别 栈是一种特殊的线性表,它只能在表的一端(栈顶)进行插入或删除运算 ** 一般线性 表 栈 逻辑结构 一对一 一对一 存储结构

c++-数据结构 栈的定义 栈的定义

问题描述 数据结构 栈的定义 栈的定义 定义:栈是限定仅在表头进行插入和删除操作的线性表. 栈定义用的是数组 那为什么只能在头插入和删除 实际上到底什么啊 解决方案 只能在栈顶操作只是栈的定义要求是这样的,这样就实现了"先进后出"的效果.你应该发现普通链表.栈.队列这三种结构本质是相同的,只是人为规定只能在一端或者两端操作. 你如果直接对栈底进行操作,当然是可以的,只是这种数据结构已经不能称之为"栈"了. 如果从编程角度来说的话,假设栈是一个类,那么这个类只提供了p

归并排序-数据结构C语言顺序表的排序和删除问题

问题描述 数据结构C语言顺序表的排序和删除问题 顺序表定义的长度为10000,此时程序可以正常运行:把顺序表长度改成500000,程序出错,不能运行.求问大神是哪里出了错误,还是要提高存储上限?如何改正?#include #include #include typedef int ElemType; #define MAX 10000 typedef struct{ ElemType *elem; int length; }SqList; void InitList(SqList &L){ L.

一个堆栈中先后有1 2 3 4入栈，请问可能的出栈序列？数据结构作业，谢谢

问题描述 一个堆栈中先后有1 2 3 4入栈,请问可能的出栈序列?数据结构作业,谢谢 一个堆栈中先后有1 2 3 4入栈,请问可能的出栈序列?数据结构作业,谢谢 解决方案 14321342132423412431214321343421324132144321 解决方案二: 有个东西叫Catalan数,可以计算出所有出栈情况个数,设入栈序列为I(n):12...n,则I(n)有C(2nn)-C(2nn-1)个出栈序列.具体多少个你可以根据公式自己算,这样不会落下. 解决方案三: 你理解栈先进后出

数据结构 递归与栈-求大神指导调用递归函数中的栈是怎么运行的

问题描述 求大神指导调用递归函数中的栈是怎么运行的 回溯法与树的遍历 回溯法:其求解过程实质是一个先序遍历一棵"状态树"的过程,只是这棵树不是遍历前预先建立的,而 是隐含在遍历过程中. 题目描述:求含n个元素的集合的幂集. 例:A={1,2,3},则A的幂集为{{1,2,3},{1,2},{1, 3},{2,3},{1},{2},{3},{}} 解题思路:求幂集的过程可看成是依次对集合A中的元素进行取或舍的过程. 选择合适的数据结构--假设以线性表表示集合. 树根结点表示幂集元素的初始