顺序堆栈和链式堆栈的实现,用一个数组实现两个堆栈的例子

 

顺序堆栈的实现:

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

#define ERROR -999

typedef int ElementType;
typedef int Position;
typedef struct SNode* PtrToNode;
struct SNode {
    ElementType *Data;    //存储元素的数组
    Position top;        //栈顶指针
    int MaxSize;        //堆栈最大容量
};
typedef PtrToNode Stack;

//生成一个空栈
Stack CreateStack(int MaxSize)
{
    Stack S = (Stack)malloc(sizeof(struct SNode));
    S->Data = (ElementType*)malloc(sizeof(sizeof(struct SNode) * MaxSize));
    S->top = -1;
    S->MaxSize = MaxSize;
    return S;
}

//判断一个栈是否已满
bool IsFull(Stack S)
{
    return S->top == S->MaxSize - 1;
}

//判断一个栈是否为空
bool IsEmpty(Stack S)
{
    return S->top == -1;    //这里我已开始写成了return S->top = -1;所以一直得不到正确结果
}

//压栈,返回是否压栈成功
bool Push(Stack S, ElementType X)
{
    if (IsFull(S))
    {
        printf("The stack is full!\n");
        return false;
    }
    else
    {
        S->Data[++(S->top)] = X;
        return true;
    }
}

//出栈,弹栈,返回弹出的元素
ElementType Pop(Stack S)
{
    if (IsEmpty(S))
    {
        printf("The Stack is Empty!\n");
        return ERROR;
    }
    else
        return (S->Data[(S->top)--]);
}
刚开始对Pop操作的返回值语句return (S->Data[(S->top)--]);存在一点疑惑,为什么程序已经把S->Data[S->top]返回回去了,
S->top还会执行自减操作(我一直认为后置版本的--运算符执行的操作是,先返回-1前的原值,再原值-1),事实上这个运算符是先把原值拷贝一份,然后原值-1,
最后返回副本,所以这条返回语句是没有问题的,因为返回副本之前原值就已经-1了

--运算符的重载实现为:

1 ClassA operator -- (int a)        //为了与前置版本相区别,参数列表中加上int a,但是int a在函数体中不起任何作用,只起区分的作用
2 {
3     ClassA copy = *this;
4     --*this;            //先自加
5     return copy;        //再返回前置版本
6 }

 

链式堆栈的实现:

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <stdbool.h>
 4 
 5 #define ERROR -999
 6 
 7 typedef int ElementType;
 8 typedef struct SNode* PtrToSNode;
 9 struct SNode {
10     ElementType Data;
11     PtrToSNode Next;
12 };
13 
14 typedef PtrToSNode Stack;
15 
16 Stack CreateStack()
17 {
18     Stack S = (Stack)malloc(sizeof(struct SNode));
19     S->Next = NULL;
20     return S;
21 }
22 
23 bool IsEmpty(Stack S)
24 {
25     return (S->Next == NULL);
26 }
27 
28 bool Push(Stack S, ElementType X)
29 {
30     PtrToSNode TmpCell;
31 
32     TmpCell = (PtrToSNode)malloc(sizeof(struct SNode));
33     TmpCell->Data = X;
34     TmpCell->Next = S->Next;
35     S->Next = TmpCell;
36     return true;
37 }
38 
39 ElementType Pop(Stack S)
40 {
41     PtrToSNode FirstCell;
42     ElementType TopElem;
43     if (IsEmpty(S))
44     {
45         printf("Stack is empty!\n");
46         return ERROR;
47     }
48     else
49     {
50         FirstCell = S->Next;
51         TopElem = FirstCell -> Data;
52         S->Next = FirstCell->Next;
53         free(FirstCell);
54         return TopElem;
55     }
56 }
57 
58 int main()
59 {
60     Stack S = CreateStack();
61     Push(S, 3);
62     int a = Pop(S);
63     printf("%d\n", a);
64     return 0;
65 
66 }

 

用一个数组实现两个堆栈的例子:

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <stdbool.h>
 4 
 5 #define ERROR -999
 6 
 7 typedef int ElementType;
 8 typedef int Position;
 9 typedef struct SNode* PtrToNode;
10 struct SNode {
11     ElementType *Data;    //存储元素的数组
12     Position top1;        //栈顶指针
13     Position top2;
14     int MaxSize;        //堆栈最大容量
15 };
16 typedef PtrToNode Stack;
17 
18 //生成一个空栈
19 Stack CreateStack(int MaxSize)
20 {
21     Stack S = (Stack)malloc(sizeof(struct SNode));
22     S->Data = (ElementType*)malloc(sizeof(sizeof(struct SNode) * MaxSize));
23     S->top1 = -1;
24     S->top2 = MaxSize;
25     S->MaxSize = MaxSize;
26     return S;
27 }
28 
29 
30 //压栈,返回是否压栈成功
31 bool Push(Stack S, ElementType X, int Tag)
32 {
33     if (S->top2 - S->top1 == 1)
34     {
35         printf("The stack is full!\n");
36         return false;
37     }
38     else
39     {
40         if (Tag == 1)
41             S->Data[++(S->top1)] = X;
42         else
43             S->Data[--(S->top2)] = X;
44         return true;
45     }
46 }
47 
48 //出栈,弹栈,返回弹出的元素
49 ElementType Pop(Stack S, int Tag)
50 {
51     if (Tag == 1)
52     {
53         if (S->top1 == -1)
54         {
55             printf("The Stack is Empty!\n");
56             return ERROR;
57         }
58         else
59             return S->Data[(S->top1)--];
60     }
61     else
62     {
63         if (S->top2 == S->MaxSize)
64         {
65             printf("Stack 2 is empty!\n");
66             return ERROR;
67         }
68         else
69             return S->Data[(S->top2)++];
70     }
71 }
72 
73 
74 int main()
75 {
76     Stack S = CreateStack(10);
77     Push(S, 2, 1);
78     int a = Pop(S, 1);
79     Push(S, 3, 2);
80     int b = Pop(S, 2);
81     printf("%d %d\n", a, b);
82     return 0;
83 }

 

 

  

 

上一篇:python笔记29-队列Queue


下一篇:SQLServer创建数据库详解