目錄

一、棧的概念及結(jié)構(gòu)

二、棧的頭文件及基本框架

三、接口實(shí)現(xiàn)

1、對(duì)棧的初始化

?2、棧的銷毀

3、入棧操作

4、出棧操作

?5、判斷棧是否為空

6、返回棧頂元素

7、遍歷棧

四、有效的括號(hào) - 力扣（LeetCode）

題目描述：

?思路：

代碼：

一、棧的概念及結(jié)構(gòu)

棧：一種特殊的線性表，其只允許在固定的一端進(jìn)行插入和刪除元素操作。進(jìn)行數(shù)據(jù)插入和刪除操作的一端稱為棧頂，另一端稱為棧底。棧中的數(shù)據(jù)元素遵守后進(jìn)先出的原則。

如同子彈夾，我們進(jìn)行添子彈和出子彈，很形象。

壓棧：棧的插入操作叫做進(jìn)棧/壓棧/入棧，入數(shù)據(jù)在棧頂。

出棧：棧的刪除操作叫做出棧。出數(shù)據(jù)也在棧頂。

?接下來，我們以數(shù)組棧的形式去模擬。

二、棧的頭文件及基本框架

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>

typedef int STDataType;

typedef struct Stack
{
	STDataType* a;//就是以a開頭的一段連續(xù)的空間
	int top;//定義棧頂位置
	int capacity;
}ST;

void SLInit(ST* ps);
void SLDestroy(ST* ps);
void STPush(ST* ps, STDataType x);
void STPop(ST* ps);
int STSize(ST* ps);
bool STEmpty(ST* ps);
STDataType STTop(ST* ps);//獲取棧頂元素

三、接口實(shí)現(xiàn)

1、對(duì)棧的初始化

void SLInit(ST* ps)
{
	ST* ret = (ST*)malloc(4 * sizeof(ST));
	if (ret == NULL)
	{
		perror(malloc);
		exit(-1);
	}
	ps->a = ret;
	ps->capacity = 4;
	ps->top = 0;
}

?2、棧的銷毀

void SLDestroy(ST* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

3、入棧操作

void STPush(ST* ps, STDataType x)
{
	assert(ps != NULL);
	//檢查需不需要擴(kuò)容
	if (ps->top == ps->capacity)
	{
		ps->capacity += 4;
		ST* ret = (ST*)realloc( ps->a, sizeof(ST) * ps->capacity);
		if (ret == NULL)
		{
			perror(realloc);
			exit(-1);
		}
		ps->a = ret;
	}
	ps->a[ps->top] = x;
	ps->top++;
}

4、出棧操作

void STPop(ST* ps)
{
	assert(ps);
	ps->top--;
}

?5、判斷棧是否為空

bool STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
    如果右邊等式成立返回true，反之返回false
}

6、返回棧頂元素

STDataType STTop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1];
}

7、遍歷棧

不同于其他數(shù)據(jù)結(jié)構(gòu)，遍歷棧不用print

//遍歷棧的特殊方式
	while (!STEmpty(&ps))
	{
		printf("%d ", STTop(&ps));
		STPop(&ps);
	}

四、有效的括號(hào) - 力扣（LeetCode）

題目描述：

給定一個(gè)只包括?'('，')'，'{'，'}'，'['，']'?的字符串?s?，判斷字符串是否有效。

有效字符串需滿足：

1. 左括號(hào)必須用相同類型的右括號(hào)閉合。
2. 左括號(hào)必須以正確的順序閉合。
3. 每個(gè)右括號(hào)都有一個(gè)對(duì)應(yīng)的相同類型的左括號(hào)。

?思路：

如果是左括號(hào)就入棧，如果是右括號(hào)就與棧頂元素進(jìn)行比較。這樣就正好匹配題目的要求，但博主目前沒有學(xué)過STL庫，所以只能將上面的手撕棧CV一下啦，下面的代碼為了避免冗余去除掉這一部分~文章來源地址http://www.zghlxwxcb.cn/news/detail-644513.html

代碼：

bool isValid(char * s)
{
    char* ret = s;
    int num = 0;
    //利用奇數(shù)偶數(shù)判斷數(shù)量是否匹配
    while(*ret)
    {
        num++;
        ret++;
    }
    if(num%2 != 0)
    {
        return false;
    }
    ST ps;
	SLInit(&ps);
    while(*s)
    {
    switch(*s)
    {
        case '{':
        case '[':
        case '(':
            STPush(&ps,*s);
            break;
        case ')':
        case ']':
        case '}':
            if(STSize(&ps) == 0)
                return false;
            if(*s == ']' && STTop(&ps) != '['||
               *s == ')' && STTop(&ps) != '('||
               *s == '}' && STTop(&ps) != '{')
            {
                SLDestroy(&ps);
                return false;
            }
            STPop(&ps);
            break;
    }
    s++;
    }
    //防止((出現(xiàn)
    if(!STEmpty(&ps))
        return false;
    return true;
}

到了這里，關(guān)于手撕數(shù)據(jù)結(jié)構(gòu)之棧+例題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！