C語言實(shí)現(xiàn)棧的示例代碼
一、了解棧的結(jié)構(gòu)特點(diǎn)
棧是一種特殊的線性表,只允許從一端進(jìn)出數(shù)據(jù),稱為后進(jìn)先出,先進(jìn)后出。
壓棧:棧的插入操作叫做進(jìn)棧/壓棧/入棧,入數(shù)據(jù)在棧頂
出棧:棧的刪除操作叫做出棧。出數(shù)據(jù)也在棧頂
二、具體實(shí)現(xiàn)
由于棧實(shí)質(zhì)是一種線性表,因此可以用兩種方式來實(shí)現(xiàn):順序表 或 鏈表
這里我使用的是類似順序表的方式來實(shí)現(xiàn)。
代碼如下:
typedef char Stacktype; typedef struct Stack { int top; Stacktype* data; int capacity; }Stack; void Stack_init(Stack* pphead); //棧的初始化 void Stack_destory(Stack* pphead); //棧的清空 void Stack_push(Stack* pphead, Stacktype data); //插入數(shù)據(jù),壓棧 void Stack_pop(Stack* pphead); //出棧(刪除數(shù)據(jù)) bool Stack_Empty(Stack* pphead); //判斷棧是否為空 Stacktype Stack_Top(Stack* pphead); //調(diào)出棧頂元素 int Stack_Size(Stack* pphead); //查看數(shù)據(jù)個(gè)數(shù) //棧的初始化 void Stack_init(Stack* pphead) { pphead->top = 0; pphead->capacity = 0; pphead->data = NULL; } //棧的清空 void Stack_destory(Stack* pphead) { pphead->top = 0; pphead->capacity = 0; free(pphead->data); pphead->data = NULL; } //插入數(shù)據(jù),壓棧 void Stack_push(Stack* pphead, Stacktype data) { assert(pphead); if (pphead->top == pphead->capacity) { int Newcapacity = (pphead->capacity == 0) ? 4 : ((pphead->top) * 2); Stacktype* temp = NULL; temp = (Stacktype*)realloc(pphead->data, sizeof(Stacktype) * Newcapacity); if (temp == NULL) { printf("Stack_push"); exit(-1); } pphead->data = temp; pphead->top = Newcapacity; } (pphead->data)[pphead->capacity] = data; pphead->capacity++; } //出棧(刪除數(shù)據(jù)) void Stack_pop(Stack* pphead) { assert(pphead); assert(Stack_Empty(pphead)); pphead->capacity--; } //判斷棧是否為空 bool Stack_Empty(Stack* pphead) { assert(pphead); return pphead->capacity != 0; } //調(diào)出棧頂元素 Stacktype Stack_Top(Stack* pphead) { assert(pphead); assert(Stack_Empty(pphead)); return pphead->data[pphead->capacity - 1]; } //查看數(shù)據(jù)個(gè)數(shù) int Stack_Size(Stack* pphead) { assert(pphead); return pphead->top; }
補(bǔ)充 棧的用處
我們好不容易實(shí)現(xiàn)了一個(gè)棧,接下來我們來做個(gè)題看看棧有什么用吧。
題目描述
給定一個(gè)只包括 ‘(’,’)’,’{’,’}’,’[’,’]’ 的字符串 s ,判斷字符串是否有效。
有效字符串需滿足:
左括號必須用相同類型的右括號閉合。
左括號必須以正確的順序閉合。
基礎(chǔ)框架
C語言的基礎(chǔ)框架如下
bool isValid(char * s){ ???????}
解題思路
左括號一定要和右括號對齊,非常滿足棧的特性
我們可以將所有的左括號存入一個(gè)棧中。
然后遇到右括號,就出棧,判斷是否匹配。
直到棧為空且字符串中的括號也遍歷完了,那么所有括號就正確的匹配了。
代碼詳解
// 1.因?yàn)镃語言并沒有現(xiàn)成的棧,所以我們需要自己造輪子,先寫個(gè)棧再說 typedef char STDateType; // 更改數(shù)據(jù)類型為char typedef struct Stack { STDateType* a; int top; int capacity; }Stack; void StackInti(Stack* ps) { assert(ps); ps->a = NULL; ps->capacity = 0; ps->top = 0; } void StackDestory(Stack* ps) { assert(ps); free(ps->a); ps->capacity = 0; ps->top = 0; } void StackPush(Stack* ps, STDateType x) { assert(ps); if (ps->top == ps->capacity) { int newCapcity = ps->capacity == 0 ? 4 : ps->capacity * 2; ps->a = (int*)realloc(ps->a, sizeof(int) * newCapcity); if (ps->a == NULL) { printf("ralloc error"); exit(-1); } ps->capacity = newCapcity; } ps->a[ps->top] = x; ps->top++; } void StackPop(Stack* ps) { assert(ps); assert(ps->top > 0); ps->top--; } bool StackEmpty(Stack* ps) { assert(ps); return ps->top == 0; } STDateType StackTop(Stack* ps) { assert(ps); assert(ps->top > 0); return ps->a[ps->top - 1]; } bool isValid(char * s){ Stack a; StackInti(&a); while(*s) { if (*s == '(' || *s == '[' || *s == '{') //入棧 { StackPush(&a, *s); } else //出棧 { if(StackEmpty(&a)) //右括號多一個(gè)的情況 { return false; } char tmp = StackTop(&a); StackPop(&a); if ((*s == ')' && tmp != '(') ||(*s == ']' && tmp != '[') ||(*s == '}' && tmp != '{') ) { return false; } } s++; } return StackEmpty(&a); //防止出現(xiàn)多一個(gè)左括號的情況 }
到此這篇關(guān)于C語言實(shí)現(xiàn)棧的示例代碼的文章就介紹到這了,更多相關(guān)C語言實(shí)現(xiàn)棧內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C++實(shí)現(xiàn)LeetCode(130.包圍區(qū)域)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(130.包圍區(qū)域),本篇文章通過簡要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07Unix下C程序內(nèi)存泄漏檢測工具Valgrind的安裝與使用詳解
以下是對Unix下C程序內(nèi)存泄漏檢測工具Valgrind的安裝與使用進(jìn)行了詳細(xì)的分析介紹,需要的朋友可以過來參考下2013-08-08- 線性表是最基本、最簡單、也是最常用的一種數(shù)據(jù)結(jié)構(gòu)。一個(gè)線性表是n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列,這篇文章帶你學(xué)習(xí)如何通過C語言實(shí)現(xiàn)線性表的順序存儲和鏈?zhǔn)酱鎯?/div> 2021-11-11
C語言中的setlinebuf()、utmpname()、rewind函數(shù)使用
這篇文章主要介紹了C語言中的setlinebuf()、utmpname()、rewind函數(shù)使用,是C語言中操作文件的一些基本函數(shù),需要的朋友可以參考下2015-08-08C語言中實(shí)現(xiàn)“17進(jìn)制”轉(zhuǎn)“10進(jìn)制”實(shí)例代碼
這篇文章主要介紹了C語言中實(shí)現(xiàn)“17進(jìn)制”轉(zhuǎn)“10進(jìn)制”實(shí)例代碼的相關(guān)資料,需要的朋友可以參考下2017-05-05最新評論