C語(yǔ)言實(shí)現(xiàn)棧及棧的詳解
前言以及成型代碼：
學(xué)習(xí)完數(shù)據(jù)表和鏈表以后我們來(lái)學(xué)習(xí)一個(gè)新的數(shù)據(jù)結(jié)構(gòu)：棧 。 還是老套路先把成型代碼給各位看關(guān)老爺呈上方便有一個(gè)初步了解。更重要的是可以方便CV工程師的工作
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}ST;
// 初始化棧
void STInit(ST* pst);
// 銷毀棧
void STDestroy(ST* pst);
// 添加數(shù)據(jù)
void STPush(ST* pst, STDataType x);
// 刪除數(shù)據(jù)
void STPop(ST* pst);
// 彈出數(shù)據(jù)
STDataType STTop(ST* pst);
// 判斷是否為空
bool STEmpty(ST* pst);
// 判斷大小
int STSize(ST* pst);
void STInit(ST* pst)
{
assert(pst);
pst->a = NULL;
pst->top = 0;
pst->capacity = 0;
}
// 銷毀棧
void STDestroy(ST* pst)
{
assert(pst);
free(pst->a);
pst->a = NULL;
pst->top = 0;
pst->capacity = 0;
}
// 添加數(shù)據(jù)
void STPush(ST* pst, STDataType x)
{
if (pst->capacity == pst->top)
{
int newcapacity = (pst->capacity == 0 ? 4 : pst->capacity * 2);
STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType));
if (tmp == NULL)
{
perror("realloc fail");
return;
}
pst->a = tmp;
pst->capacity = newcapacity;
}
pst->a[pst->top] = x;
pst->top++;
}
// 刪除數(shù)據(jù)
void STPop(ST* pst)
{
assert(pst);
assert(!(STEmpty(pst)));
pst->top--;
}
// 彈出數(shù)據(jù)
STDataType STTop(ST* pst)
{
assert(pst);
assert(!(STEmpty(pst)));
return pst->a[pst->top - 1];
}
// 判斷是否為空
bool STEmpty(ST* pst)
{
assert(pst);
return pst->top == 0;
}
// 判斷大小
int STSize(ST* pst)
{
assert(pst);
return pst->top;
}一、棧的概念
棧：一種特殊的線性表，其只允許在固定的一端進(jìn)行插入和刪除元素操作。
進(jìn)行數(shù)據(jù)插入和刪除操作的一端稱為棧頂，另一端稱為棧底。
棧中的數(shù)據(jù)元素遵守后進(jìn)先出LIFO（Last In First Out）的原則。
壓棧：棧的插入操作叫做進(jìn)棧/壓棧/入棧，入數(shù)據(jù)在棧頂。
出棧：棧的刪除操作叫做出棧。出數(shù)據(jù)也在棧頂。
二、棧的實(shí)現(xiàn)
棧的實(shí)現(xiàn)一般可以使用數(shù)組或者鏈表實(shí)現(xiàn)，相對(duì)而言數(shù)組的結(jié)構(gòu)實(shí)現(xiàn)更優(yōu)一些。因?yàn)閿?shù)組在尾上插入數(shù)據(jù)的代價(jià)比較小。
三、代碼實(shí)現(xiàn)以及詳細(xì)解釋
1. 初步介紹
定義結(jié)構(gòu)體，以及棧內(nèi)數(shù)據(jù)類型初始化棧 void STInit(ST* pst);銷毀棧 void STDestroy(ST* pst);
添加數(shù)據(jù) void STPush(ST* pst, STDataType x);
刪除數(shù)據(jù) void STPop(ST* pst)；
彈出數(shù)據(jù) STDataType STTop(ST* pst);
判斷是否為空 bool STEmpty(ST* pst);
判斷大小 int STSize(ST* pst);
2. 定義結(jié)構(gòu)體，以及棧內(nèi)數(shù)據(jù)類型
代碼：
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int STDataType; //定義棧內(nèi)數(shù)據(jù)類型，方便后面修改
typedef struct Stack //創(chuàng)建棧的基本結(jié)構(gòu)
{
STDataType* a;
int top;
int capacity;
}ST; 這幾行代碼是棧的地基，也是這個(gè)結(jié)構(gòu)中最簡(jiǎn)單的代碼了。
3. 初始化棧 void STInit(ST* pst);
代碼：
// 初始化棧
void STInit(ST* pst)
{
assert(pst); //判斷是否為空指針
pst->a = NULL; //棧為空的，所以先初始化為空指針
pst->top = 0;
pst->capacity = 0;
}初始化棧，顧名思義就是把棧的結(jié)構(gòu)上面添加一些初始值。讓前面的地基有框架。
4. 銷毀棧 void STDestroy(ST* pst);
代碼：
// 銷毀棧
void STDestroy(ST* pst)
{
assert(pst);
free(pst->a); //釋放指針
pst->a = NULL; //置空指針a
pst->top = 0; //把棧頂?shù)奈恢媒档?，釋放?shù)據(jù)
pst->capacity = 0;//把棧的大小置為0
}創(chuàng)建以后肯定是要銷毀的，要不然就會(huì)造成內(nèi)存泄漏。
5.添加數(shù)據(jù) void STPush(ST* pst, STDataType x);
代碼：
// 添加數(shù)據(jù)
void STPush(ST* pst, STDataType x)
{
if (pst->capacity == pst->top) //判斷是否要擴(kuò)容
{
int newcapacity = (pst->capacity == 0 ? 4 : pst->capacity * 2); //擴(kuò)容步驟，當(dāng)為空棧時(shí)擴(kuò)基礎(chǔ)的大小，不為空則擴(kuò)成原來(lái)的二倍
STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType));//使用realloc擴(kuò)出來(lái)一定的空間
if (tmp == NULL)
{
perror("realloc fail");
return;
}
pst->a = tmp; //初始化這一塊空間
pst->capacity = newcapacity;
}
pst->a[pst->top] = x; //把x的直插入到棧的頂部
pst->top++;
}添加數(shù)據(jù)也是很重要的一個(gè)步驟，這一步直接決定了這個(gè)棧的成功與否。添加的時(shí)候要首先判斷后面的空間是否足夠，夠的話直接加上去，不夠的話就擴(kuò)容。
6.刪除數(shù)據(jù) void STPop(ST* pst)；
// 刪除數(shù)據(jù)
void STPop(ST* pst)
{
assert(pst);
assert(!(STEmpty(pst))); //判斷是否為空
pst->top--;
}刪除數(shù)據(jù)的時(shí)候要借助后面的判空函數(shù)，為空就不能再刪除了
7. 彈出數(shù)據(jù) STDataType STTop(ST* pst);
代碼：
// 彈出數(shù)據(jù)
STDataType STTop(ST* pst)
{
assert(pst);
assert(!(STEmpty(pst)));
return pst->a[pst->top - 1];
}彈出數(shù)據(jù)就是：調(diào)用完這個(gè)函數(shù)以后可以返回棧頂?shù)闹?/p>
8. 判斷是否為空 bool STEmpty(ST* pst);
// 判斷是否為空
bool STEmpty(ST* pst)
{
assert(pst);
return pst->top == 0;//判空
}判空就是看里面還有數(shù)據(jù)沒(méi)有了，有的話返回false 沒(méi)有數(shù)據(jù)也就是空值的狀態(tài)就返回true
9. 判斷大小 int STSize(ST* pst);
代碼：
// 判斷大小
int STSize(ST* pst)
{
assert(pst);
return pst->top;
}直接返回棧頂就可以了
到此這篇關(guān)于C語(yǔ)言實(shí)現(xiàn)棧及棧的詳解的文章就介紹到這了,更多相關(guān)C語(yǔ)言實(shí)現(xiàn)棧內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
c++ class中成員與分配內(nèi)存的問(wèn)題詳解
很多人都知道C++類是由結(jié)構(gòu)體發(fā)展得來(lái)的,所以他們的成員變量（C語(yǔ)言的結(jié)構(gòu)體只有成員變量）的內(nèi)存分配機(jī)制是一樣的,下面這篇文章主要給大家介紹了關(guān)于c++ class中成員與分配內(nèi)存問(wèn)題的相關(guān)資料,需要的朋友可以參考下2021-10-10
這篇文章主要介紹了C++中的哈希容器unordered_map使用示例,本文直接給出實(shí)例代碼,并講解了一些hash table的知識(shí),需要的朋友可以參考下2015-06-06
二分查找法，又叫做折半查找法，它是一種效率較高的查找方法。但是，折半查找要求線性表必須采用順序存儲(chǔ)結(jié)構(gòu)，而且表中元素按關(guān)鍵字有序排列2022-04-04
這篇文章主要介紹了C++中auto_ptr智能指針的用法詳解的相關(guān)資料,需要的朋友可以參考下2016-07-07
這篇文章主要介紹了MFC框架之OnIdle案例詳解,本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-08-08
詳解如何將c語(yǔ)言文件打包成exe可執(zhí)行程序
這篇文章主要介紹了詳解如何將c語(yǔ)言文件打包成exe可執(zhí)行程序，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2021-02-02
這篇文章主要為大家詳細(xì)介紹了OpenCV識(shí)別提取圖像中的水平線與垂直線，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-07-07
C語(yǔ)言中sizeof函數(shù)踩過(guò)的坑總結(jié)
sizeof是C語(yǔ)言的一種單目操作符，如C語(yǔ)言的其他操作符++、--等。它并不是函數(shù)。sizeof操作符以字節(jié)形式給出了其操作數(shù)的存儲(chǔ)大小。操作數(shù)可以是一個(gè)表達(dá)式或括在括號(hào)內(nèi)的類型名。操作數(shù)的存儲(chǔ)大小由操作數(shù)的類型決定2022-04-04
C++編程模板匹配超詳細(xì)的識(shí)別手寫(xiě)數(shù)字實(shí)現(xiàn)示例
大家好！本篇文章是關(guān)于手寫(xiě)數(shù)字識(shí)別的，接下來(lái)我將在這里記錄我的手寫(xiě)數(shù)字識(shí)別的從零到有，我在這里把我自己的寫(xiě)代碼過(guò)程發(fā)出來(lái)，希望能幫到和我一樣努力求知的人2021-10-10
這篇文章主要介紹了C語(yǔ)言之strtol函數(shù)用法詳解,本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07