C語言數(shù)據(jù)結(jié)構(gòu)進階之棧和隊列的實現(xiàn)
棧的實現(xiàn)：
一、棧的概念和性質(zhì)
棧（stack）又名堆棧，它是一種運算受限的線性表。限定僅在固定的一端進行插入和刪除操作的線性表。這一端被稱為棧頂，相對地，把另一端稱為棧底。棧中的數(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ù)的代價比較小這里我們用順序表結(jié)構(gòu)來實現(xiàn)棧。
順序表可以把使用的空間寫成固定值，也可以構(gòu)建動態(tài)開辟內(nèi)存；但是如果寫成固定的數(shù)組形式當存的數(shù)據(jù)滿了就不能再使用了，所以下面我們實現(xiàn)的是動態(tài)開辟內(nèi)存的形式。
所以我們先創(chuàng)建一個順序表結(jié)構(gòu)體類型，結(jié)構(gòu)體類型中有指針，下標，容量。
指針： 用來維護在堆上連續(xù)的一段空間，
下標：表示數(shù)據(jù)存放到哪一個位置了，因為數(shù)據(jù)只能一個接著一個地存放，要有個下標來記錄我數(shù)據(jù)放到哪一個位置了。
容量：與下標相比較，當下標與容量相等就表示空間存儲滿了，要進行擴容處理。
創(chuàng)建類型如下：
typedef int STDataType; //對int類型重新起個名字叫DataType
//創(chuàng)建一個棧結(jié)構(gòu)體類型
struct Stack
{
STDataType* a; //數(shù)據(jù)的指針
int top; //棧頂
int capacity; //記錄開辟空間的最大下標處
};
//對順序表類型struct Stack類型重新起個名字叫SL
typedef struct Stack ST;
//當size 和 capacity相等時要進行擴容處理
三、棧的相關變量內(nèi)存布局圖
四、棧的初始化和銷毀
//初始化變量st
void StackInit(ST* ps)
{
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}
//棧的銷毀
void StackDestroy(ST* ps)
{
free(ps->a);
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}
五、棧的接口實現(xiàn)：
1.入棧
//入棧
void StackPush(ST* ps, STDataType x)
{
assert(ps);
//內(nèi)存滿了要擴容
if (ps->capacity == ps->top)
{
ps->capacity = ps->capacity > 0 ? ps->capacity * 2 : 2;
STDataType* tmp =
(STDataType*)realloc(ps->a,sizeof(STDataType) * ps->capacity);
if (tmp == NULL)
{
perror("erron ");
exit(-1);
}
ps->a = tmp;
}
//沒有滿就直接在后面入棧
ps->a[ps->top] = x;
ps->top++;
}
2.出棧
//出棧，要注意棧不能為空
void StackPop(ST* ps)
{
assert(ps);
//棧為空就不能再出棧了
assert(ps->top >= 1);
ps->top--;
}
3.獲取棧頂?shù)臄?shù)據(jù)
//返回棧頂?shù)脑?
STDataType StackTop(ST* ps)
{
assert(ps);
//棧不能為空
assert(ps->top >= 1);
return ps->a[ps->top - 1];
}
4.獲取棧的元素個數(shù)
//獲取棧的元素個數(shù)
int StackSize(ST* ps)
{
assert(ps);
assert(ps->top >= 1);
return ps->top - 1;
}
5.判斷棧是否為空
//判斷棧是否為空
bool StackEmpty(ST* ps)
{
return ps->top == 0;
}
隊列的實現(xiàn)：
一、隊列的概念和性質(zhì)
隊列：只允許在一端進行插入數(shù)據(jù)操作，在另一端進行刪除數(shù)據(jù)操作的特殊線性表，隊列具有先進先出FIFO(First In First Out)的性質(zhì)。
隊列：進行插入操作的一端稱為隊尾
出隊列： 進行刪除操作的一端稱為隊頭
二、隊列的實現(xiàn)思路
隊列也可以數(shù)組和鏈表的結(jié)構(gòu)實現(xiàn)，使用鏈表的結(jié)構(gòu)實現(xiàn)更優(yōu)一些，因為如果使用數(shù)組的結(jié)構(gòu)，出隊列在數(shù)組頭上出數(shù)據(jù)，效率會比較低。
而鏈表我們采用雙向鏈接結(jié)構(gòu)，一個指針來維護頭節(jié)點，一個指針維護尾部節(jié)點
定義的結(jié)構(gòu)體類型如下：
typedef int QDataType;
//創(chuàng)建一個結(jié)點型結(jié)構(gòu)體
typedef struct QueueNode
{
struct QueueNode* next;
QDataType data;
}QueueNode;
//創(chuàng)建一個隊列
typedef struct Queue
{
QueueNode* head;
QueueNode* tail;
}Queue;
三、隊列相關變量的內(nèi)存布局圖
四、隊列的初始化和銷毀
//初始化隊列
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = NULL;
pq->tail = NULL;
}
//隊列銷毀
void QueueDestroy(Queue* pq)
{
assert(pq);
QueueNode* cur = pq->head;
while (cur != NULL)
{
QueueNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = NULL;
pq->tail = NULL;
}
五、隊列的接口實現(xiàn)：
1. 入數(shù)據(jù)
//入數(shù)據(jù)有兩種情況
void QueuePush(Queue* pq,QDataType x)
{
assert(pq);
QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
if (newNode == NULL)
{
perror("erron ");
exit(-1);
}
newNode->next = NULL;
newNode->data = x;
//1.入隊列時隊列為空狀態(tài)
if (pq->head == NULL)
{
pq->head = newNode;
pq->tail = newNode;
}
//2.入隊列，隊列不為空，直接在尾指針后面鏈接即可
else
{
pq->tail->next = newNode;
pq->tail = newNode;
}
}
2.出數(shù)據(jù)
//出數(shù)據(jù)，類似鏈表的頭刪
void QueuePop(Queue* pq)
{
assert(pq);
//要保證隊列不能為空
assert(pq->head != NULL);
QueueNode* next = pq->head->next;
free(pq->head);
pq->head = next;
//防止野指針出現(xiàn)，當隊列為空時要把tail指針置為空
if (pq->head == NULL)
{
pq->tail = NULL;
}
}
3.取隊頭數(shù)據(jù)
//取隊頭數(shù)據(jù)
QDataType QueueFront(Queue* pq)
{
assert(pq);
//檢驗隊列不能為空
assert(pq->head != NULL);
return pq->head->data;
}
4.取隊尾數(shù)據(jù)
//取隊尾數(shù)據(jù)
QDataType QueueBack(Queue* pq)
{
assert(pq);
//同樣要檢驗隊列不能為空
assert(pq->head != NULL);
return pq->tail->data;
}
5.獲取隊列元素個數(shù)
//獲取隊列元素個數(shù)
int QueueSize(Queue* pq)
{
assert(pq);
int count = 0;
QueueNode* cur = pq->head;
while (cur != NULL)
{
count++;
cur = cur->next;
}
return count;
}
6.判斷隊列是否為空
//判斷隊列是否為空
bool QueueEmpty(Queue* pq)
{
return pq->head == NULL;
}
總結(jié)
以上就是棧和隊列的實現(xiàn)內(nèi)容了，其中前面我只有把源文件Stack.c 和Queue.c拆開來分析了。如果想要棧和隊列的全部內(nèi)容，闊以移步到gitee上獲取
【棧的源碼鏈接，點擊即可】
【隊列的源碼鏈接，點擊即可】
到此這篇關于C語言數(shù)據(jù)結(jié)構(gòu)進階之棧和隊列的實現(xiàn)的文章就介紹到這了,更多相關C語言 數(shù)據(jù)結(jié)構(gòu) 內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
C語言實現(xiàn)BMP圖像處理(彩色圖轉(zhuǎn)灰度圖)
這篇文章主要為大家詳細介紹了C語言實現(xiàn)BMP圖像處理，彩色圖轉(zhuǎn)灰度圖，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-10-10
這篇文章主要介紹了C語言之如何求三次方根問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-12-12
C++ Primer中&、*符號的多重定義與int *p和int* p的區(qū)別講解
今天小編就為大家分享一篇關于C++Primer中&、*符號的多重定義與int *p和int* p的區(qū)別講解，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2019-04-04
這篇文章主要為大家詳細介紹了C++代碼實現(xiàn)逆波蘭式，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-11-11
這篇文章主要為大家詳細介紹了C++如何使用curl庫進行http請求，并且實現(xiàn)獲取返回的頭信息的時間，也就是獲取后臺服務的當前時間，感興趣的可以了解一下2023-07-07
C語言中fchdir()函數(shù)和rewinddir()函數(shù)的使用詳解
這篇文章主要介紹了C語言中fchdir()函數(shù)和rewinddir()函數(shù)的使用詳解,是C語言入門學習中的基礎知識,需要的朋友可以參考下2015-09-09
詳解Visual Studio 2019(VS2019) 基本操作
這篇文章主要介紹了詳解Visual Studio 2019(VS2019) 基本操作，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-03-03
C++圖論之Bellman-Ford算法和SPFA算法的實現(xiàn)
貝爾曼-福特算法（Bellman-Ford）是由理查德·貝爾曼和萊斯特·福特創(chuàng)立的，求解單源最短路徑問題的一種算法。SPFA 算法是 Bellman-Ford算法 的隊列優(yōu)化算法的別稱，通常用于求含負權(quán)邊的單源最短路徑。本文將詳解兩個算法的實現(xiàn)，需要的可以參考一下2022-06-06
C語言中回調(diào)函數(shù)的含義與使用場景詳解(2)
這篇文章主要為大家詳細介紹了C語言中回調(diào)函數(shù)的含義與使用場景，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03
在現(xiàn)實中，我們做數(shù)學題總會遇到階乘問題，這在計算機中也不例外。 那我們應該怎么實現(xiàn)呢？下面小編就為大家講解一下C語言中階乘的實現(xiàn)2022-07-07