C語(yǔ)言實(shí)現(xiàn)棧的示例詳解

更新時(shí)間：2022年06月29日 10:50:27 作者：。菀枯。

棧是一種特殊的線性表，只允許從一端進(jìn)出數(shù)據(jù)，稱(chēng)為后進(jìn)先出，先進(jìn)后出。本文主要為大家介紹了C語(yǔ)言實(shí)現(xiàn)棧的示例代碼，感興趣的可以了解一下

前言

前一段時(shí)間，我們?cè)囍肅語(yǔ)言實(shí)現(xiàn)了數(shù)據(jù)結(jié)構(gòu)中的順序表，單鏈表，雙向循環(huán)鏈表。今天我們?cè)儆肅語(yǔ)言來(lái)實(shí)現(xiàn)另一種特殊的線性結(jié)構(gòu)：棧

一. 什么是棧

棧（stack）又名堆棧，它是一種運(yùn)算受限的線性表。限定僅在表尾進(jìn)行插入和刪除操作的線性表。這一端被稱(chēng)為棧頂，相對(duì)地，把另一端稱(chēng)為棧底。向一個(gè)棧插入新元素又稱(chēng)作進(jìn)棧、入?；驂簵?，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個(gè)棧刪除元素又稱(chēng)作出棧或退棧，它是把棧頂元素刪除掉，使其相鄰的元素成為新的棧頂元素。

類(lèi)似于步槍的子彈夾，后進(jìn)去的子彈先發(fā)射出來(lái)以后，前面的子彈才可以發(fā)射。

二. 使用什么來(lái)實(shí)現(xiàn)棧

前一段時(shí)間，我們學(xué)習(xí)了兩種線性表，一種是順序表，一種是鏈表，那么對(duì)于棧我們?cè)撚媚囊粋€(gè)來(lái)實(shí)現(xiàn)比較好呢

首先我們來(lái)對(duì)比一下線性表和鏈表

不同點(diǎn)	順序表	鏈表
存儲(chǔ)空間上	物理上一定連續(xù)	邏輯上連續(xù)，但物理上不一定連續(xù)
隨機(jī)訪問(wèn)	可以直接訪問(wèn)任何元素	必須從頭節(jié)點(diǎn)開(kāi)始往后尋找
任意位置插入或刪除元素	要搬移其他的元素，效率低。	只需要修改節(jié)點(diǎn)的指針指向，效率高
插入	動(dòng)態(tài)順序表，當(dāng)空間不夠時(shí)需要擴(kuò)容	無(wú)容量概念，需要就申請(qǐng)，不用就釋放
應(yīng)用場(chǎng)景	元素高效存儲(chǔ)，并且需要頻繁訪問(wèn)	需要在任意位置插入或者刪除頻繁

綜合以上來(lái)看，我認(rèn)為實(shí)現(xiàn)一個(gè)棧，使用順序表比較好。

1.棧是先進(jìn)后出，使用順序表，在元素出棧后更容易找到新的棧頂。

2.順序表CPU高速緩存命中率高，可以減少CPU去內(nèi)存拿數(shù)據(jù)的次數(shù)，速度快，效率高。

三. 棧的實(shí)現(xiàn)

3.1 頭文件

1.包含的標(biāo)準(zhǔn)庫(kù)

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h> //C語(yǔ)言中的bool類(lèi)型需要這個(gè)頭文件
#include <assert.h>

2.定義結(jié)構(gòu)體

typedef int STDateType;//棧中元素的數(shù)據(jù)類(lèi)型

typedef struct Stack
{
	STDateType* a; //順序表
	int top; //棧頂
	int capacity; //棧的容量
}Stack;

3.函數(shù)的聲明

void StackInti(Stack* ps);
// 棧的初始化
void StackDestory(Stack* ps);
// 棧的銷(xiāo)毀
void StackPush(Stack* ps, STDateType x);
// 入棧
void StackPop(Stack* ps);
// 出棧
bool StackEmpty(Stack* ps);
// 判斷棧是否為空
STDateType StackTop(Stack* ps);
// 取棧頂元素

3.2 函數(shù)實(shí)現(xiàn)

1. 棧的初始化

我們用assert（斷言），防止ps為空指針。

void StackInti(Stack* ps)
{
    assert(ps);
    
    ps->a = NULL;
    ps->capacity = 0;
    ps->top = 0;
}

2. 棧的銷(xiāo)毀

釋放順序表。

void StackDestory(Stack* ps)
{
	assert(ps);

	free(ps->a);
	ps->capacity = 0;
	ps->top = 0;
}

3.入棧

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++;
}

4. 出棧

void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->top > 0); //空棧不能被刪除

	ps->top--;
}

5. 判斷棧是否為空

bool StackEmpty(Stack* ps)
{
    assert(ps);
    return ps->top == 0; // 如果為空則返回true，否則返回false
}

6. 取棧頂元素

STDateType StackTop(Stack* ps)
{
    assert(ps);
    assert(ps->top > 0);//空棧不能被刪除

    return ps->a[ps->top - 1];
}

這樣我們就實(shí)現(xiàn)了一個(gè)簡(jiǎn)單的棧

3.3 完整代碼

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

typedef int STDateType;

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];
}

四. 棧的用處

我們好不容易實(shí)現(xiàn)了一個(gè)棧，接下來(lái)我們來(lái)做個(gè)題看看棧有什么用吧。

題目描述

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

有效字符串需滿足：

左括號(hào)必須用相同類(lèi)型的右括號(hào)閉合。

左括號(hào)必須以正確的順序閉合。

基礎(chǔ)框架

C語(yǔ)言的基礎(chǔ)框架如下

bool isValid(char * s){

???????}

解題思路

左括號(hào)一定要和右括號(hào)對(duì)齊，非常滿足棧的特性

我們可以將所有的左括號(hào)存入一個(gè)棧中。

然后遇到右括號(hào)，就出棧，判斷是否匹配。

直到棧為空且字符串中的括號(hào)也遍歷完了，那么所有括號(hào)就正確的匹配了。

代碼詳解

// 1.因?yàn)镃語(yǔ)言并沒(méi)有現(xiàn)成的棧，所以我們需要自己造輪子，先寫(xiě)個(gè)棧再說(shuō)
typedef char STDateType; // 更改數(shù)據(jù)類(lèi)型為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)) //右括號(hào)多一個(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è)左括號(hào)的情況
}

到此這篇關(guān)于C語(yǔ)言實(shí)現(xiàn)棧的示例詳解的文章就介紹到這了,更多相關(guān)C語(yǔ)言棧內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: