C語言 淺談棧與隊列的定義與操作
更新時間：2021年11月04日 08:33:31 作者：王不患吖吖吖
棧和隊列，嚴格意義上來說，也屬于線性表，因為它們也都用于存儲邏輯關(guān)系為 "一對一" 的數(shù)據(jù)，但由于它們比較特殊，因此將其單獨作為一章，做重點講解
棧的定義
棧同樣是一種線性表，它的特性是插入元素必須從后面插入，刪除元素也是從后面刪除，進行數(shù)據(jù)刪除和插入的一端稱為棧頂，另一端是棧底。
壓?！褪遣迦朐?br />
出棧—就是刪除元素
它可以用數(shù)組實現(xiàn)也可以用鏈表實現(xiàn)
但是用數(shù)組實現(xiàn)更好，因為鏈表的插入和刪除要進行遍歷，而數(shù)組可以進行隨機訪問，從而時間復(fù)雜度更低。
棧的實現(xiàn)
前置
棧的元素需要表明容量，還有棧頂
typedef int SDType;
typedef struct Srack
{
SDType* a;
int top;
int capacity;
}ST;
初始化棧
把元素置為空，棧頂在下標為0的位置
void StackInit(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}
棧的銷毀
不再贅述
void StackDestrory(ST* ps)
{
assert(ps);
free(ps);
ps=NULL;
ps->capacity = ps->top = 0;
}
棧的插入
先判空，如果容量滿了，進行增容，把棧頂元素進行賦值，再把棧頂指針加一
void StackPush(ST* ps, SDType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
SDType* tmp = (SDType)realloc(ps->capacity, sizeof(SDType) * newCapacity);
if (tmp == NULL)
{
printf("Realloc fail!\n");
}
else
{
ps->a = tmp;
ps->capacity = newCapacity;
}
}
ps->a[ps->top] = x;
ps->top++;
}
出棧的操作
棧頂指針減一即可
void StackPop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
ps->top--;
}
取棧頂元素
先進行判空，不空的話直接取出棧頂指針指向的元素
SDType StackTop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps -> a[ps->top - 1];
}
棧的大小
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}
判斷棧是否為空
bool StackEmpty(ST* ps)
{
return ps->top == 0;
}
隊列的定義
隊列只允許在一段進行插入操作，一段進行刪除操作，在隊尾進行插入，在隊頭進行刪除
隊列的基本操作
隊列的初始化
我們在進行基本操作的時候要用到頭指針和尾指針
void QueueInit(Queue* pq)
{
assert(pq != NULL);
pq->head = NULL;
pq->tail = NULL;
}
隊列的銷毀
將臨時指針cur被賦值為head，保存下一個，遍歷進行刪除，最后把頭指針和尾指針進行free
void QueueDestroy(Queue* pq)
{
assert(pq != NULL);
QueueNode* cur = pq->head;
QueueNode* next = cur->next;
while (cur)
{
free(cur);
cur = next;
next = next->next;
}
pq->head = pq->tail = NULL;
}
隊列的插入
隊列只能從隊尾查，如果開始的時候隊頭和隊尾重合，那就直接進行插入，
如果不，那就找到尾，在尾后邊進行插入
void QueuePush(Queue* pq,QDataType x)
{
assert(pq);
QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
newNode->data = x;
newNode->next = NULL;
if (pq->head == NULL)
{
pq->head = pq->tail = newNode;
}
else
{
pq->tail->next = newNode;
pq->tail = newNode;
}
}
隊列的刪除
很簡單，刪除隊尾頭元素，先保存下一個，再把隊頭復(fù)制給新的
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
QueueNode* NewHead = pq->head->next;
free(pq->head);
pq->head = NewHead;
if (pq->head == NULL)
{
pq->tail = NULL;
}
}
隊列的判空
是否隊頭指向空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL;
}
取出隊頭元素
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}
取出隊尾元素
先判空
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}
隊列的大小
直接遍歷就行
int QueueSize(Queue* pq)
{
assert(pq);
int n = 0;
QueueNode* cur = pq->head;
while (cur)
{
cur = cur->next;
n++;
}
return n;
}
點個贊把
到此這篇關(guān)于C語言 淺談棧與隊列的定義與操作的文章就介紹到這了,更多相關(guān)C語言 棧與隊列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
win10環(huán)境下vscode Linux C++開發(fā)代碼自動提示配置(基于WSL)
這篇文章主要介紹了win10環(huán)境下vscode Linux C++開發(fā)代碼自動提示配置(基于WSL),文中通過示例代碼介紹的非常詳細，對大家的學(xué)習或者工作具有一定的參考學(xué)習價值，需要的朋友們下面隨著小編來一起學(xué)習學(xué)習吧2020-05-05
下面小編就為大家?guī)硪黄狢++ 賦值構(gòu)造函數(shù)注意點介紹。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-12-12
快速排序時間復(fù)雜度為O(nlogn)，是數(shù)組相關(guān)的題目當中經(jīng)常會用到的算法,下面這篇文章主要給大家介紹了關(guān)于C語言實現(xiàn)快速排序算法的相關(guān)資料,需要的朋友可以參考下2022-06-06
這篇文章主要為大家詳細介紹了C語言實現(xiàn)校園導(dǎo)游系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03
C++使用easyX庫實現(xiàn)三星環(huán)繞效果流程詳解
EasyX是針對C/C++的圖形庫，可以幫助使用C/C++語言的程序員快速上手圖形和游戲編程。這篇文章主要介紹了C++使用easyX庫實現(xiàn)三星環(huán)繞效果，需要的可以參考一下2022-10-10
這篇文章主要為大家詳細介紹了基于easyx的C++實現(xiàn)貪吃蛇，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-10-10
類是創(chuàng)建對象的模板，一個類可以創(chuàng)建多個對象，每個對象都是類類型的一個變量；創(chuàng)建對象的過程也叫類的實例化。每個對象都是類的一個具體實例（Instance），擁有類的成員變量和成員函數(shù)2021-10-10
這篇文章主要為大家介紹了C語言共用體union作用的使用示例教程，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-02-02
這篇文章主要介紹了C++編程中new運算符的使用學(xué)習教程,是C++入門學(xué)習中的基礎(chǔ)知識,需要的朋友可以參考下2016-01-01
做OTA升級功能時，我們能直接拿到的往往只是升級包的鏈接，需要我們自己去下載，這時候就需要用到http下載器。本文將利用C語言實現(xiàn)簡單的http下載器，感興趣的可以了解一下2022-12-12