C語言實現(xiàn)棧的示例詳解
更新時間：2022年06月29日 10:50:27 作者：。菀枯。
棧是一種特殊的線性表，只允許從一端進出數(shù)據(jù)，稱為后進先出，先進后出。本文主要為大家介紹了C語言實現(xiàn)棧的示例代碼，感興趣的可以了解一下
前言
前一段時間，我們試著用C語言實現(xiàn)了數(shù)據(jù)結構中的順序表，單鏈表，雙向循環(huán)鏈表。今天我們再用C語言來實現(xiàn)另一種特殊的線性結構：棧
一. 什么是棧
棧（stack）又名堆棧，它是一種運算受限的線性表。限定僅在表尾進行插入和刪除操作的線性表。這一端被稱為棧頂，相對地，把另一端稱為棧底。向一個棧插入新元素又稱作進棧、入棧或壓棧，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個棧刪除元素又稱作出?；蛲藯?，它是把棧頂元素刪除掉，使其相鄰的元素成為新的棧頂元素。
類似于步槍的子彈夾，后進去的子彈先發(fā)射出來以后，前面的子彈才可以發(fā)射。
二. 使用什么來實現(xiàn)棧
前一段時間，我們學習了兩種線性表，一種是順序表，一種是鏈表，那么對于棧我們該用哪一個來實現(xiàn)比較好呢
首先我們來對比一下線性表和鏈表
| 不同點 | 順序表 | 鏈表 |
|---|---|---|
| 存儲空間上 | 物理上一定連續(xù) | 邏輯上連續(xù)，但物理上不一定連續(xù) |
| 隨機訪問 | 可以直接訪問任何元素 | 必須從頭節(jié)點開始往后尋找 |
| 任意位置插入或刪除元素 | 要搬移其他的元素，效率低。 | 只需要修改節(jié)點的指針指向，效率高 |
| 插入 | 動態(tài)順序表，當空間不夠時需要擴容 | 無容量概念，需要就申請，不用就釋放 |
| 應用場景 | 元素高效存儲，并且需要頻繁訪問 | 需要在任意位置插入或者刪除頻繁 |
綜合以上來看，我認為實現(xiàn)一個棧，使用順序表比較好。
1.棧是先進后出，使用順序表，在元素出棧后更容易找到新的棧頂。
2.順序表CPU高速緩存命中率高，可以減少CPU去內存拿數(shù)據(jù)的次數(shù)，速度快，效率高。
三. 棧的實現(xiàn)
3.1 頭文件
1.包含的標準庫
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> //C語言中的bool類型需要這個頭文件 #include <assert.h>
2.定義結構體
typedef int STDateType;//棧中元素的數(shù)據(jù)類型
typedef struct Stack
{
STDateType* a; //順序表
int top; //棧頂
int capacity; //棧的容量
}Stack;
3.函數(shù)的聲明
void StackInti(Stack* ps); // 棧的初始化 void StackDestory(Stack* ps); // 棧的銷毀 void StackPush(Stack* ps, STDateType x); // 入棧 void StackPop(Stack* ps); // 出棧 bool StackEmpty(Stack* ps); // 判斷棧是否為空 STDateType StackTop(Stack* ps); // 取棧頂元素
3.2 函數(shù)實現(xiàn)
1. 棧的初始化
我們用assert（斷言），防止ps為空指針。
void StackInti(Stack* ps)
{
assert(ps);
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}
2. 棧的銷毀
釋放順序表。
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];
}
這樣我們就實現(xià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];
}
四. 棧的用處
我們好不容易實現(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語言 棧內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要為大家詳細介紹了C語言實現(xiàn)圖書管理系統(tǒng)課程設計，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-07-07
今天遇見了一道有意思的內存泄露題目，特地分享給大家，相信屏幕前的你學習完一定有所收獲，預祝讀者學習愉快，多多進步早日升職加薪2021-10-10
今天小編就為大家分享一篇opencv3/C++繪制幾何圖形實例，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-12-12
這篇文章主要為大家詳細介紹了C語言的數(shù)據(jù)的存儲，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能給你帶來幫助2021-08-08
這篇文章主要為大家整理并介紹了C語言編程必背的示例代碼大全，有需要的朋友可以借鑒參考下，希望能夠有所幫助2021-11-11
在學習過程中很重要的一個必會的小技巧：計算某一段代碼的執(zhí)行時間,可以用來分析代碼的效率和算法的時間復雜度等等(個人主要是在總結各種排序算法時遇到的這個方法),本文給大家介紹了C++記錄程序運行時間的四種方法,需要的朋友可以參考下2025-03-03
這篇文章主要該大家分享C語言算法佩奇存錢的練習，文章主要通過描述佩奇存錢的問題然后確定程序框架將結果運算出來，下面來看詳細內容吧,需要的朋友可以參考一下2022-04-04
C++中范圍（Ranges）與視圖（Views）的常見問題、易錯點
ranges和views是C20引入的重要特性,它們讓代碼更加簡潔、高效且富有表達力,通過理解其基本概念、注意常見的陷阱,并合理應用高級技巧,開發(fā)者可以充分利用這些新特性,提升軟件質量和開發(fā)效率,,本文將深入淺出地探討ranges與views的基礎概念、常見問題、易錯點及避免策略2024-06-06
函數(shù)是一組一起執(zhí)行一個任務的語句。每個?C?程序都至少有一個函數(shù)，即主函數(shù)?main()?，所有簡單的程序都可以定義其他額外的函數(shù)2022-03-03
C++實現(xiàn)LeetCode(134.加油站問題)
這篇文章主要介紹了C++實現(xiàn)LeetCode(134.加油站問題),本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內容,需要的朋友可以參考下2021-07-07