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

// Array Stack Implementation
#include<stdio.h>
 
#define MaxSize 50
 
typedef struct Stack_Array{
    int data[MaxSize];
    int top;
}Sqstack,*pSqstack;
 
void Initstack();  // Initialize
int Isempty();     // Check if stack is empty
int Push();        // Push
int Pop();         // Pop
int Gettop();      // Get top element
 
int main(void)     // Test
{
    int val;
    Sqstack s1;
    pSqstack ps1=&s1;
    Initstack(&s1);  // Initialize
 
    if(Isempty(&s1))  // Check if stack is empty
        printf("Stack is empty!\n");
    else printf("Stack is not empty!\n");
 
    printf("Enter value to push onto stack");    // Push 1
    scanf("%d",&val);
    Push (ps1,&val);
 
    printf("Enter value to push onto stack");    // Push 2
    scanf("%d",&val);
    Push (ps1,&val);
 
    if(Isempty(ps1))        // Check if stack is empty
        printf("Stack is empty!\n");
    else printf("Stack is not empty!\n");
 
    if(Gettop(ps1,&val))    // Get top element
        printf("Top value is %d\n",val);
    else printf("Failed to get top element!\n");
 
    if(Pop(ps1,&val))    // Pop
        printf("Pop successful, popped element is %d\n",val);
    else printf("Pop failed!\n");
 
    return 0;
}
// Initialize
void Initstack (pSqstack ps1)
{
    ps1->top=-1;
    return;
    
// Check if stack is empty
int    Isempty(pSqstack ps1)
    
    if(ps1->top==-1)
        return 1;
    else return 0;
    
// If stack not full, push element
int    Push(pSqstack ps1,int *val)//*val: accepts an address (int *(&val    )
    
    if(ps1->top==MaxSize)
        return 0;
    else
    {
        ps1->top++;
        ps1->data[ps1->top]=*val;// The value is passed here; *val is *(&val), where &val is input by the calling function.
                // Can also be written as ps1->data[++ps1->top]=*val; it must be ++ps1->top
        return 1;
    }
}
// If stack not empty, pop element and return it in val
int Pop(pSqstack ps1,int *val)
{
    if(Isempty(ps1))
        return 0;
    else
    {
        *val=ps1->data[ps1->top--];
        return 1;
    }
}
// Get top element, return it in val
int Gettop(pSqstack ps1,int *val)
{
    if(Isempty(ps1))
        return 0;
    else 
    {
        *val=ps1->data[ps1->top];
        return 1;
    }
}

  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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151

// Linked List Stack Implementation
#include <stdio.h>
#include <stdlib.h>

#define Stack_Init_Size 10 // Initial max length of the stack
#define StackIncrement 10 // Length to add if max stack space is insufficient
typedef int ElemType;
typedef int Status;

typedef struct {
    ElemType *base; // Base pointer of the stack
    ElemType *top; // Top pointer of the stack
    int stack_size; // Maximum length of the stack
} SqStack;

// Initialize stack
Status InitStack(SqStack *S) {
    // Allocate initial space
    S->base = (ElemType *) malloc(Stack_Init_Size * sizeof(ElemType));
    if (!S->base) {
        exit(0);
    }
    S->top = S->base; /// Top and base pointers are the same
    S->stack_size = Stack_Init_Size; // Max stack length equals initial length
    return 1;
}

// Check if stack is empty; just compare top and base pointers
Status EmptyStack(SqStack *S) {
    return S->base == S->top;
}

// Get actual stack length; top - base pointer gives length
Status LengthStack(SqStack *S) {
    if (S->top == S->base) {
        return 0;
    }
    return (Status) (S->top - S->base);
}

// Get top element; parameter e stores the top element
Status GetTopStack(SqStack *S, ElemType *e) {
    if (S->top == S->base) {
        return 0;
    } 
    *e = *(S->top - 1);
    return 1;
}

// Push element; parameter e is the element to push
Status PushStack(SqStack *S, ElemType e) {
    // If max stack length is not enough, reallocate to increase size
    if (S->top - S->base >= S->stack_size) {
        S->base = (ElemType *)realloc(S->base, (S->stack_size + StackIncrement) * sizeof(ElemType));
        if (!S->base) {
            return 0;
        }
        // Top pointer is base pointer + previous max stack length
        S->top = S->base + S->stack_size;
        // Current max stack length is sum of previous max length and increment
        S->stack_size += StackIncrement;
    }
    *S->top++ = e; // Assign first, then move top pointer up
    return 1;
}

// Pop element; parameter e stores the popped element
Status PopStack(SqStack *S, ElemType *e) {
    if (S->base == S->top) {
        return 0;
    }
    *e = *--S->top; // Move top pointer down first, then assign
    return 1;
}

// Destroy stack; free stack space, set top and base pointers to NULL, length to 0
Status DestroyStack(SqStack *S) {
    free(S->base);
    S->base = S->top = NULL;
    S->stack_size = 0;
    return 1;
}

// Traverse stack; print each element sequentially
Status StackTraverse(SqStack *S) {
    ElemType *p;

    if (S->top == S->base) {
        printf("Stack is empty.\n");
        return 0;
    }
    p = S->top;
    // Traverse from top downwards
    while (p > S->base) {
        p--;
        printf("%d ", *p);
    }
    printf("\n");
    return 1;
}

int main() {
    SqStack q, *S;
    S = &q;

    int i, n, e;

    printf("Create an empty Stack :\n");
    InitStack(S);

    printf("Enter the length of the Stack :\n");
    scanf("%d", &n);

    for (i = 1; i <= n; i++) {
        scanf("%d", &e);
        PushStack(S, e);
    }
    printf("Is the stack empty?\n");

    if (EmptyStack(S)) {
        printf("Yes!\n");
    } else {
        printf("No!\n");
    }
    printf("The length of stack is %d.\n", LengthStack(S));

    printf("The stack is :\n");
    StackTraverse(S);

    GetTopStack(S, &e); // e is already passed by reference, no need to assign return value to e.
    printf("The top data is %d.\n", e);

    printf("Enter the data to push onto the stack :\n");
    scanf("%d", &e);
    PushStack(S, e);
    printf("The new stack is :\n");
    StackTraverse(S);

    printf("Popping the top data : ");
    PopStack(S, &e); // e is already passed by reference, no need to assign return value to e.
    printf("%d\n", e);

    printf("The new stack is :\n");
    StackTraverse(S);

    printf("Destroying the stack :\n");
    DestroyStack(S);
    StackTraverse(S);

    return 0;
}