数据结构中的栈：概念、操作与实战
第一部分 栈分类及常见形式
栈是一种遵循后进先出(LIFO, Last In First Out)原则的线性数据结构。栈主要有以下几种实现形式：
1. 数组实现的栈（顺序栈）
#define MAX_SIZE 100typedef struct {int data[MAX_SIZE];int top;
} ArrayStack;
2. 链表实现的栈（链式栈）
typedef struct StackNode {int data;struct StackNode* next;
} StackNode;typedef struct {StackNode* top;
} LinkedStack;
3. 动态扩容栈
当栈满时能自动扩容的栈（基于数组实现）
typedef struct {int *data;int top;int capacity;
} DynamicStack;
4. 双栈共享同一存储空间
两个栈共享一个数组空间，从两端向中间生长
typedef struct {int data[MAX_SIZE];int top1; // 栈1的栈顶指针int top2; // 栈2的栈顶指针
} DoubleStack;
第二部分 栈常见操作
1. 初始化栈
// 初始化数组栈
void initArrayStack(ArrayStack *stack) {stack->top = -1;
}// 初始化链式栈
void initLinkedStack(LinkedStack *stack) {stack->top = NULL;
}// 初始化动态栈
void initDynamicStack(DynamicStack *stack, int initialCapacity) {stack->data = (int*)malloc(initialCapacity * sizeof(int));stack->top = -1;stack->capacity = initialCapacity;
}
2. 入栈操作
// 数组栈入栈
void pushArrayStack(ArrayStack *stack, int value) {if(stack->top >= MAX_SIZE - 1) {printf("栈已满\n");return;}stack->data[++stack->top] = value;
}// 链式栈入栈
void pushLinkedStack(LinkedStack *stack, int value) {StackNode* newNode = (StackNode*)malloc(sizeof(StackNode));newNode->data = value;newNode->next = stack->top;stack->top = newNode;
}// 动态栈入栈（带自动扩容）
void pushDynamicStack(DynamicStack *stack, int value) {if(stack->top == stack->capacity - 1) {stack->capacity *= 2;stack->data = (int*)realloc(stack->data, stack->capacity * sizeof(int));}stack->data[++stack->top] = value;
}
3. 出栈操作
// 数组栈出栈
int popArrayStack(ArrayStack *stack) {if(stack->top == -1) {printf("栈为空\n");return -1; // 错误码}return stack->data[stack->top--];
}// 链式栈出栈
int popLinkedStack(LinkedStack *stack) {if(stack->top == NULL) {printf("栈为空\n");return -1; // 错误码}StackNode* temp = stack->top;int value = temp->data;stack->top = stack->top->next;free(temp);return value;
}
4. 查看栈顶元素
// 查看数组栈顶元素
int peekArrayStack(ArrayStack *stack) {if(stack->top == -1) {printf("栈为空\n");return -1;}return stack->data[stack->top];
}// 查看链式栈顶元素
int peekLinkedStack(LinkedStack *stack) {if(stack->top == NULL) {printf("栈为空\n");return -1;}return stack->top->data;
}
5. 判断栈是否为空
// 判断数组栈是否为空
int isEmptyArrayStack(ArrayStack *stack) {return stack->top == -1;
}// 判断链式栈是否为空
int isEmptyLinkedStack(LinkedStack *stack) {return stack->top == NULL;
}
6. 获取栈大小
// 获取数组栈大小
int sizeArrayStack(ArrayStack *stack) {return stack->top + 1;
}// 获取链式栈大小
int sizeLinkedStack(LinkedStack *stack) {int count = 0;StackNode* current = stack->top;while(current != NULL) {count++;current = current->next;}return count;
}
第三部分 栈编程题例子
1. 括号匹配检查
int isValidParentheses(char* s) {char stack[10000];int top = -1;for(int i = 0; s[i] != '\0'; i++) {if(s[i] == '(' || s[i] == '[' || s[i] == '{') {stack[++top] = s[i];} else {if(top == -1) return 0;char topChar = stack[top--];if((s[i] == ')' && topChar != '(') ||(s[i] == ']' && topChar != '[') ||(s[i] == '}' && topChar != '{')) {return 0;}}}return top == -1;
}
2. 逆波兰表达式求值
int evalRPN(char** tokens, int tokensSize) {int stack[10000];int top = -1;for(int i = 0; i < tokensSize; i++) {if(strcmp(tokens[i], "+") == 0) {int b = stack[top--];int a = stack[top--];stack[++top] = a + b;} else if(strcmp(tokens[i], "-") == 0) {int b = stack[top--];int a = stack[top--];stack[++top] = a - b;} else if(strcmp(tokens[i], "*") == 0) {int b = stack[top--];int a = stack[top--];stack[++top] = a * b;} else if(strcmp(tokens[i], "/") == 0) {int b = stack[top--];int a = stack[top--];stack[++top] = a / b;} else {stack[++top] = atoi(tokens[i]);}}return stack[top];
}
3. 用栈实现队列
typedef struct {int inStack[MAX_SIZE];int outStack[MAX_SIZE];int inTop;int outTop;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* queue = (MyQueue*)malloc(sizeof(MyQueue));queue->inTop = -1;queue->outTop = -1;return queue;
}void push(MyQueue* obj, int x) {obj->inStack[++obj->inTop] = x;
}int pop(MyQueue* obj) {if(obj->outTop == -1) {while(obj->inTop != -1) {obj->outStack[++obj->outTop] = obj->inStack[obj->inTop--];}}return obj->outStack[obj->outTop--];
}int peek(MyQueue* obj) {if(obj->outTop == -1) {while(obj->inTop != -1) {obj->outStack[++obj->outTop] = obj->inStack[obj->inTop--];}}return obj->outStack[obj->outTop];
}int empty(MyQueue* obj) {return obj->inTop == -1 && obj->outTop == -1;
}
4. 最小栈（能在O(1)时间内检索到最小元素的栈）
typedef struct {int dataStack[MAX_SIZE];int minStack[MAX_SIZE];int top;
} MinStack;MinStack* minStackCreate() {MinStack* stack = (MinStack*)malloc(sizeof(MinStack));stack->top = -1;return stack;
}void minStackPush(MinStack* obj, int val) {obj->dataStack[++obj->top] = val;if(obj->top == 0) {obj->minStack[obj->top] = val;} else {obj->minStack[obj->top] = val < obj->minStack[obj->top-1] ? val : obj->minStack[obj->top-1];}
}void minStackPop(MinStack* obj) {obj->top--;
}int minStackTop(MinStack* obj) {return obj->dataStack[obj->top];
}int minStackGetMin(MinStack* obj) {return obj->minStack[obj->top];
}
5. 栈的压入、弹出序列验证
int validateStackSequences(int* pushed, int pushedSize, int* popped, int poppedSize) {if(pushedSize != poppedSize) return 0;int stack[pushedSize];int top = -1;int popIndex = 0;for(int i = 0; i < pushedSize; i++) {stack[++top] = pushed[i];while(top != -1 && stack[top] == popped[popIndex]) {top--;popIndex++;}}return top == -1;
}
6. 每日温度（计算需要等待多少天才能得到更暖和的温度）
int* dailyTemperatures(int* temperatures, int temperaturesSize, int* returnSize) {*returnSize = temperaturesSize;int* result = (int*)malloc(temperaturesSize * sizeof(int));memset(result, 0, temperaturesSize * sizeof(int));int stack[temperaturesSize];int top = -1;for(int i = 0; i < temperaturesSize; i++) {while(top != -1 && temperatures[i] > temperatures[stack[top]]) {int prevIndex = stack[top--];result[prevIndex] = i - prevIndex;}stack[++top] = i;}return result;
}
栈作为一种基础而重要的数据结构，在编译器设计、操作系统、算法实现等领域有广泛应用。掌握栈的各种操作和典型应用场景，对于提升编程能力和算法思维至关重要。通过练习这些题目，可以深入理解栈的特性及其解决问题的思路。