數據結構——lesson5棧和隊列詳解

hellohello~這里是土土數據結構學習筆記🥳🥳

💥個人主頁：大耳朵土土垚的博客
💥 所屬專欄：數據結構學習筆記
💥對于順序表鏈表有疑問的都可以在上面數據結構的專欄進行學習哦~感謝大家的觀看與支持🌹🌹🌹
有問題可以寫在評論區或者私信我哦~

前言：

之前的博客我們學習了數據結構中的順序表和鏈表，現在我們一起回顧一下它們各自的優缺點。
首先是順序表：
?優點：
1.支持下標的隨機訪問（因為是數組的形式）；
2.尾插尾刪比較方便，效率不錯；
3.CPU高速緩存命中率較高；
? 缺點：
1.前面部分插入刪除數據需要挪動數據，時間復雜度為O(n)；
2.空間不夠需要擴容——一方面擴容需要付出代價例如異地擴容，另一方面擴容一般還伴隨著空間的浪費；
其次是鏈表：
?優點：
1.任意位置插入刪除數據都比較方便高效，時間復雜度為O(1);
2.按需申請釋放空間
?缺點：
1.不支持下標的隨機訪問；
2.CPU高速緩存命中率較低；
我們發現順序表的優點和缺點恰好對應著鏈表的缺點和優點，順序表和鏈表各自都有它們獨特的作用與優勢，不存在優劣之分。大家在使用的時候要根據自己的需求去選擇哦~

一、棧

1.1棧的概念及結構

棧：一種特殊的線性表，其只允許在固定的一端進行插入和刪除元素操作。進行數據插入和刪除操作的一端稱為棧頂，另一端稱為棧底。棧中的數據元素遵守后進先出LIFO（Last In First Out）的原則。

壓棧：棧的插入操作叫做進棧/壓棧/入棧，入數據在棧頂。
出棧：棧的刪除操作叫做出棧。出數據也在棧頂。

1.2棧的實現

棧的實現一般可以使用數組或者鏈表實現，相對而言數組的結構實現更優一些。因為數組在尾上插入數據的代價比較小。

在這里插入圖片描述

如圖所示，左邊是棧尾，右邊是棧頂（進行出棧也就是刪除操作）；
以下是棧的實現：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>typedef int STDataType;// 支持動態增長的棧
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);
// 獲取棧中有效元素個數 
int StackSize(Stack* ps);
// 檢測棧是否為空，如果為空返回true，如果不為空返回false
bool StackEmpty(Stack* ps);
// 銷毀棧 
void StackDestroy(Stack* ps);

棧實現包括初始化，入棧，出棧，獲取棧頂元素，獲取棧中有效元素個數，判斷棧是否為空以及銷毀棧這7個函數。

下面我們來具體實現棧：

（1）初始化棧

void StackInit(Stack* ps);

// 初始化棧 
void StackInit(Stack* ps)
{assert(ps);ps->a = NULL;ps->capacity = 0;ps->top = 0;//指向棧頂的下一個數據//ps->top = -1; //則指向棧頂數據
}

這里要注意ps->top = 0 代表的是棧頂元素的下一個；ps->top = -1才指向棧頂元素，因為后面的函數每增加一個元素，ps->top++，如果初始化top = 0，加一個元素后，top=1；表示的位置是下標為1（其本質是數組，下標為1的位置表示第二個元素），但確間接表明了棧中元素的個數剛好為1，所以為了后續方便，我們選擇初始化top=0；當然你也可以自由選擇。

（2）入棧

void StackPush(Stack* ps, STDataType data);

void StackPush(Stack* ps, STDataType data)
{assert(ps);if (ps->top == ps->capacity)//判斷空間是否滿了{//空間capacity滿了就需要擴容STDataType newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//判斷是否擴容過，如果capacity為0就增加4//個單位空間，否則開辟capacity的2倍空間ps->capacity = newcapacity;//擴容后capacity要等于newcapacityps->a = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));if (ps->a == NULL){perror("realloc fail");return;}}ps->a[ps->top] = data;//入棧ps->top++;//棧頂+1}

這里入棧要注意判斷棧的容量是否滿了，滿了需要使用realloc函數擴容，對于realloc函數有疑問的小伙伴可以查看土土的博客——C語言動態內存函數介紹

（3）出棧

void StackPop(Stack* ps)

// 出棧 
void StackPop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));//判斷非空ps->top--;
}

出棧就比較簡單，只需將top–即可，但是同時也要注意判斷棧不為空哦~判空函數StackEmpty(ps）將在后面實現

（4）獲取棧頂元素

STDataType StackTop(Stack* ps）

// 獲取棧頂元素 
STDataType StackTop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));//判斷非空return ps->a[ps->top-1];
}

是時候考驗你們的專注力了，這里返回棧頂元素用的是top-1；有小伙伴知道為什么不直接用top嗎？答案我們放在下一個獲取棧中有效元素個數函數中揭曉。

（5）獲取棧中有效元素個數

int StackSize(Stack* ps)

// 獲取棧中有效元素個數 
int StackSize(Stack* ps)
{assert(ps);return ps->top;
}

上一個函數獲取棧頂元素我們使用的是top-1，是因為在初始化函數時我們就介紹過將top初始化為0，指向棧頂元素的下一個，所以要獲取棧頂元素我們要將top-1；依此類推棧中有效元素個數就恰好是top了。

（6）檢測棧是否為空

bool StackEmpty(Stack* ps)

// 檢測棧是否為空，如果為空返回true，如果不為空返回false
bool StackEmpty(Stack* ps)
{assert(ps);/*if (ps->top == 0)return true;elsereturn false;*/return ps->top == 0;
}

這里可以使用if語句來判斷，也可以如上面代碼所示直接使用return返回。

（7）銷毀棧

void StackDestroy(Stack* ps)

// 銷毀棧 
void StackDestroy(Stack* ps)
{assert(ps);free(ps->a);ps->capacity = 0;ps->a = NULL;ps->top = 0;
}

這里就不過多贅述，使用free銷毀即可；因為數組時地址連續的一段物理空間，所以只要數組首元素地址即可free整個數組與鏈表需要遍歷不同。

棧實現可視化如下圖所示：

在這里插入圖片描述
代碼如下：

#define _CRT_SECURE_NO_WARNINGS 1
#include"stack.h"
void Sttest()
{Stack ST;StackInit(&ST);StackPush(&ST, 1);StackPush(&ST, 2);StackPush(&ST, 3);StackPush(&ST, 4);while (ST.top)//打印棧{printf("%d", StackTop(&ST));StackPop(&ST);//打印一個出一個}StackDestroy(&ST);}
int main()
{Sttest();return 0;
}

二、隊列

2.1隊列的概念及結構

隊列：只允許在一端進行插入數據操作，在另一端進行刪除數據操作的特殊線性表，隊列具有先進先出FIFO(First In First Out)
入隊列：進行插入操作的一端稱為隊尾
出隊列：進行刪除操作的一端稱為隊頭

發現進行刪除操作的都是隊頭，無論棧還是隊列；
隊列根據其名字，我們不難發現類似于我們生活中的排隊，先排隊的肯定會先出去；

2.2隊列的實現

隊列也可以數組和鏈表的結構實現，使用鏈表的結構實現更優一些，因為如果使用數組的結構，出隊列在數組頭上出數據，效率會比較低。

// 鏈式結構：表示隊列 
typedef int QDataType;
typedef struct QListNode 
{ struct QListNode* pNext; QDataType data; 
}QNode; // 隊列的結構 
typedef struct Queue 
{ 
QNode* front; 
QNode* rear; 
}Queue; 
// 初始化隊列 
void QueueInit(Queue* q); 
// 隊尾入隊列 
void QueuePush(Queue* q, QDataType data); 
// 隊頭出隊列 
void QueuePop(Queue* q); 
// 獲取隊列頭部元素 
QDataType QueueFront(Queue* q); 
// 獲取隊列隊尾元素 
QDataType QueueBack(Queue* q); 
// 獲取隊列中有效元素個數 
int QueueSize(Queue* q); 
// 檢測隊列是否為空，如果為空返回非零結果，如果非空返回0 
int QueueEmpty(Queue* q); 
// 銷毀隊列 
void QueueDestroy(Queue* q);

隊列相較于棧定義了兩個結構體來表示，一個結構體QNode表示節點，另一個結構體Queue則用來表示隊列的頭尾指針，展示隊列的結構。
隊列也包含了初始化，隊尾入隊列，隊頭出隊列，獲取隊列頭部元素，獲取隊列尾部元素，以及有效元素個數，判空，銷毀這八個函數。

(1）初始化隊列

void QueueInit(Queue* q);

// 初始化隊列 
void QueueInit(Queue* q)
{assert(q);q->front = NULL;q->rear = NULL;
}

將Queue結構體初始化即可

(2)隊尾入隊列

void QueuePush(Queue* q, QDataType data);

// 隊尾入隊列 
void QueuePush(Queue* q, QDataType data)
{assert(q);QNode* newnode = (QNode*)malloc(sizeof(QNode));//創建新節點if (newnode == NULL){perror("malloc fail");return;}newnode->data = data;newnode->pNext = NULL;//隊列為空的情況入隊列if (QueueEmpty(q)){q->front = newnode;q->rear = newnode;return;}//隊列不為空的情況入隊列else{q->rear->pNext = newnode;q->rear = newnode;return;}
}

隊尾入隊列首先要記得malloc一個新節點，然后要記得判斷隊列是否為空，分為兩種情況。判空函數將在后面實現。

(3)隊頭出隊列

void QueuePop(Queue* q);

// 隊頭出隊列 
void QueuePop(Queue* q)
{assert(q);assert(!QueueEmpty(q));//判斷隊列非空QNode* tmp = q->front;//先保存隊頭指針q->front = tmp->pNext;free(tmp);
}

隊頭出隊列要記得free釋放出去節點的空間。

(4)獲取隊列頭部元素

QDataType QueueFront(Queue* q);

// 獲取隊列頭部元素 
QDataType QueueFront(Queue* q)
{assert(q);assert(!QueueEmpty(q));//判斷隊列非空return q->front->data;}

通過結構體Queue的front指針可以直接找到頭返回即可。

(5)獲取隊列隊尾元素

QDataType QueueBack(Queue* q);

// 獲取隊列隊尾元素 
QDataType QueueBack(Queue* q)
{assert(q);assert(!QueueEmpty(q));//判斷隊列非空return q->rear->data;
}

同樣通過結構體Queue的rear指針可以直接找到尾返回即可。

(6) 獲取隊列中有效元素個數

int QueueSize(Queue* q)

// 獲取隊列中有效元素個數 
int QueueSize(Queue* q)
{assert(q);assert(!QueueEmpty(q));//判斷隊列非空int count = 0;//記錄元素個數QNode* cur = q->front;while (cur){cur = cur->pNext;count++;}return count;
}

這里隊列用的是鏈表的結構，所以需要使用循環遍歷來獲取有效元素的個數。

(7)檢測隊列是否為空

bool QueueEmpty(Queue* q);

// 檢測隊列是否為空，如果為空返回true,非空返回false
bool QueueEmpty(Queue* q)
{assert(q);return q->front == NULL;}

隊列頭指針為空即沒有元素進入隊列。

(8)銷毀隊列

void QueueDestroy(Queue* q);

// 銷毀隊列 
void QueueDestroy(Queue* q)
{assert(q);while (q->front){QueuePop(q);}
}

QueuePop()函數將元素從隊頭刪除的同時也使用了free釋放空間，所以這里直接使用該函數即可。

隊列實現可視化如下圖所示：

在這里插入圖片描述
實現代碼如下：

#include"queue.h"void Qtest()
{Queue QT;QueueInit(&QT);QueuePush(&QT, 1);QueuePush(&QT, 2);QueuePush(&QT, 3);QueuePush(&QT, 4);while (QT.front){printf("%d", QueueFront(&QT));QueuePop(&QT);}QueueDestroy(&QT);
}
int main()
{Qtest();return 0;
}

三、練習題

1.一個棧的初始狀態為空。現將元素1、2、3、4、5、A、B、C、D、E依次入棧，然后再依次出棧，則元素出
棧的順序是（  ）。
A 12345ABCDEB EDCBA54321C ABCDE12345D 54321EDCBA2.若進棧序列為 1,2,3,4 ，進棧過程中可以出棧，則下列不可能的一個出棧序列是（）
A 1,4,3,2B 2,3,4,1C 3,1,4,2D 3,4,2,13.以下(  )不是隊列的基本運算？
A 從隊尾插入一個新元素
B 從隊列中刪除第i個元素
C 判斷一個隊列是否為空
D 讀取隊頭元素的值