栈是一种先进后出（FILO，First-In-Last-Out）的线性表，栈和队列非常相像，但是栈只能在栈顶插入（入栈）和删除（出栈）元素。同样，栈可以由链表和数组来实现。
对于栈这种数据结构，可以用浏览器来解释；比如我们可以把打开一个网站的过程看作是一次入栈操作，而返回上一次浏览的网站就相当于一次出栈操作。
树或栈这种数据结构用于解决 具有完全包含关系的问题；
// 栈的结构定义（顺序表）typedef struct Stack { int *data; int size, top; // size: 栈的容量，top: 标记栈顶元素的位置} Stack;// 栈的结构定义（链表）typedef struct Node { int data; struct Node *next;} Node;typedef struct Stack { Node *top; int length;} Stack;#include <stdio.h>#include <stdlib.h>#include <time.h>#define COLOR(a, b) "\033[" #b "m" a "\033[0m"#define RED(a) COLOR(a, 31)#define GREEN(a) COLOR(a, 32)typedef struct Stack { int *data; int size, top; // size: 栈的容量，top: 虚拟栈顶指针} Stack;Stack *init(int); // 初始化栈空间int top(Stack *); // 获取栈顶元素int empty(Stack *); // 判断栈空间是否为空int push(Stack *, int); // 入栈/压栈int pop(Stack *); // 出栈/弹栈void clear(Stack *); // 清空栈空间void output(Stack *); // 遍历栈空间元素int expand(Stack *); // 扩容int main() { srand(time(0)); #define MAX_OP 20 Stack *s = init(1); for (int i = 0; i < MAX_OP; i++) { int op = rand() % 4; int val = rand() % 100; switch (op) { case 0: case 1: case 2: { printf("push %d to the stack = %d\n", val, push(s, val)); } break; case 3: { if (!empty(s)) { printf("pop %d from the stack = ", top(s)); printf("%d\n", pop(s)); } } break; } output(s), printf("\n"); } #undef MAX_OP return 0;}Stack *init(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 push(Stack *s, int val) { if (s == NULL) return 0; if (s->top == s->size -1) { if (!expand(s)) { printf(RED("fail to expand!\n")); return 0; } printf(GREEN("success to expand! the new size = %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 *s) { if (s == NULL) return ; free(s->data); free(s); return ;}void output(Stack *s) { if (s == NULL) return ; printf("Stack(%d) : [", s->top + 1); for (int i = 0; i <= s->top; i++) { i && printf(", "); printf("%d", s->data[i]); } printf("]\n"); return ;}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; s->data = temp; s->size += extr_size; return 1;}#include <stdio.h>#include <stdlib.h>#include <time.h>typedef struct Node { int data; struct Node *next;} Node;typedef struct Stack { Node *top; int length;} Stack;Node *getNewNode(int);Stack *init_stack();void clear(Stack *);int empty(Stack *);int push(Stack *, int);int pop(Stack *);void output(Stack *);int top(Stack *);int main() { srand(time(0)); #define MAX_OP 20 Stack *s = init_stack(); for (int i = 0; i < MAX_OP; i++) { int op = rand() % 4; int val = rand() % 100; switch (op) { case 0: case 1: case 2: { printf("push %d to the Stack = %d\n", val, push(s, val)); } break; case 3: { if (!empty(s)) { printf("pop %d from the Stack = ", top(s)); printf("%d\n", pop(s)); } } break; } output(s), printf("\n"); } #undef MAX_OP clear(s); return 0;}Node *getNewNode(int val) { Node *p = (Node *)malloc(sizeof(Node)); p->data = val; p->next = NULL; return p;}Stack *init_stack() { Stack *s = (Stack *)malloc(sizeof(Stack)); s->top = NULL; s->length = 0; return s;}void clear(Stack *s) { if (s == NULL) return; Node *p = s->top, *q; while (p != NULL) { q = p->next; free(p); p = q; } free(s); return;}int empty(Stack *s) { return s->top == NULL;}int top(Stack *s) { return s->top->data;}int push(Stack *s, int val) { if (s == NULL) return 0; Node *p = getNewNode(val); p->next = s->top; s->top = p; s->length += 1; return 1;}int pop(Stack *s) { if (s == NULL) return 0; if (empty(s)) return 0; Node *p = s->top; s->top = p->next; free(p); s->length -= 1; return 1;}void output(Stack *s) { if (s == NULL) return; printf("Stack[%d] : ", s->length); for (Node *p = s->top; p; p = p->next) { p != s->top && printf(" "); printf("%d", p->data); } printf("\n"); return;}