定义

堆栈(英语:Stack)又称为栈或堆叠,是计算机科学中一种特殊的串列形式的抽象数据类型,其特殊之处在于只能允许在链表或数组的一端(称为堆栈顶端指针,英语:Top)进行加入数据(英语:Push)和输出数据(英语:Pop)的运算。由于堆栈数据结构只允许在一端进行操作,因而按照后进先出(LIFO, Last In First Out)的原理运作。

实现:

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

#define OK 1
#define NONONO -1;
typedef int Element_type; //定义 Element_type 类型,即栈数据类型为 int
typedef int Status;

typedef struct STACK_NODE
{
    Element_type data;
    struct STACK_NODE *next;
} StackNode, *Stack_pointer;

typedef struct
{
    Stack_pointer top;
} Stack;

Status StackInit(Stack *S);
// 删除堆栈
Status StackDestroy(Stack *S);
//  清除堆栈
Status StackClear(Stack *S);
//  栈空
Status isStackEmpty(const Stack S);
//  将元素压入栈顶
Status StackPush(Stack *S, Element_type value);
//  删除栈顶元素
Status StackPop(Stack *S);
//  返回栈顶元素的值
Status StackGetTop(const Stack S, Element_type *x);
//  返货堆栈长度
Status StackLength(const Stack S);
//  遍历堆栈
void StackTrave(const Stack S);

Status StackInit(Stack *S)
{
    S->top = (Stack_pointer)malloc(sizeof(StackNode));
    assert(S->top != NULL);
    S->top->next = NULL;
    return OK;
}

Status StackDestroy(Stack *S)
{
    Stack_pointer tmp;
    while (S->top)
    {
        tmp = S->top->next;
        free(S->top);
        S->top = tmp;
    }
    return OK;
}

Status StackClear(Stack *S)
{
    StackDestroy(S);
    StackInit(S);
}

Status isStackEmpty(const Stack S)
{
    return S.top->next == NULL;
}

Status StackPush(Stack *S, Element_type value)
{
    StackNode *p;
    p = (StackNode *)malloc(sizeof(StackNode));
    assert(p != NULL);
    p->data = value;
    p->next = S->top->next;
    S->top->next = p;
    return OK;
}

Status StackPop(Stack *S)
{
    StackNode *tmp;
    if (!isStackEmpty(*S))
    {
        tmp = S->top;
        S->top = tmp->next;
        free(tmp);
    }
}

Status StackGetTop(const Stack S, Element_type *x)
{
    assert(!isStackEmpty(S));
    *x = S.top->next->data;
    return OK;
}

Status StackLength(const Stack S)
{
    int i;
    StackNode *p = S.top->next;
    while (p != NULL)
    {
        i++;
        p = p->next;
    }
    return i;
}

void StackTrave(const Stack S)
{
    printf("Stack: \n");
    StackNode *p = S.top->next;
    for (; p;)
    {
        printf("| %d |\n", p->data);
        p = p->next;
    }
    printf("\n");
}

void test_stack()
{
    Stack S;
    if (StackInit(&S))
    {
        Element_type temp;
        printf("stack init success\n");
        if (isStackEmpty(S))
            printf("stack is empty\n");
        printf("stack's length is %d\n", StackLength(S));
        for (int i = 0; i < 10; i++)
            StackPush(&S, i);
        StackTrave(S);
        printf("stack's length is %d\n", StackLength(S));
        if (StackGetTop(S, &temp))
            printf("The top element is %d\n", temp);
        StackTrave(S);
        StackGetTop(S, &temp);
        StackPop(&S);
        printf("deleted element is %d\n", temp);
        StackTrave(S);
        printf("stack's length is %d\n", StackLength(S));
        StackPush(&S, 99);
        printf("insert 99 to stack\n");
        StackTrave(S);
        printf("stack's length is %d\n", StackLength(S));
        if (StackDestroy(&S))
            printf("\ndestroy success\n");
    }
}
int main(void)
{
    test_stack();
    return 0;
}


如有错误还请 dalao 指正


Leave a Reply

Your email address will not be published. Required fields are marked *