C語言實現(xiàn)棧及棧的詳解
前言以及成型代碼：
學習完數(shù)據(jù)表和鏈表以后我們來學習一個新的數(shù)據(jù)結(jié)構(gòu)：棧 。 還是老套路先把成型代碼給各位看關老爺呈上方便有一個初步了解。更重要的是可以方便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é)構(gòu)實現(xiàn)更優(yōu)一些。因為數(shù)組在尾上插入數(shù)據(jù)的代價比較小。
三、代碼實現(xiàn)以及詳細解釋
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; 這幾行代碼是棧的地基，也是這個結(jié)構(gòu)中最簡單的代碼了。
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)建以后肯定是要銷毀的，要不然就會造成內(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語言中數(shù)據(jù)是如何存儲在內(nèi)存中的
使用編程語言進行編程時，需要用到各種變量來存儲各種信息。變量保留的是它所存儲的值的內(nèi)存位置。這意味著，當您創(chuàng)建一個變量時，就會在內(nèi)存中保留一些空間。您可能需要存儲各種數(shù)據(jù)類型的信息，操作系統(tǒng)會根據(jù)變量的數(shù)據(jù)類型，來分配內(nèi)存和決定在保留內(nèi)存中存儲什么2022-04-04
大家好，本篇文章主要講的是C語言16進制與ASCII字符相互轉(zhuǎn)換，感興趣的同學趕快來看一看吧，對你有幫助的話記得收藏一下2022-01-01
這篇文章主要介紹了VC++在TXT文件指定位置追加內(nèi)容的方法,功能較為實用,需要的朋友可以參考下2014-08-08
這篇文章主要為大家詳細介紹了C語言復雜鏈表的復制，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-02-02
這篇文章主要為大家詳細介紹了用C語言實現(xiàn)三子棋小游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-06-06
C++實現(xiàn)LeetCode(67.二進制數(shù)相加)
這篇文章主要介紹了C++實現(xiàn)LeetCode(67.二進制數(shù)相加),本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-07-07
這篇文章主要為大家詳細介紹了如何使用qt制作了一個簡單的圖片播放器，可以播放gif、png等格式圖片。文中的示例代碼講解詳細，需要的可以參考一下2022-12-12
C++ 數(shù)據(jù)結(jié)構(gòu)鏈表的實現(xiàn)代碼
這篇文章主要介紹了C++ 數(shù)據(jù)結(jié)構(gòu)鏈表的實現(xiàn)代碼的相關資料,需要的朋友可以參考下2017-01-01
Linux下控制(統(tǒng)計)文件的生成的C代碼實現(xiàn)
這篇文章主要介紹了Linux下控制(統(tǒng)計)文件的生成的C代碼實現(xiàn)，感興趣的小伙伴們可以參考一下2016-01-01
中序遍歷(LDR)是二叉樹遍歷的一種，也叫做中根遍歷、中序周游。在二叉樹中，中序遍歷首先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹2021-07-07