一、概念

栈是一种LIFO（last in first out，后进先出）的线性表。

二、数据结构

数组实现：

#define MAX_LEN 100
struct Stack {
    int arr[MAX_LEN];
    int top;
};

链表实现：

struct Node {
    int value;
    Node* next;
};

struct Stack {
    Node *top;
    int size;
};

三、相关操作

• 元素入栈
• 元素出栈
• 返回栈顶元素
• 返回栈中元素个数

四、实现

数组实现

#include<stdio.h>
#define MAX_LEN 100

struct Stack {
    int arr[MAX_LEN];
    int top;
};

void initStack(Stack *stack) { //初始化栈
    stack->top = 0;
}

void push(Stack *stack, int value) { //元素入栈
    stack->arr[stack->top] = value;
    stack->top++;
}

int pop(Stack *stack) { //元素出栈
    if(stack->top <= 0) {
        return -1;
    }

    stack->top--;
    return stack->arr[stack->top];
}

int top(Stack *stack) { //返回栈顶元素
    if(stack->top <= 0) {
        return -1;
    }   

    return stack->arr[stack->top - 1];
}

int size(Stack *stack) { //返回栈中元素个数
    return stack->top;
}

void printStack(Stack *stack) {
    printf("printStack: ");
    for(int i=stack->top-1; i>=0; i--) {
        printf("%d ", stack->arr[i]);
    }
    printf("\n");
}

void main() {
    Stack stack;
    initStack(&stack);
    printStack(&stack);

    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);
    push(&stack, 40);
    push(&stack, 50);
    printStack(&stack);

    printf("pop: %d\n", pop(&stack));
    printf("pop: %d\n", pop(&stack));
    printStack(&stack);

    printf("top: %d\n", top(&stack));
    printStack(&stack);

    printf("size: %d\n", size(&stack));
}

链表实现

#include<stdio.h>
#include<malloc.h>

struct Node {
    int value;
    Node* next;
};

struct Stack {
    Node* top;
    int size;
};

Node* mallocNode() { //申请结点内存
    Node* node = (Node*)malloc(sizeof(Node));
    return node;
}

void initStack(Stack *stack) { //初始化栈
    Node* node = mallocNode();
    node->value = -1;
    node->next = NULL;
    stack->top = node;
    stack->size = 0;
}

void push(Stack *stack, int value) { //元素入栈
    Node* node = mallocNode();
    node->value = value;
    node->next = stack->top->next;
    stack->top->next = node;
    stack->size++;
}

Node* pop(Stack *stack) { //元素出栈
    if(stack->size == 0) {
        return NULL;
    }

    Node* p = stack->top->next;
    stack->top->next = stack->top->next->next;
    stack->size--;
    return p;
}

Node* top(Stack *stack) { //返回栈顶元素
    if(stack->size == 0) {
        return NULL;
    }

    return stack->top->next;
}

int size(Stack *stack) { //返回栈中元素个数
    return stack->size;
}

void printStack(Stack *stack) { //打印
    printf("printStack: ");
    Node* p = stack->top->next;
    while(p != NULL) {
        printf("%d ", p->value);
        p = p->next;
    }
    printf("\n");
}

void freeStack(Stack *stack) { //释放栈内存
    Node *p, *q;
    p = stack->top->next;
    stack->top->next = NULL;
    stack->size = 0;
    while(p != NULL) {
        q = p;
        p = p->next;
        free(q);
    }
}

void main() {
    Stack stack;
    initStack(&stack);
    printStack(&stack);

    Node* node =  pop(&stack);
    if(node != NULL) {
        printf("pop: %d\n", node->value);
        free(node);
    }
    printStack(&stack);

    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);
    push(&stack, 40);
    push(&stack, 50);
    printStack(&stack);

    node =  pop(&stack);
    if(node != NULL) {
        printf("pop: %d\n", node->value);
        free(node);
    }
    node =  pop(&stack);
    if(node != NULL) {
        printf("pop: %d\n", node->value);
        free(node);
    }
    printStack(&stack);

    node =  top(&stack);
    if(node != NULL) {
        printf("top: %d\n", node->value);
    }
    printStack(&stack);

    printf("size: %d\n", size(&stack));

    freeStack(&stack);
    printStack(&stack);
}