算法设计------栈实现

栈

栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。栈中元素的进出是按后进先出的原则进行，这是栈的重要特征（LIFO–Last In First Out）。

栈的C语言实现

.h文件

typedef struct node{
    int member;//数据域
    struct node * pNext;
}Node,* pNode;

typedef struct stack{
    pNode Top;//栈顶指针
    pNode Bottom;//栈底指针
}Stack, * pStack;

void InitStack(pStack);//初始化
bool Push(pStack,int);//入栈操作
int Pop(pStack);//出栈操作
bool Empty(pStack);//判空
void Clear(pStack);//清空
void TraverseStack(pStack);//遍历

.c文件

void InitStack(pStack);
bool Push(pStack,int);
int Pop(pStack);
bool Empty(pStack);
void clear(pStack);
void TraverseStack(pStack);

void InitStack(pStack ps){
    ps -> Top =  malloc(sizeof(Node));
    if (NULL == ps -> Top) {
        printf("动态分配内存失败");
        exit(-1);
    }else{
        ps -> Bottom = ps -> Top;
        ps -> Top -> pNext = NULL;
    }
    return;
}

bool Push(pStack ps,int num){
    
    pNode newNode = (pNode) malloc(sizeof(Node));
    if (NULL == newNode) {
        printf("动态分配内存失败");
        return false;
    }else{
        newNode -> member = num;
        newNode -> pNext = ps -> Top;
        ps -> Top = newNode;
        return true;
    }
}

bool Empty(pStack ps){
    
    if (ps -> Top == ps -> Bottom) {
        return true;
    }else{
        return false;
    }
}

int Pop(pStack ps){
    int return_val;
    if (Empty(ps)) {
        exit(-1);
    }else{
        return_val = ps -> Top -> member;
        pNode tempNode = ps -> Top;
        ps -> Top = ps -> Top -> pNext;
        free(tempNode);
        return return_val;
    }
}

void TraverseStack(pStack ps){
    pNode traverNode = ps -> Top;
    while (!(traverNode == ps -> Bottom)) {
        printf("%d\n",traverNode -> member);
        traverNode = traverNode -> pNext;
    }
}

void Clear(pStack ps){
    pNode tempNode = NULL;
    while (ps -> Top != ps -> Bottom) {
        tempNode = ps -> Top;
        ps -> Top = ps -> Top -> pNext;
        free(tempNode);
    }
}

测试代码

void testStack (){
    Stack s;
    int i;
    int re_num;
    InitStack(&s);
    
    for (i = 0 ; i < 5; i++) {
        printf("第 %d 个数：\n",i+1);
        if (Push(&s, i + 1)) {
            continue;
        }else{
            printf("进行入栈操作失败！\n");
            exit(-1);
        }
    }
    
    printf("stack after Push\n");
    TraverseStack(&s);
    
    for (int i = 0; i < 3; i ++) {
        re_num = Pop(&s);
        printf("remover %d ",re_num);
    }
    
    printf("stack after Pop\n");
    TraverseStack(&s);
    
    Clear(&s);
    
    printf("stack after clear \n");
    TraverseStack(&s);
}

时间复杂度：push、pop操作的时间复杂度均为 O(1)

如果对你有帮助的话，Star✨下一吧！