? ?
??博客昵稱(chēng)：博客小夢(mèng)
??最喜歡的座右銘：全神貫注的上吧！?。?br> ??作者簡(jiǎn)介：一名熱愛(ài)C/C++，算法等技術(shù)、喜愛(ài)運(yùn)動(dòng)、熱愛(ài)K歌、敢于追夢(mèng)的小博主！
??博主小留言：哈嘍！??各位CSDN的uu們，我是你的博客好友小夢(mèng)，希望我的文章可以給您帶來(lái)一定的幫助，話不多說(shuō)，文章推上！歡迎大家在評(píng)論區(qū)嘮嗑指正，覺(jué)得好的話別忘了一鍵三連哦！??
前言??
? ? 哈嘍各位友友們??，我今天又學(xué)到了很多有趣的知識(shí)，現(xiàn)在迫不及待的想和大家分享一下！??我僅已此文，手把手帶領(lǐng)大家棧的實(shí)現(xiàn)和力扣題解知識(shí)~ 都是精華內(nèi)容，可不要錯(cuò)過(guò)喲?。。??????
什么是棧？
? ?棧和順序表和鏈表一樣，是線性結(jié)構(gòu)的。棧可以用數(shù)組實(shí)現(xiàn)，也可以用鏈表實(shí)現(xiàn)。這里采用的是動(dòng)態(tài)數(shù)組（順序結(jié)構(gòu)）實(shí)現(xiàn)的方式。棧的特點(diǎn)是LIFO。什么是“LIFO”呢？用中文簡(jiǎn)單的來(lái)說(shuō)就是后進(jìn)先出。也有人會(huì)叫先進(jìn)后出，其實(shí)都是同一個(gè)意思。
棧的C語(yǔ)言實(shí)現(xiàn)
頭文件編寫(xiě)源碼：
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int STDataType;
//順序棧
typedef struct STNode
{
STDataType* a;
int top;
int capacity;
}ST;
void STInit(ST* pst);
void STDestroy(ST* pst);
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);
bool STEmpty(ST* pst);
STDataType STTop(ST* pst);
int STSize(ST* pst);
功能文件編寫(xiě)源碼：
#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
void STInit(ST* pst)
{
assert(pst);
pst->a = NULL;
//top指向棧頂元素的下一個(gè)位置
pst->capacity = pst->top = 0;
}
void STDestroy(ST* pst)
{
assert(pst);
free(pst->a);
pst->capacity = pst->top = 0;
pst->a = NULL;
}
void STPush(ST* pst, STDataType x)
{
assert(pst);
//擴(kuò)容
if (pst->capacity == pst->top)
{
int newcapacity = pst->capacity == 0 ? 4 : 2 * (pst->capacity);
STDataType* tem = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);
if (tem == NULL)
{
perror("realloc fail\n");
exit(-1);
}
pst->capacity = newcapacity;
pst->a = tem;
}
pst->a[pst->top] = x;
(pst->top)++;
}
bool STEmpty(ST* pst)
{
assert(pst);
return pst->top == 0;
}
void STPop(ST* pst)
{
assert(pst);
assert(!STEmpty(pst));
(pst->top)--;
}
STDataType STTop(ST* pst)
{
assert(pst);
assert(!STEmpty(pst));
return pst->a[pst->top - 1];
}
int STSize(ST* pst)
{
assert(pst);
return pst->top;
}
測(cè)試文件編寫(xiě)源碼：
#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
int main()
{
//ST s;
//STInit(&s);
//STPush(&s, 1);
//STPush(&s, 2);
//STPush(&s, 3);
//STPush(&s, 4);
//STPush(&s, 3);
//STPush(&s, 4);
//while (!STEmpty(&s))
//{
// printf("%d ", STTop(&s));
// STPop(&s);
//}
//printf("\n");
ST s;
STInit(&s);
STPush(&s, 1);
STPush(&s, 2);
STPush(&s, 3);
STPush(&s, 4);
STPop(&s);
STPop(&s);
while (!STEmpty(&s))
{
printf("%d ", STTop(&s));
STPop(&s);
}
printf("\n");
return 0;
}
運(yùn)行結(jié)果截圖：
力扣題解——有效的括號(hào)
誰(shuí)說(shuō)C語(yǔ)言不能“C”，接下來(lái)我用C語(yǔ)言手撕這道題目。這道題目非常巧妙的運(yùn)用到了棧這個(gè)特點(diǎn)
我的做法是：
- 先讓左括號(hào)入棧
- 遇到右括號(hào)在出棧
不理解上述思想的可以自己畫(huà)圖理解理解，這個(gè)我相信難不倒大家，下面是我畫(huà)的一個(gè)比較粗糙的圖解~
如果用C嘎嘎來(lái)寫(xiě)，則可以直接調(diào)用庫(kù)函數(shù)的棧，而C語(yǔ)言就比較難受了。因?yàn)镃語(yǔ)言沒(méi)有這樣的庫(kù)函數(shù)，所以我們需要首先一個(gè)棧，但是不能說(shuō)C語(yǔ)言就不能做，照樣可以"C"! 。前面的棧我已經(jīng)寫(xiě)好了，直接ctrl c + ctrl v ，復(fù)制一份到題目中即可。
題目源碼：
typedef int STDataType;
//順序棧
typedef struct STNode
{
STDataType* a;
int top;
int capacity;
}ST;
void STInit(ST* pst);
void STDestroy(ST* pst);
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);
bool STEmpty(ST* pst);
STDataType STTop(ST* pst);
int STSize(ST* pst);
#define _CRT_SECURE_NO_WARNINGS 1
void STInit(ST* pst)
{
assert(pst);
pst->a = NULL;
//top指向棧頂元素的下一個(gè)位置
pst->capacity = pst->top = 0;
}
void STDestroy(ST* pst)
{
assert(pst);
free(pst->a);
pst->capacity = pst->top = 0;
pst->a = NULL;
}
void STPush(ST* pst, STDataType x)
{
assert(pst);
//擴(kuò)容
if (pst->capacity == pst->top)
{
int newcapacity = pst->capacity == 0 ? 4 : 2 * (pst->capacity);
STDataType* tem = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);
if (tem == NULL)
{
perror("realloc fail\n");
exit(-1);
}
pst->capacity = newcapacity;
pst->a = tem;
}
pst->a[pst->top] = x;
(pst->top)++;
}
bool STEmpty(ST* pst)
{
assert(pst);
return pst->top == 0;
}
void STPop(ST* pst)
{
assert(pst);
assert(!STEmpty(pst));
(pst->top)--;
}
STDataType STTop(ST* pst)
{
assert(pst);
assert(!STEmpty(pst));
return pst->a[pst->top - 1];
}
int STSize(ST* pst)
{
assert(pst);
return pst->top;
}
bool isValid(char * s)
{
ST st;
STInit(&st);
//循環(huán)遍歷字符串s，遇到\0結(jié)束
while(*s)
{
if(*s == '('
|| *s == '['
|| *s == '{')
{
STPush(&st,*s);
}
else
{
if(STEmpty(&st))
{
STDestroy(&st);
return false;
}
char Top = STTop(&st);
STPop(&st);
if(*s == ')' && Top != '('
|| *s == ']' && Top != '['
|| *s == '}' && Top != '{')
{
STDestroy(&st);
return false;
}
}
s++;
}
bool ret = STEmpty(&st);
STDestroy(&st);
return ret;
}
運(yùn)行結(jié)果截圖：
文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-453460.html
總結(jié)撒花??
? ?本篇文章旨在分享的是棧的C語(yǔ)言實(shí)現(xiàn)和力扣題解知識(shí)。希望大家通過(guò)閱讀此文有所收獲！
? ???如果我寫(xiě)的有什么不好之處，請(qǐng)?jiān)谖恼孪路浇o出你寶貴的意見(jiàn)??。如果覺(jué)得我寫(xiě)的好的話請(qǐng)點(diǎn)個(gè)贊贊和關(guān)注哦~??????文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-453460.html
到了這里，關(guān)于【追夢(mèng)之旅】——棧居然還能這樣玩？！+ 力扣 - 有效括號(hào)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
