堆疊：一種特殊的線性表，其只允許在固定的一端進行插入和洗掉元素操作，進行資料插入和洗掉操作的一端稱為堆疊頂，另一端稱為堆疊底，堆疊中的資料元素遵守后進先出LIFO（Last In First Out）的原則，
順序存盤還是鏈式存盤？
兩種理論上都是可以的，
陣列堆疊
鏈式堆疊
陣列堆疊結構體
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}ST;
函式介面
// 堆疊初始化 指標傳遞
void StackInit(ST* ps);
// 堆疊銷毀
void StackDestroy(ST* ps);
// 壓堆疊
void StackPush(ST* ps, STDataType x);
// 彈堆疊
void StackPop(ST* ps);
// 取堆疊頂元素
STDataType StackTop(ST* ps);
// 判斷堆疊空
bool StackEmpty(ST* ps);
// 堆疊大小
int StackSize(ST* ps);
介面實作
學了順序表和鏈表操作，寫個堆疊已經是easy的了，這里就不多講了，
void StackInit(ST* ps)
{
assert(ps);
ps->a = NULL;
// top=0: top指向堆疊頂元素下一個位置
// top=-1: top指向堆疊頂元素位置
ps->top = 0;
ps->capacity = 0;
}
void StackDestroy(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = ps->top = 0;
}
void StackPush(ST* ps, STDataType x)
{
assert(ps);
// 空間不夠擴容
if (ps->top == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
STDataType* tmp = realloc(ps->a, sizeof(STDataType) * newcapacity);
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
ps->a = tmp;
ps->capacity = newcapacity;
}
ps->a[ps->top] = x;
ps->top++;
}
void StackPop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
ps->top--;
}
bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}
STDataType StackTop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->a[ps->top - 1];
}
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}
堆疊 OJ：20. 有效的括號
括號匹配問題
本題思路也是簡單的:
- 遇到左括號，入堆疊
- 遇到右括號，出堆疊頂元素和右括號比較
但是細節的地方要注意，比如一些容易忽略的記憶體泄漏！
bool isValid(char * s){
ST st;
StackInit(&st);
while(*s)
{
// 遇到左括號：入堆疊
if(*s == '('
|| *s == '{'
|| *s == '[')
{
StackPush(&st, *s);
s++;
}
else
{
// 遇到右括號
// 堆疊不空：彈出堆疊頂元素和右括號比對
// 堆疊空, return false
if(StackEmpty(&st))
{
StackDestroy(&st); // 防止記憶體泄漏
return false;
}
else
{
STDataType x = StackTop(&st);
StackPop(&st);
// 比較
if((x=='(' && *s ==')')
|| (x == '{' && *s == '}')
|| (x == '[' && *s ==']'))
{
s++;
}
else
{
return false;
}
}
}
} // end of while
// 遍歷完了，堆疊仍然不空，說明有左括號沒有匹配
bool ret = StackEmpty(&st);
StackDestroy(&st);
return ret;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/342208.html
標籤：其他
上一篇：（C語言）手撕資料結構之——佇列
下一篇：【資料結構】堆疊