栈是一种线性数据结构，顺序可能是 LIFO（后进先出）或 FILO（先进先出）。
堆栈主要有三个基本操作：
1、push，把元素压入栈
2、pop，从栈中弹出元素（同时从栈中移除），最后加入的第一个被弹出
3、peek 或 top，返回堆栈顶部的元素
4、isEmpty，如果 stack 为空则返回 true，否则返回 false
如何理解堆栈？
堆栈有许多现实生活中的例子。考虑在食堂中堆叠在一起的碟子，位于顶部的碟子是第一个被移除的，放置在最底部的碟子在堆中保持最长时间。
堆栈操作的时间复杂度：
push()，pop()，isEmpty() 和 peek() 都需要 O(1) 时间。我们不会在任何这些操作中运行任何循环。
实现：
有两种方法来实现堆栈：
1、使用数组
2、使用链表
使用数组实现堆栈
优点：易于实施。存取操作不涉及指针
缺点：不是动态的。不会在运行时根据需要增长和缩小。
//// 栈的数组实现// Created by ruby on 2019/1/17.//#include#include #include // 保存栈的数据结构struct Stack { int top; int capacity; int* array;};// 根据指定大小创建栈, 初始化大小为 0, 容量为 capacitystruct Stack* createStack(unsigned capacity) { struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack)); stack->top = -1; stack->capacity = capacity; stack->array = (int*)malloc(capacity * sizeof(int)); return stack;}// 栈是否已满int isFull(struct Stack* stack) { return stack->top == stack->capacity - 1;}// 栈是否为空int isEmpty(struct Stack* stack) { return stack->top == -1;}// 添加 item 到栈中void push(struct Stack* stack, int item) { if (isFull(stack)) { printf("stack is full\n"); return; } stack->array[++stack->top] = item;}// 从栈中弹出一个元素int pop(struct Stack* stack) { if (isEmpty(stack)) { printf("stack is empty\n"); return -1; } return stack->array[stack->top--];}int main(){ struct Stack* stack = createStack(100); push(stack, 10); push(stack, 20); push(stack, 30); printf("%d popped from stack\n", pop(stack)); return 0;}
使用链表实现堆栈
优点：堆栈的链表实现可以根据运行时的需求增长和缩小。
缺点：由于需要指针记录元素地址，需要额外的内存。
#include#include #include struct StackNode { int data; struct StackNode* next;};struct StackNode* newNode(int data) { struct StackNode* stackNode = (struct StackNode*)malloc(sizeof(struct StackNode)); stackNode->data = data; stackNode->next = NULL; return stackNode;}int isEmpty(struct StackNode* root) { return !root;}void push(struct StackNode** root, int data) { struct StackNode* stackNode = newNode(data); stackNode->next = *root; *root = stackNode; printf("%d pushed to stack\n", data);}int pop(struct StackNode** root) { if (isEmpty(*root)) { return INT_MIN; } struct StackNode* temp = *root; *root = (*root)->next; int popped = temp->data; free(temp); return popped;}int peek(struct StackNode* root) { if (isEmpty(root)) return INT_MIN; return root->data;}int main(){ struct StackNode* root = NULL; push(&root, 10); push(&root, 20); push(&root, 30); printf("%d popped from stack\n", pop(&root)); printf("Top element is %d\n", peek(root)); return 0;}