數據結構中的棧：概念、操作與實戰

第一部分 棧分類及常見形式

棧是一種遵循后進先出(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;
}

棧作為一種基礎而重要的數據結構，在編譯器設計、操作系統、算法實現等領域有廣泛應用。掌握棧的各種操作和典型應用場景，對于提升編程能力和算法思維至關重要。通過練習這些題目，可以深入理解棧的特性及其解決問題的思路。