柚子快報(bào)邀請(qǐng)碼778899分享：c語言 數(shù)據(jù)結(jié)構(gòu)——隊(duì)列和棧
柚子快報(bào)邀請(qǐng)碼778899分享：c語言 數(shù)據(jù)結(jié)構(gòu)——隊(duì)列和棧
目錄
一、棧
????????1、概念與結(jié)構(gòu)
? ? ? ? 2、棧的結(jié)構(gòu)與初始化
? ? ? ? 3、入棧
????????4、出棧?
????????5、取棧頂元素?
????????6、取棧中有效元素個(gè)數(shù)?
?????????7、棧是否為空
?二、隊(duì)列
? ? ? ? ?1、概念與結(jié)構(gòu)
? ? ? ? 2、隊(duì)列的結(jié)構(gòu)與初始化
?????????3、入隊(duì)列
?????????4、出隊(duì)列
?????????5、取隊(duì)頭數(shù)據(jù)
?????????6、取隊(duì)尾數(shù)據(jù)
? ? ? ? ?7、隊(duì)列判空
?????????8、隊(duì)列中有效元素個(gè)數(shù)
?練習(xí)題目鏈
一、棧
????????1、概念與結(jié)構(gòu)
????????棧：?種特殊的線性表，其只允許在固定的?端進(jìn)?插?和刪除元素操作，進(jìn)?數(shù)據(jù)插?和刪除操作的?端稱為棧頂，另?端稱為棧底。棧中的數(shù)據(jù)元素遵守后進(jìn)先出LIFO（Last In First Out）的原則。
????????壓棧：棧的插?操作叫做進(jìn)棧/壓棧/?棧，?數(shù)據(jù)在棧頂。
????????出棧：棧的刪除操作叫做出棧。出數(shù)據(jù)也在棧頂。
? ? ? ? 棧的底層邏輯實(shí)現(xiàn)，可以是使用順序表實(shí)現(xiàn)也可以使用鏈表表實(shí)現(xiàn)，我這里采用的是動(dòng)態(tài)順序表實(shí)現(xiàn)
????????棧的實(shí)現(xiàn)?般可以使?數(shù)組或者鏈表實(shí)現(xiàn)，相對(duì)??數(shù)組的結(jié)構(gòu)實(shí)現(xiàn)更優(yōu)?些。因?yàn)閿?shù)組在尾上插?數(shù)據(jù)的代價(jià)?較?
? ? ? ? 2、棧的結(jié)構(gòu)與初始化
// ?！筮M(jìn)先出
struct stack
{
int* data;//棧
int top;//棧頂元素位置
int capacity;//棧的容量
};
//棧初始化
void stackinit(struct stack* stack)
{
//設(shè)置棧頂位置
stack->top = 0;
//初始棧的容量為4
stack->capacity = 4;
//創(chuàng)建數(shù)組
stack->data = (int*)malloc(sizeof(int) * stack->capacity);
}
? ? ? ? 3、入棧
? ? ? ? ?時(shí)間復(fù)雜度：O（ 1 ）
? ? ? ? 在棧的結(jié)構(gòu)中 top 時(shí)刻記錄著棧頂?shù)奈恢?，直接插入即可，因此時(shí)間復(fù)雜度為O（ 1 ）
? ? ? ? 注意在插入前要檢查棧是否已經(jīng)滿了，如果滿了要擴(kuò)容?
//棧頂插入元素
void stackpush(struct stack* stack, int x)
{
//判斷是否需要擴(kuò)容
if (stack->top == stack->capacity)
{
//擴(kuò)容至當(dāng)前棧容量的兩倍
stack->capacity = stack->capacity * 2;
//更新棧
int* newstack = (int*)realloc(stack->data, sizeof(int) * stack->capacity);
//創(chuàng)建失敗
if (newstack)
{
assert("error");
}
stack->data = newstack;
}
//棧頂插入元素
stack->data[stack->top] = x;
//棧頂加一
stack->top++;
}
????????4、出棧?
?????????時(shí)間復(fù)雜度：O（ 1 ）
?????????在棧的結(jié)構(gòu)中 top 時(shí)刻記錄著棧頂?shù)奈恢?，直接減少棧中有效元素即可，因此時(shí)間復(fù)雜度為O（ 1 ）
//棧頂刪除元素
void stackpop(struct stack* arr)
{
//棧不能為空
if (arr->top == 0)
{
return;
}
//出棧
arr->top--;
}
????????5、取棧頂元素?
????????時(shí)間復(fù)雜度：O（ 1 ）
?????????在棧的結(jié)構(gòu)中 top 時(shí)刻記錄著棧頂?shù)奈恢茫苯臃祷丶纯?，因此時(shí)間復(fù)雜度為O（ 1 ）
//查找棧頂元素
int stacktop(struct stack* arr)
{
//棧不能為空
if (arr->top != 0)
{
assert("stack is NULL");
}
//返回棧頂元素
return arr->data[(arr->top) - 1];
}
????????6、取棧中有效元素個(gè)數(shù)?
????????時(shí)間復(fù)雜度：O（ 1 ）
?????????在棧的結(jié)構(gòu)中 top 時(shí)刻記錄著棧頂?shù)奈恢?，也是棧中有效元素個(gè)數(shù)直接返回即可，因此時(shí)間復(fù)雜度為O（ 1 ）
//查找棧中元素個(gè)數(shù)
int stacksize(struct stack* arr)
{
//查找棧中元素個(gè)數(shù)
return arr->top;
}
?????????7、棧是否為空
?????????時(shí)間復(fù)雜度：O（ 1 ）
? ? ? ? 判斷棧中元素個(gè)數(shù)是否為零?
//判斷棧是否為空
int stackempty(struct stack* arr)
{
//判斷棧是否為空
if (arr->top != 0)
{
return 1;
}
else
{
return 0;
}
}
?二、隊(duì)列
? ? ? ? ?1、概念與結(jié)構(gòu)
? ? ? ? 隊(duì)列：只允許在?端進(jìn)?插?數(shù)據(jù)操作，在另?端進(jìn)?刪除數(shù)據(jù)操作的特殊線性表，隊(duì)列具有先進(jìn)先出FIFO(First In First Out)
?????????隊(duì)列：進(jìn)?插?操作的?端稱為隊(duì)尾
????????出隊(duì)列：進(jìn)?刪除操作的?端稱為隊(duì)頭
?????????隊(duì)列也可以數(shù)組和鏈表的結(jié)構(gòu)實(shí)現(xiàn)，使?鏈表的結(jié)構(gòu)實(shí)現(xiàn)更優(yōu)?些，因?yàn)槿绻?數(shù)組的結(jié)構(gòu)，出隊(duì)列在數(shù)組頭上出數(shù)據(jù)，效率會(huì)?較低，這里我使用鏈表實(shí)現(xiàn)
? ? ? ? 2、隊(duì)列的結(jié)構(gòu)與初始化
//隊(duì)列節(jié)點(diǎn)
struct queuenode
{
int data;//存儲(chǔ)數(shù)據(jù)
struct queuenode* next;//下一個(gè)元素的地址
};
//隊(duì)列，維護(hù)隊(duì)列的隊(duì)尾和對(duì)頭
struct queue
{
struct queuenode* head;//隊(duì)頭
struct queuenode* tail;//隊(duì)尾
int size;//隊(duì)列有效元素個(gè)數(shù)
};
//隊(duì)列初始化
void queueinit(struct queue* queue)
{
//初始為空
queue->head = NULL;
queue->tail = NULL;
//初始隊(duì)列中元素個(gè)數(shù)為0
queue->size = 0;
}
?????????3、入隊(duì)列
????????時(shí)間復(fù)雜度：O（ 1?）?
? ? ? ? 我們有維護(hù)隊(duì)列的尾節(jié)點(diǎn)，創(chuàng)建一個(gè)新節(jié)點(diǎn)在尾節(jié)點(diǎn)后插入同時(shí)更新尾節(jié)點(diǎn)的指向?，因此時(shí)間復(fù)雜度為O（ 1 ）
//隊(duì)列——插入
void queuepush(struct queue* list, int x)
{
//創(chuàng)建隊(duì)列節(jié)點(diǎn)，并初始化
struct queuenode* node = calloc(1, sizeof(struct queuenode));
node->data = x;
node->next = NULL;
//隊(duì)列中沒有元素時(shí)，對(duì)頭和隊(duì)尾都為新創(chuàng)建的節(jié)點(diǎn)
if (list->head == NULL)
{
list->head = node;
list->tail = node;
}
else
{
//隊(duì)尾的下一個(gè)節(jié)點(diǎn)為新創(chuàng)建的節(jié)點(diǎn)
list->tail->next = node;
//更改隊(duì)尾節(jié)點(diǎn)的指向
list->tail = node;
}
//隊(duì)列有效元素個(gè)數(shù)加一
list->size++;
}
?????????4、出隊(duì)列
?????????時(shí)間復(fù)雜度：O（ 1?）?
? ? ? ? 刪除頭節(jié)點(diǎn)，并更新頭節(jié)點(diǎn)為頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，?因此時(shí)間復(fù)雜度為O（ 1 ）
//隊(duì)列——?jiǎng)h除
void queuepop(struct queue* list)
{
//隊(duì)列不能為空
if (list->head == NULL)
{
assert(list->head);
}
//保存對(duì)頭的下一個(gè)節(jié)點(diǎn)
struct queuenode* cur = list->head->next;
//刪除隊(duì)頭
free(list->head);
//更改對(duì)頭的指向
list->head = cur;
//當(dāng)對(duì)頭為空時(shí)，隊(duì)尾也要為空
if (cur == NULL)
{
list->tail = NULL;
}
//隊(duì)列有效元素減一
list->size--;
}
?????????5、取隊(duì)頭數(shù)據(jù)
?????????時(shí)間復(fù)雜度：O（ 1?）?
? ? ? ? 這里有維護(hù)頭節(jié)點(diǎn)，直接返回頭節(jié)點(diǎn)數(shù)據(jù)，因此時(shí)間復(fù)雜度為O（ 1 ）
//隊(duì)列——返回對(duì)頭數(shù)據(jù)
int queuefront(struct queue* list)
{
//隊(duì)列不能為空
if (list->head == NULL)
{
assert(list->head);
}
//返回對(duì)頭數(shù)據(jù)
return list->head->data;
}
?????????6、取隊(duì)尾數(shù)據(jù)
????????時(shí)間復(fù)雜度：O（ 1?）??
????????這里有維護(hù)尾節(jié)點(diǎn)，直接返回頭節(jié)點(diǎn)數(shù)據(jù)，因此時(shí)間復(fù)雜度為O（ 1 ）?
//隊(duì)列——返回隊(duì)尾數(shù)據(jù)
int queueback(struct queue* list)
{
//隊(duì)列不能為空
if (list->tail == NULL)
{
assert(list->tail);
}
//返回隊(duì)尾數(shù)據(jù)
return list->tail->data;
}
? ? ? ? ?7、隊(duì)列判空
?????????時(shí)間復(fù)雜度：O（ 1?）??
????????判斷隊(duì)列中的有效元素個(gè)數(shù)是否為0?
//隊(duì)列——判斷隊(duì)列是否為空
int queueempty(struct queue* list)
{
//隊(duì)列——判斷隊(duì)列是否為空
if (list->head == NULL)
{
return 0;
}
else
{
return 1;
}
}
?????????8、隊(duì)列中有效元素個(gè)數(shù)
????????時(shí)間復(fù)雜度：O（ 1?）??
?????????這里有維護(hù)隊(duì)列中有效元素個(gè)數(shù)，直接返回，因此時(shí)間復(fù)雜度為O（ 1 ）
//隊(duì)列——返回隊(duì)列有效元素個(gè)數(shù)
int queuesize(struct queue* list)
{
//返回答案
return list->size;
}
?練習(xí)題目鏈
? ? ? ? 數(shù)據(jù)結(jié)構(gòu)最好的鞏固就是寫算法題目也是最好的體現(xiàn)，學(xué)習(xí)了不代表學(xué)會(huì)了，一定要加以實(shí)踐
????????20. 有效的括號(hào) - 力扣（LeetCode）?
????????225. 用隊(duì)列實(shí)現(xiàn)棧 - 力扣（LeetCode）?
????????232. 用棧實(shí)現(xiàn)隊(duì)列 - 力扣（LeetCode）
????????155. 最小棧 - 力扣（LeetCode）?
? ? ? ? 更多的可以在力扣上寫：?力扣 (LeetCode) 全球極客摯愛的技術(shù)成長(zhǎng)平臺(tái)
柚子快報(bào)邀請(qǐng)碼778899分享：c語言 數(shù)據(jù)結(jié)構(gòu)——隊(duì)列和棧
好文推薦
本文內(nèi)容根據(jù)網(wǎng)絡(luò)資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀點(diǎn)和立場(chǎng)。
轉(zhuǎn)載請(qǐng)注明，如有侵權(quán)，聯(lián)系刪除。
BOL海外優(yōu)選坊
