棧
1 概念
-
棧是一種先進後出（FILO，First-In-Last-Out）的線性表，棧和隊列非常相像，但是棧只能在棧頂插入（入棧）和刪除（出棧）元素。同樣，棧可以由鏈表和數組來實現。
-
對於棧這種數據結構，可以用瀏覽器來解釋；比如我們可以把打開一個網站的過程看作是一次入棧操作，而返回上一次瀏覽的網站就相當於一次出棧操作。
-
樹或棧這種數據結構用於解決 具有完全包含關係的問題；
2 基本操作
2.1 結構定義
- 實現棧需要引入1個變量top， 用來標記當前棧頂元素的位置。
// 棧的結構定義（順序表）
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;
2.2 入棧（top+1）
- 判斷當前棧是否已滿，能否繼續插入元素；
- 棧頂標記 top 後移一位；
- 將新元素插入到當前棧頂標記的位置；
2.3 出棧（top-1）
- 判斷當前棧是否為空，能否繼續刪除元素；
- 棧頂標記 top 前移一位；
3 代碼演示
3.1 數組棧
#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;
}
3.2 鏈棧
#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;
}
4 應用
4.1 數列翻轉
- 將數列中的元素依次入棧；
- 將棧頂元素依次出棧，直到棧為空為止；
4.2 表達式中的括號匹配
- 依次遍歷表達式中的字符，當該字符為左括號時，就入棧；當該字符為右括號時，就出棧；
- 在整個表達式遍歷結束時，且當前棧為空，則括號匹配成功，否則，括號匹配失敗；
