C語言 淺談棧與隊列的定義與操作
更新時間：2021年11月04日 08:33:31 作者：王不患吖吖吖
棧和隊列，嚴格意義上來說，也屬于線性表，因為它們也都用于存儲邏輯關系為 "一對一" 的數(shù)據，但由于它們比較特殊，因此將其單獨作為一章，做重點講解
棧的定義
棧同樣是一種線性表，它的特性是插入元素必須從后面插入，刪除元素也是從后面刪除，進行數(shù)據刪除和插入的一端稱為棧頂，另一端是棧底。
壓?！褪遣迦朐?br />
出棧—就是刪除元素
它可以用數(shù)組實現(xiàn)也可以用鏈表實現(xiàn)
但是用數(shù)組實現(xiàn)更好，因為鏈表的插入和刪除要進行遍歷，而數(shù)組可以進行隨機訪問，從而時間復雜度更低。
棧的實現(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;
}
}
隊列的刪除
很簡單，刪除隊尾頭元素，先保存下一個，再把隊頭復制給新的
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;
}
點個贊把
到此這篇關于C語言 淺談棧與隊列的定義與操作的文章就介紹到這了,更多相關C語言 棧與隊列內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要介紹了C++ sort 排序(降序、升序)使用總結,需要的朋友可以參考下2020-11-11
模板類vector是一個動態(tài)數(shù)組，類似于string類，可存放任意類型，能夠末尾、中間增加數(shù)據，基本上是是new創(chuàng)建動態(tài)數(shù)組的替代品，vector可以自動完成new和delete2022-08-08
這篇文章主要為大家詳細介紹了C語言職工信息管理系統(tǒng)源碼，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-01-01
undefined reference to `SetPduPowerConsumptionCnt''錯誤的解決方法
編譯時出現(xiàn)undefined reference to `SetPduPowerConsumptionCnt'錯誤要如何解決呢？有沒有什么好的解決方法？下面小編就為大家解答吧，如果你也遇到了這種情況，可以過來參考下2013-07-07
C++文件關鍵詞快速定位出現(xiàn)的行號實現(xiàn)高效搜索
這篇文章主要為大家介紹了C++文件關鍵詞快速定位出現(xiàn)的行號實現(xiàn)高效搜索,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-10-10
在宏定義中，“宏名稱”和“宏字符串”是通過“空格”來區(qū)分的,某些朋友不要混淆了，接下來請祥看本文2012-12-12
這篇文章主要介紹了C++ 封裝 DLL 供 C# 調用（以C# 調用C++ 二次封裝的VLC播放庫為介質，支持回調函數(shù)的封裝）,需要的朋友可以參考下面我文章的具體內容2021-09-09
這篇文章主要為大家詳細介紹了C++全密碼生成的實現(xiàn)代碼，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-10-10
這篇文章主要為大家詳細介紹了C++實現(xiàn)高校教室管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03
這篇文章主要為大家整理并介紹了C語言編程必背的示例代碼大全，有需要的朋友可以借鑒參考下，希望能夠有所幫助2021-11-11