栈

栈

性质

• 先进后出
• FILO : first in last out
• LIFO : last in first out

结构定义

typedef struct Stack {
    int *data;
    int size, top;
} Stack;

结构操作

• 入栈/压栈：
• 出栈/弹栈：

Stack *init_Stack(int);
int top(Stack *);
int empty(Stack *);
int expand(Stack *);
void clear_Stack(Stack *);
int push(Stack *, int);
int pop(Stack *);
int top(Stack *);
void output(Stack *);

代码演示

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

typedef struct Stack {
    int *data;
    int size, top;
} Stack;

Stack *init_Stack(int);
int top(Stack *);
int empty(Stack *);
int expand(Stack *);
void clear_Stack(Stack *);
int push(Stack *, int);
int pop(Stack *);
int top(Stack *);
void output(Stack *);

int main() {
    srand(time(0));
    #define MAX_N 20
    Stack *s = init_Stack(1);
    for (int i = 0; i < MAX_N; i++) {
        int op = rand() % 4;
        int val = rand() % 100;
        switch (op) {
            case 0 :
            case 1 :
            case 2 : {
                printf("压栈元素：%d, %s\n", val, push(s, val) ? "压入成功" : "压入失败");
            } break;
            
            case 3 : {
                if (!empty(s)) {
                    printf("弹栈元素：%d, ", top(s));
                    printf("%s\n", pop(s) ? "弹出成功" : "弹出失败");
                }
            }
        }
        output(s), printf("\n");
    }
    return 0;
}

Stack *init_Stack(int n) { //初始化 
    Stack *s = (Stack *)malloc(sizeof(Stack));
    s->data = (int *)malloc(sizeof(int) * (n));
    s->size = n;
    s->top = -1;
    return s;
} 

int top(Stack *s) {
    return s->data[s->top];
}

int empty(Stack *s) {
    return s->top == -1; 
}
int expand(Stack *s) {
    int extr_size = s->size;
    int *temp;
    while (extr_size) {
        temp = (int *)realloc(s->data, sizeof(int) * (s->size + extr_size));
        if (temp != NULL) break;
        extr_size >>= 1;
    }
    if (temp == NULL) return 0;
//    free(s->data);
    s->data = temp;
    s->size += extr_size;
    return 1;
}

int push(Stack *s, int val) {
    if (s == NULL) return 0;
    if (s->top == s->size - 1) {
        if (!expand(s)) {
            printf("扩容失败, \n");
            return 0;
        }
        printf("扩容成功, 容量：%d\n", s->size);        
    }
    s->data[++(s->top)] = val;
    return 1;
}

int pop(Stack *s) {
    if (s == NULL) return 0;
    if (empty(s)) return 0;
    s->top -= 1;
    return 1;
}


void clear_Stack(Stack *s) {
    if (s == NULL) return ;
    free(s->data);
    free(s);
    return ; 
}

void output(Stack *s) {
    if (s == NULL) return ;
    printf("Stack: [");
    for (int i = 0; i <= s->top; i++) {
        i && printf(", ");
        printf("%d", s->data[i]);
    }
    printf("]\n");
}

栈的应用

• 单调栈 ：临近最大（最小）值
• 单调队列：区间最大（最小）值
• 队列（循环）：树的层序遍历，广度优先搜索（图算法基础）
• 栈：树的深度遍历，深度优先搜索（图算法基础）