数据结构栈的代码实现(C语言)

一 、栈的顺序代码实现

1. 初始化一个空栈

bool InitStack(SqStack *s) {
    s->base = (ElemType *) malloc(STACK_INIT_SIZE * sizeof(ElemType));
    if(s->base == NULL) {
        return false;
    }
    s->top = s->base;
    s->stack_size = STACK_INIT_SIZE;
    return true;
}

2. 判断栈是否为空

bool isEmpty(SqStack *s) {
    return s->base == s->top? true : false;
}

3. 获得栈中元素的个数

int getLength(SqStack *s) {
    return s->top - s->base;
}

4. 打印栈中的元素

void printStack(SqStack *s) {
    while(s->top != s->base) {
        s->top--;
        printf("elems in the stack :%d\n", *(s->top));
    }
}

5. 向栈中插入元素

bool putStack(SqStack *s, ElemType e) {
    //栈已满重新分配存储空间
    if(s->top - s->base >= s->stack_size) {
        s->base = (ElemType *) realloc(s->base,(s->stack_size + STACK_INCREASEMENT)*sizeof(SqStack));
        if(s->base == NULL)
            return false;
        s->top = s->base + s->stack_size;
        s->stack_size += STACK_INCREASEMENT;
    }
    //入栈
    *(s->top) = e;
    s->top++;
    return true;
}

6. 栈中元素出栈

int outStack(SqStack *s) {
    if(isEmpty(s)) return NULL;
    s->top--;
    ElemType e = *(s->top);
    return e;
}

7. 清空栈

bool clearStack(SqStack *s) {
    s->top = s->base;
    return true;
}

8. 主函数

int main()
{
    int n, tmp;
    SqStack S;
    InitStack(&S);
    printf("请输入要入栈的元素个数:");
    scanf("%d",&n);
    for (int i = 0; i < n; i++) {
    printf("请输入第 %d 个需要入栈的元素:",i+1);
    scanf("%d",&tmp);
    putStack(&S, tmp);
    }
    printf("length of S:%d \n",getLength(&S));
    printf("the out stack elem is : %d \n",outStack(&S));
    printf("length of S:%d \n",getLength(&S));
    printStack(&S);

    clearStack(&S);
    printf("the length of stack after cleared : %d", getLength(&S));
    return 0;
}

二 、栈的链式代码实现

1. 初始化一个空栈

void initStack(PSTACK pStack) {

    pStack->pTop = (PNODE) malloc(sizeof(NODE));
    if (NULL != pStack->pTop) {

        pStack->pBottom = pStack->pTop;

        pStack->pTop->pNext = NULL;
    } else {
        printf("内存分配失败!程序退出!\n");
        exit(-1);
    }
    return;
}

2. 向栈中添加元素

void pushStack(PSTACK pStack, int val) {
    //动态创建一个新结点
    PNODE pNew = (PNODE) malloc(sizeof(NODE));
    //设置新结点的数据域的值
    pNew->data = val;
    //将新结点的指针域指向之前建的空节点
    pNew->pNext = pStack->pTop;  //pStack->pTop不能换成pStack->pBottom
    //pTop指向新的结点
    pStack->pTop = pNew;
}

3. 栈中元素出栈

bool popStack(PSTACK pStack, int *pVal) {
    if (isEmpty(pStack)) {
        return false;
    } else {
        //先保存栈顶元素的地址，然后将pTop指向下一元素,最后释放之前栈顶元素的内存
        PNODE rNode = pStack->pTop;
        *pVal = rNode->data;
        pStack->pTop = rNode->pNext;
        free(rNode);
        return true;
    }
}

4. 判断栈是否为空

bool isEmpty(PSTACK pStack) {
    if (pStack->pTop == pStack->pBottom)
        return true;
    else
        return false;
}

5. 遍历栈中的元素

void traverseStack(PSTACK pStack) {
    //将栈顶赋给一个临时结点,因为在遍历栈的时候不能销毁栈
    PNODE pNode = pStack->pTop;
    //循环遍历栈,直到栈底
    while (pStack->pBottom != pNode) {
        printf("%d ", pNode->data);
        pNode = pNode->pNext;
    }
    printf("\n");
    return;
}

6. 清空栈

void clearStack(PSTACK pStack) {
    //栈为空，则退出该函数
    if (isEmpty(pStack)) {
        return;
    } else {
        //两个结点指针变量用来释放栈中元素的内存
        PNODE p = pStack->pTop;
        PNODE q = NULL;
        //循环释放内存
        while (p != pStack->pBottom) {
            q = p->pNext;
            free(p);
            p = q;
        }
        //将栈顶和栈底指向同一个指针域为空的结点
        pStack->pTop = pStack->pBottom;
        return;
    }
}

7. 主函数

int main(void) {
    PSTACK stack;
    int val, param, a;
    initStack(stack);
    printf("请输入入栈的个数:");
    scanf("%d",&a);
    for (int i = 0; i < a; i++) {
        printf("请输入第 %d 个入栈的数:",i+1);
        scanf("%d",&param);
        pushStack(stack, param);
    }
    traverseStack(stack);
    //调用出栈的函数
    if (popStack(stack, &val))
        printf("出栈成功，出栈的元素值为：%d\n", val);
    else
        printf(" 出栈失败!");
    //调用清空栈的函数
    clearStack(stack);
    traverseStack(stack);
    system("pause");
    return 0;
}