前言
前面兩篇文章講述了關(guān)于線性表中的順序表與鏈表，這篇文章繼續(xù)講述線性表中的棧和隊列。
這里講述的兩種線性表與前面的線性表不同，只允許在一端入數(shù)據(jù)，一段出數(shù)據(jù)，詳細(xì)內(nèi)容請看下面的文章。
順序表與鏈表兩篇文章的鏈接：
線性表之順序表
線性表之鏈表
注意： 本文提到的效率全部為空間復(fù)雜度?。。。?/p>
一、棧
1. 棧的概念
棧:一種特殊的線性表，其只允許在固定的一端進(jìn)行插入和刪除元素操作。進(jìn)行數(shù)據(jù)插入和刪除操作的一端稱為棧頂，另一端稱為棧底。棧中的數(shù)據(jù)元素遵守后進(jìn)先出LIFO (Last ln FirstOut)的原則.
入棧:棧的插入操作叫做進(jìn)棧/壓棧/入棧，入數(shù)據(jù)在棧頂。
出棧:棧的刪除操作叫做出棧。出數(shù)據(jù)也在棧頂。
2. 棧的結(jié)構(gòu)
棧的結(jié)構(gòu)決定了棧只能在棧頂入數(shù)據(jù)，棧頂出數(shù)據(jù)，并且遵循著后進(jìn)先出的原則。
2.1 選擇數(shù)據(jù)結(jié)構(gòu)完成棧（數(shù)組 or 鏈表)
2.1.1 數(shù)組
前面學(xué)習(xí)過順序表就能知道，數(shù)組只有尾插和尾刪的效率高為 O(1) , 而靠近頭的位置的插入刪除的效率比較低為O(N)。
而對于棧這種只能在棧頂插入、刪除的數(shù)據(jù)結(jié)構(gòu)可謂是完美契合數(shù)組的優(yōu)點。
2.1.2 鏈表
前面學(xué)習(xí)過鏈表就可以知道，對于單鏈表的頭插、頭刪的效率非常高為 O(1) , 而它的尾插、尾刪需要找尾，效率比較低為 O(N)。
若以單鏈表的頭為棧底，尾為棧頂，則入棧、出棧相當(dāng)于單鏈表的尾插、尾刪效率并不高。
顯然這不是我們的最佳選項，但是若用一個變量記錄尾的情況下，尾插、尾刪的效率也可以達(dá)到O(1)。
若以單鏈表的頭為棧頂，尾為棧底，則入棧、出棧相當(dāng)于單鏈表的頭插、頭刪效率非常高為O(1)。
這里與前面的數(shù)組差不多，也是棧的操作完全契合單鏈表的優(yōu)點。
棧能夠使用單鏈表實現(xiàn)，當(dāng)然也可以用帶頭雙向循環(huán)鏈表實現(xiàn)，但是我認(rèn)為這里使用帶頭雙向循環(huán)鏈表有點大炮打蚊子，大材小用的感覺。
2.1.3 我選擇用數(shù)組完成棧
為什么這里選擇數(shù)組完成棧呢？
明明數(shù)組容量不足時擴(kuò)容需要消耗，而鏈表沒有這個消耗，為什么不用鏈表？
原因有以下幾點：
- 由于數(shù)組物理結(jié)構(gòu)上是連續(xù)的，緩存命中率高，訪問效率高。
- 相比鏈表，數(shù)組只需要存儲數(shù)據(jù)，而鏈表每一個節(jié)點還需要存下一個節(jié)點的地址。
- 雖然數(shù)組擴(kuò)容有消耗，但是鏈表每次申請節(jié)點的時候也會有消耗。
2.2 棧的操作
3. 棧的實現(xiàn)
Stack.h頭文件的實現(xiàn)
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
// 支持動態(tài)增長的棧
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top; // 棧頂
int capacity; // 容量
}Stack;
// 初始化棧
void StackInit(Stack* ps);
// 入棧
void StackPush(Stack* ps, STDataType data);
// 出棧
void StackPop(Stack* ps);
// 獲取棧頂元素
STDataType StackTop(Stack* ps);
// 獲取棧中有效元素個數(shù)
int StackSize(Stack* ps);
// 檢測棧是否為空，如果為空返回非零結(jié)果，如果不為空返回0
int StackEmpty(Stack* ps);
// 銷毀棧
void StackDestroy(Stack* ps);
Stack.c文件的實現(xiàn)
3.1 初始化棧
棧的初始化將傳入函數(shù)的結(jié)構(gòu)體進(jìn)行初始化：
a. 棧頂初始化的時候注意有兩種情況:
1. top指向棧頂元素
2. top指向棧頂元素的后面一個位置
當(dāng)然都可以，我選擇 1 僅僅方便我自己理解
b. 是否在初始化的時候給棧申請部分空間
當(dāng)然都可以，我這里選擇不申請空間，在后面用realloc函數(shù)申請和擴(kuò)容空間。
// 初始化棧
void StackInit(Stack* ps)
{
assert(ps);
ps->capacity = 0;
//ps->top = -1; //top指向棧頂
ps->top = 0; //top指向棧頂?shù)暮竺嬉粋€元素
ps->a = NULL;
}
3.2 入棧
當(dāng)數(shù)據(jù)入棧時需要判斷棧是否為滿，若為滿則需要擴(kuò)容，這里的StackFull函數(shù)其實并沒有必要，由于棧只有尾插這一個插入操作不需要復(fù)用擴(kuò)容操作，所以可以直接寫在入棧操作中。
注意：
當(dāng)realloc()函數(shù)的參數(shù)為NULL時，其作用與malloc()函數(shù)的作用一樣。
void StackFull(Stack* ps)
{
assert(ps);
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
if (tmp == NULL)
{
perror("realloc");
return;
}
ps->a = tmp;
ps->capacity = newcapacity;
}
// 入棧
void StackPush(Stack* ps, STDataType data)
{
assert(ps);
if (ps->capacity == ps->top)
StackFull(ps);
ps->a[ps->top] = data;
ps->top++;
}
3.3 判空
前面假設(shè)了top是指向棧頂元素后面一個位置，所以當(dāng) top 指向 0 的時候棧是空的。
// 檢測棧是否為空，如果為空返回非零結(jié)果，如果不為空返回0
int StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;
}
3.4 出棧
執(zhí)行出棧操作時，棧不能為空，且只需要 top-- ， 不需要將其數(shù)據(jù)抹除。
// 出棧
void StackPop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
//棧為空，則不能繼續(xù)出棧
ps->top--;
}
3.5 取棧頂元素
與出棧操作一樣，取棧頂元素時，棧不能為空。
且top是指向棧頂元素后面一個位置，所以取棧頂元素時取的是 top - 1 指向的元素。
// 獲取棧頂元素
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
//棧為空，則無棧頂元素
return ps->a[ps->top - 1];
}
3.6 獲取棧中有效元素個數(shù)
由于top是指向棧頂元素的下一個位置，而元素個數(shù)正好是下標(biāo) + 1 ，也就是top。
// 獲取棧中有效元素個數(shù)
int StackSize(Stack* ps)
{
assert(ps);
return ps->top; //由于top是指向棧頂元素的下一個位置
//而元素個數(shù)正好是下標(biāo) + 1 ，也就是top
}
3.7 銷毀棧
// 銷毀棧
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}
4. 整體代碼的實現(xiàn)
#include "Stack.h"
// 初始化棧
void StackInit(Stack* ps)
{
assert(ps);
ps->capacity = 0;
ps->top = 0; //top指向棧頂?shù)暮竺嬉粋€元素
ps->a = NULL;
}
void StackFull(Stack* ps)
{
assert(ps);
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
if (tmp == NULL)
{
perror("realloc");
return;
}
ps->a = tmp;
ps->capacity = newcapacity;
}
// 入棧
void StackPush(Stack* ps, STDataType data)
{
assert(ps);
if (ps->capacity == ps->top)
StackFull(ps);
ps->a[ps->top] = data;
ps->top++;
}
// 檢測棧是否為空，如果為空返回非零結(jié)果，如果不為空返回0
int StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;
}
// 出棧
void StackPop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
//棧為空，則不能繼續(xù)出棧
ps->top--;
}
// 獲取棧頂元素
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
//棧為空，則無棧頂元素
return ps->a[ps->top - 1];
}
// 獲取棧中有效元素個數(shù)
int StackSize(Stack* ps)
{
assert(ps);
return ps->top; //由于top是指向棧頂元素的下一個位置
//而元素個數(shù)正好是下標(biāo) + 1 ，也就是top
}
// 銷毀棧
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}
二、隊列
1. 隊列的概念
隊列:只允許在一端進(jìn)行插入數(shù)據(jù)操作，在另一端進(jìn)行刪除數(shù)據(jù)操作的特殊線性表，隊列具有 先進(jìn)先出 FIFO(First In First Out) 的原則。
入隊列:進(jìn)行插入操作的一端稱為隊尾
出隊列:進(jìn)行刪除操作的一端稱為隊頭
2. 隊列的結(jié)構(gòu)
2.1 選擇數(shù)據(jù)結(jié)構(gòu)完成隊列（數(shù)組 or 鏈表)
2.1.1 數(shù)組
前面學(xué)習(xí)過順序表就能知道，數(shù)組只有尾插和尾刪的效率高為 O(1) , 而靠近頭的位置的插入刪除的效率比較低為O(N)。
而對于隊列這種只能在隊尾插入、對頭刪除的數(shù)據(jù)結(jié)構(gòu)，無論隊頭和隊尾定義在哪，使用數(shù)組完成必定會有頭刪或頭插，會使得隊列的效率降低，所以不建議使用數(shù)組完成。
2.1.2 鏈表
前面學(xué)習(xí)過鏈表就可以知道，對于單鏈表的頭插、頭刪的效率非常高為 O(1) , 而它的尾插、尾刪需要找尾，效率比較低為 O(N)。
(1)若以單鏈表的頭為隊頭，尾為隊尾，則入隊列、出隊列相當(dāng)于單鏈表的尾插、頭刪效率并不高。
(2)若以單鏈表的頭為隊尾，尾為隊頭，則入隊列、出隊列相當(dāng)于單鏈表的頭插、尾刪效率并不高。
雖然兩種情況都有一種操作效率為O(N) , 但是這兩種情況都是與尾有關(guān)的操作，
所以只要在結(jié)構(gòu)體中定一個記錄尾的成員，那么尾插、尾刪的效率就能達(dá)到O(1).
2.1.3 我選擇用鏈表完成隊列
為什么這里選擇鏈表完成隊列？
通過上面的講述原因已經(jīng)顯而易見了。
原因如下：
由于無論怎么改造數(shù)組都會有一個操作效率為 O(N),而鏈表只需要改變結(jié)構(gòu)體，使其多一個指向尾的成員，就能使隊列的插入、刪除的操作效率為O(1).
3. 隊列的實現(xiàn)
Queue.h頭文件的實現(xiàn)
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int QDataType;
// 鏈?zhǔn)浇Y(jié)構(gòu)：表示隊列
typedef struct QListNode
{
struct QListNode* next;
QDataType data;
}QNode;
// 隊列的結(jié)構(gòu)
typedef struct Queue
{
QNode* front;
QNode* rear; //指向隊列最后一個元素的后面
int size;
}Queue;
// 初始化隊列
void QueueInit(Queue* q);
// 隊尾入隊列
void QueuePush(Queue* q, QDataType data);
// 隊頭出隊列
void QueuePop(Queue* q);
// 獲取隊列頭部元素
QDataType QueueFront(Queue* q);
// 獲取隊列隊尾元素
QDataType QueueBack(Queue* q);
// 獲取隊列中有效元素個數(shù)
int QueueSize(Queue* q);
// 檢測隊列是否為空，如果為空返回非零結(jié)果，如果非空返回0
int QueueEmpty(Queue* q);
// 銷毀隊列
void QueueDestroy(Queue* q);
Queue.c文件的實現(xiàn)
3.1 初始化隊列
這里隊列的front指向隊頭，rear指向隊尾。
當(dāng)隊列為空的時候，那么front和rear 都是指向 NULL。
// 初始化隊列
void QueueInit(Queue* q)
{
q->front = NULL;
q->rear = NULL;
q->size = 0;
}
3.2 隊尾入隊列
由于使用鏈表實現(xiàn)隊列，插入時需要申請一個節(jié)點。
入隊列分為兩種情況：
- 隊列為空時，需要改變隊頭、隊尾的指針。
- 隊列不為空時，只需要將新節(jié)點接到隊尾，并將尾指針向后移動即可。
// 隊尾入隊列
void QueuePush(Queue* q, QDataType data)
{
assert(q);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc");
return;
}
newnode->next = NULL;
newnode->data = data;
if (q->front == NULL) //分隊列是否有元素兩種情況
{ //隊列為空
assert(q->rear == NULL);
q->front = newnode;
q->rear = newnode;
}
else
{ //隊列不為空
q->rear->next = newnode;
q->rear = newnode;
}
q->size++;//入隊列，隊列長度加一
}
3.3 判空
當(dāng)隊列中的頭、尾指針都指向NULL的時候為隊列為空。
// 檢測隊列是否為空，如果為空返回非零結(jié)果，如果非空返回0
int QueueEmpty(Queue* q)
{
assert(q);
return q->front == NULL && q->rear == NULL;
}
3.4 隊頭出隊列
出隊列分為兩種情況：
- 隊列中只有一個元素時：刪除最后一個節(jié)點，并將
front和rear指向NULL。 - 隊列中有多個元素時：刪除
front指向的節(jié)點，并將front向后移動。
// 隊頭出隊列
void QueuePop(Queue* q)
{
assert(q);
//出隊列時，隊列不能為空
assert(!QueueEmpty(q));
//當(dāng)隊列中只有一個元素的時候，不僅僅頭指針需要改變，尾指針也需要改變
//因為當(dāng)刪除最后一個元素時，首指針釋放當(dāng)前節(jié)點，并向后移動，而尾指針并沒有移動
//當(dāng)釋放后若在插入元素時，尾指針會造成野指針的情況
if (q->front->next == NULL)
{
QNode* del = q->front;
q->front = NULL;
q->rear = NULL;
free(del);
}
else
{
QNode* del = q->front;
q->front = q->front->next;
free(del);
}
q->size--;
}
3.5 獲取隊列頭部元素
front 指向的節(jié)點存儲著頭部元素。
// 獲取隊列頭部元素
QDataType QueueFront(Queue* q)
{
assert(q);
//獲取隊列頭部元素時，隊列不能為空
assert(!QueueEmpty(q));
return q->front->data;
}
3.6 獲取隊列隊尾元素
rear 指向的節(jié)點存儲著尾元素。
// 獲取隊列隊尾元素
QDataType QueueBack(Queue* q)
{
assert(q);
//獲取隊列頭部元素時，隊列不能為空
assert(!QueueEmpty(q));
return q->rear->data;
}
3.7 獲取隊列中有效元素個數(shù)
結(jié)構(gòu)體中的 size 存儲著隊列中的有效元素個數(shù)
// 獲取隊列中有效元素個數(shù)
int QueueSize(Queue* q)
{
assert(q);
//結(jié)構(gòu)體中定義了一個size
//而這里遍歷鏈表得到個數(shù)，效率低O(N)
/*int size = 0; 不要用
QNode* cur = q->front;
while (cur != q->rear)
{
size++;
q->front = q->front->next;
}*/
return q->size;
}
3.8 銷毀隊列
銷毀隊列與前面銷毀單鏈表相同，需要將每一個節(jié)點都釋放。
// 銷毀隊列
void QueueDestroy(Queue* q)
{
assert(q);
QNode* cur = q->front;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
}
4. 整體代碼的實現(xiàn)
// 初始化隊列
void QueueInit(Queue* q)
{
q->front = NULL;
q->rear = NULL;
q->size = 0;
}
// 隊尾入隊列
void QueuePush(Queue* q, QDataType data)
{
assert(q);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc");
return;
}
newnode->next = NULL;
newnode->data = data;
if (q->front == NULL) //分隊列是否有元素兩種情況
{
assert(q->rear == NULL);
q->front = newnode;
q->rear = newnode;
}
else
{
q->rear->next = newnode;
q->rear = newnode;
}
q->size++;//入隊列，隊列長度加一
}
// 檢測隊列是否為空，如果為空返回非零結(jié)果，如果非空返回0
int QueueEmpty(Queue* q)
{
assert(q);
return q->front == NULL && q->rear == NULL;
}
// 隊頭出隊列
void QueuePop(Queue* q)
{
assert(q);
//出隊列時，隊列不能為空
assert(!QueueEmpty(q));
//當(dāng)隊列中只有一個元素的時候，不僅僅頭指針需要改變，尾指針也需要改變
//因為當(dāng)刪除最后一個元素時，首指針釋放當(dāng)前節(jié)點，并向后移動，而尾指針并沒有移動
//當(dāng)釋放后若在插入元素時，尾指針會造成野指針的情況
if (q->front->next == NULL)
{
QNode* del = q->front;
q->front = NULL;
q->rear = NULL;
free(del);
}
else
{
QNode* del = q->front;
q->front = q->front->next;
free(del);
}
q->size--;
}
// 獲取隊列頭部元素
QDataType QueueFront(Queue* q)
{
assert(q);
//獲取隊列頭部元素時，隊列不能為空
assert(!QueueEmpty(q));
return q->front->data;
}
// 獲取隊列隊尾元素
QDataType QueueBack(Queue* q)
{
assert(q);
//獲取隊列頭部元素時，隊列不能為空
assert(!QueueEmpty(q));
return q->rear->data;
}
// 獲取隊列中有效元素個數(shù)
int QueueSize(Queue* q)
{
assert(q);
//結(jié)構(gòu)體中定義了一個size
//而這里遍歷鏈表得到個數(shù)，效率低
/*int size = 0; 不要用
QNode* cur = q->front;
while (cur != q->rear)
{
size++;
q->front = q->front->next;
}*/
return q->size;
}
// 銷毀隊列
void QueueDestroy(Queue* q)
{
assert(q);
QNode* cur = q->front;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
}
結(jié)尾
注意： 本文提到的效率全部為空間復(fù)雜度?。。。?br> 如果有什么建議和疑問，或是有什么錯誤，大家可以在評論區(qū)中提出。
希望大家以后也能和我一起進(jìn)步??！????
如果這篇文章對你有用的話，希望大家給一個三連??！????文章來源：http://www.zghlxwxcb.cn/news/detail-457761.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-457761.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】線性表之棧、隊列的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
