堆栈的数组实现

堆栈的抽象数据类型定义为:
类型名称: 堆栈(Stack)
数据对象集: 一个有0个或多个元素的又穷线性表
操作集: 对与一个具体长度为正整数maxSize的堆栈, 堆栈中元素的类型为elementType,
堆栈的基本操作主要有:
(1) ptr_stack(int maxSize): 生成空栈, 其最大长度为maxSize
(2) int isFull(ptr_stack ptr): 判断栈是否已满, 若栈中元素等于maxSize时返回true,
否则返回false
(3) int push(ptr_stack ptr, elementType x): 将元素x压入栈. 若栈已满则返回false,
否则将元素x压入堆栈顶并返回true
(4) int pop(ptr_stack ptr): 删除并返回栈顶元素. 若堆栈为空则返回错误信息.

#include <stdio.h>

#define true 1 // 表示真
#define false 0 // 表示假

typedef int elementType;

struct s_stack {
    elementType *data; // 数据
    int top; // 栈顶指针(栈空指向-1)
    int maxSize; // 堆栈的最大容量
};

typedef struct s_stack stack;
typedef struct s_stack* ptr_stack;

// 函数声明
ptr_stack createStack (int maxSize);
int isFull (ptr_stack ptr);
int push (ptr_stack ptr, elementType x);
void print (ptr_stack ptr);
elementType pop (ptr_stack ptr);

int main () {
    int i;
    ptr_stack p_stack;
    p_stack = createStack(20);

    /* 入栈测试开始 */
    for (i=2; i<30; i+=3) {
        push(p_stack, i);
    }
    print(p_stack);
    /* 入栈测试结束 */

    /* 出栈测试开始 */
    int popValue = pop(p_stack);
    printf("出栈的元素是: %d
", popValue);
    print(p_stack);
    /* 出栈测试结束 */
    return 0;
}

// 生成空栈
ptr_stack createStack (int maxSize) {
    ptr_stack ptr = (stack*)malloc(sizeof(stack));
    ptr->data = (elementType*)malloc(sizeof(elementType) * maxSize);
    ptr->top = -1; // 栈空时, top = -1
    ptr->maxSize = maxSize;
    return ptr;
}

// 判断栈是否满
int isFull (ptr_stack ptr) {
    if (ptr->top == ptr->maxSize - 1) {
        return true;
    } else {
        return false;
    }
}

// 入栈
int push (ptr_stack ptr, elementType x) {
    if (isFull(ptr)) {
        printf("栈满

");
        return false;
    }

    ptr->top += 1;
    ptr->data[ptr->top] = x;
    return true;
}

// 打印
void print (ptr_stack ptr) {
    int i;
    printf("当前栈的长度: %d
", ptr->top + 1);
    for (i=0; i<=ptr->top; i++) {
        printf("%d
", ptr->data[i]);
    }
    printf("
");
}

// 出栈
// 返回栈顶元素, 并把栈顶指针-1
elementType pop (ptr_stack ptr) {
    // 先判断栈是否为空
    if (ptr->top == -1) {
        printf("栈空

");
        return -888; // -888 是自定义的特殊值, 必须是正常栈元素
        // 不可能取到得值
    }

    ptr->top = ptr->top - 1;
    return ptr->data[ptr->top + 1]; // 返回出栈元素的值
}