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