链栈

链栈

何为链栈

• 由链表实现的栈

优点

• 插入元素和删除元素时间复杂度都是常数O(1)

实现方法

• 头插法

结构定义

typedef struct Node {
    int data;
    struct Node *next;
} Node;

typedef struct Chain_Stack {
    int length;
    Node head;
} Chain_Stack;

结构操作

Node *getnewNode(int);
int pop(Chain_Stack *);
int top(Chain_Stack *);
void output(Chain_Stack *);
int empty(Chain_Stack *);
int push(Chain_Stack *, int);
void clear_Node(Node *);
void clear_Chain_Stack(Chain_Stack *);
Chain_Stack *init_Stack();

代码演示

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

typedef struct Node {
    int data;
    struct Node *next;
} Node;

typedef struct Chain_Stack {
    int length;
    Node head;
} Chain_Stack;

Node *getnewNode(int);
int pop(Chain_Stack *);
int top(Chain_Stack *);
void output(Chain_Stack *);
int empty(Chain_Stack *);
int push(Chain_Stack *, int);
void clear_Node(Node *);
void clear_Chain_Stack(Chain_Stack *);
Chain_Stack *init_Stack();

int main() {
    srand(time(0));
    #define MAX_N 2200
    Chain_Stack *cs = init_Stack();
    for (int i = 0; i < MAX_N; i++) {
        int op = rand() % 4;
        int val = rand() % 100;
        switch (op) {
            
            
            case 2 : {
                printf("插入元素：%d, %s\n", val, push(cs, val) ? "插入成功" : "失败");
            } break;
            case 1 :
            case 0 :
            case 3 : {
                if (!empty(cs)) {
                    printf("删除元素：%d, ", top(cs));
                    printf("%s\n", pop(cs) ? "删除成功" : "删除失败");
                } else printf("没有元素可以删除\n");
            } break;
        }
        output(cs), printf("\n");
    }
    #undef MAX_N
    clear_Chain_Stack(cs);
    return 0;
}

Node *getnewNode(int val) {
    Node *node = (Node *)malloc(sizeof(Node)); //默认空间申请成功 
    node->data = val;
    node->next = NULL;
    return node;
}

Chain_Stack *init_Stack() {
    Chain_Stack *cs = (Chain_Stack *)malloc(sizeof(Chain_Stack));
    cs->head.next = NULL;
    cs->length = 0; //[0,length); 
    return cs;
} 

int empty(Chain_Stack *cs) {
    //if (cs == NULL) return -1;
    return !(cs->length);
}

int push(Chain_Stack *cs, int val) {
    if (cs == NULL) return 0;
    Node *node = getnewNode(val);
    node->next = cs->head.next;
    cs->head.next = node;
    cs->length += 1;
    return 1;
}

int top(Chain_Stack *cs) {
    //if (cs == NULL) return -1;
    return cs->head.next->data;
}

int pop(Chain_Stack *cs) {
    if (cs == NULL) return 0;

    Node *p = cs->head.next;
    cs->head.next = cs->head.next->next;
    clear_Node(p);
    cs->length -= 1;
    return 1;
}

void clear_Node(Node *node) {
    if (node == NULL) return ;
    free(node);
    return ;
}

void clear_Chain_Stack(Chain_Stack *cs) {
    if (cs == NULL) return ;
    Node *p = cs->head.next, *temp;
    while (p) {
        temp = p->next;
        clear_Node(p);
        p = temp;
    }
    free(cs);
    return ;
}

void output(Chain_Stack *cs) {
    if (cs == NULL) return ;
    printf("Stack(%d)：", cs->length);
    Node *p = cs->head.next;
    for (int i = 0; i < (cs->length); i++) {
        printf("%d->", p->data);
        p = p->next;
    }
    printf("NULL\n");
    return ;
}