C語言實現(xiàn)棧的示例代碼

更新時間：2022年06月27日 09:46:14 作者：MT_125

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

一、了解棧的結構特點

棧是一種特殊的線性表，只允許從一端進出數(shù)據(jù)，稱為后進先出，先進后出。

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

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

二、具體實現(xiàn)

由于棧實質是一種線性表，因此可以用兩種方式來實現(xiàn)：順序表或鏈表

這里我使用的是類似順序表的方式來實現(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);     //調出棧頂元素
int Stack_Size(Stack* pphead);          //查看數(shù)據(jù)個數(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;
}
//調出棧頂元素
Stacktype Stack_Top(Stack* pphead)
{
    assert(pphead);
    assert(Stack_Empty(pphead));
    return pphead->data[pphead->capacity - 1];
}
//查看數(shù)據(jù)個數(shù)
int Stack_Size(Stack* pphead)
{
    assert(pphead);
    return pphead->top;
}

補充棧的用處

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

題目描述

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

有效字符串需滿足：

左括號必須用相同類型的右括號閉合。

左括號必須以正確的順序閉合。

基礎框架

C語言的基礎框架如下

bool isValid(char * s){

???????}

解題思路

左括號一定要和右括號對齊，非常滿足棧的特性

我們可以將所有的左括號存入一個棧中。

然后遇到右括號，就出棧，判斷是否匹配。

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

代碼詳解

// 1.因為C語言并沒有現(xiàn)成的棧，所以我們需要自己造輪子，先寫個棧再說
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)) //右括號多一個的情況
            {
                return false;
            }

            char tmp = StackTop(&a);
            StackPop(&a);
            if ((*s == ')' && tmp != '(') 
              ||(*s == ']' && tmp != '[')
              ||(*s == '}' && tmp != '{') )
            {
                return false;
            }
        }
        s++;
    }
    return StackEmpty(&a); //防止出現(xiàn)多一個左括號的情況
}

到此這篇關于C語言實現(xiàn)棧的示例代碼的文章就介紹到這了,更多相關C語言實現(xiàn)棧內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章:

C語言
棧

C語言中基礎小問題詳細介紹
這篇文章詳細介紹了C語言中基礎小問題，有需要的朋友可以參考一下
2013-10-10
C語言的數(shù)組指針與函數(shù)指針詳解
這篇文章主要為大家詳細介紹了C語言的數(shù)組指針與函數(shù)指針，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助
2022-03-03
C語言算法練習之打魚還是曬網
這篇文章主要該大家分享C語言打魚還是曬網的練習，文章主要通過三天打魚兩天曬網的俗語提出問題，在某一天輪到打魚還是曬網，下面來看詳細內容吧,需要的朋友可以參考一下
2022-03-03
C++超詳細講解內存空間分配與this指針
this?指針在C++類和對象中是個很方便實用的關鍵字，可以簡化對象成員屬性的調用，使代碼表達的含義更加準確；在之前的學習中我們都可以判斷變量所占內存空間大小，那么我們創(chuàng)建的類對象所占的內存空間怎么計算呢?想知道this的妙用和類對象占用的內存空間就來跟我學習吧
2022-05-05
詳解C++ 動態(tài)庫導出函數(shù)名亂碼及解決
這篇文章主要介紹了C++ 動態(tài)庫導出函數(shù)名亂碼及解決，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧
2019-03-03
基于C++自動化編譯工具的使用詳解
本篇文章是對C++中自動化編譯工具的使用進行了詳細的分析介紹，需要的朋友參考下
2013-05-05
C語言單鏈表實現(xiàn)通訊錄管理系統(tǒng)
這篇文章主要為大家詳細介紹了C語言單鏈表實現(xiàn)通訊錄管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
2021-05-05
C語言詳解Z字形變換排列的實現(xiàn)
Z字形變換排列就是指將一個給定字符串根據(jù)給定的行數(shù)，以從上往下、從左到右進行 Z 字形排列，下面讓我們用C語言來實現(xiàn)
2022-04-04
C++全面精通類與對象
類和對象是兩種以計算機為載體的計算機語言的合稱。對象是對客觀事物的抽象，類是對對象的抽象。類是一種抽象的數(shù)據(jù)類型；變量就是可以變化的量，存儲在內存中—個可以擁有在某個范圍內的可變存儲區(qū)域
2022-05-05
C++中利用cout和fstream采用非科學計數(shù)法輸出
這篇文章主要介紹了C++中利用cout和fstream采用非科學計數(shù)法輸出方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教
2022-11-11