引言
在順序表和鏈表那篇博客中提到過,棧和隊列也屬于線性表
線性表:
線性表(linear list)是n個具有相同特性的數據元素的有限序列。 線性表是一種在實際中廣泛使用的數據結構。線性表在邏輯上是線性結構,也就是說是連續的一條直線。但在物理上并不一定是連續的。線性表在物理上存儲時,通常以數組和鏈式結構的形式存儲。
但棧和隊列相比于之前學的順序表和鏈表,就簡單的多了。
現在我們就來看看數據結構中的棧和隊列到底是什么,以及用C語言的模擬實現吧!
棧
概念及結構
棧的概念
棧:一種特殊的線性表,其只允許在固定的一端進行插入和刪除元素操作。進行數據插入和刪除操作的一端稱為棧頂,另一端稱為棧底。棧中的數據元素遵守后進先出LIFO(Last In First Out)的原則。
壓棧(push):棧的插入操作叫做進棧/壓棧/入棧,入數據在棧頂。
出棧(pop):棧的刪除操作叫做出棧。出數據也在棧頂。
在上圖中,左邊兩圖是壓棧(push)的過程;右邊兩圖是出棧(pop)的過程
以上就是棧的概念及邏輯,下面我們就可以來看看棧的實現了
棧的具體結構
棧的實現一般可以使用數組或者鏈表實現,相對而言數組的結構實現更優一些。因為數組在尾上插入數據的代價比較小,其緩存命中率也高。
下面是數組實現棧的結構
capacity是容量,指向所開空間最后一位的下一位;top是有效元素個數,指向有效數字的下一位
下面是鏈表實現棧的結構
由于數組實現棧相比于鏈表實現更有優勢,這里我們用數組手搓一個棧
手搓一個棧(棧的實現)
這里的棧的空間也需要動態開辟(需要時動態擴容),故數組的內存是開辟在堆中的。
先放上需要實現的接口,頭文件Stack.h
//Stack.h
// 下面是定長的靜態棧的結構,實際中一般不實用
// 所以我們主要實現后面的支持動態增長的棧
// typedef int STDataType;
// #define N 10
// typedef struct Stack
// {
// STDataType _a[N];
// int _top; // 棧頂
// }Stack;#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>typedef int STDataType;
typedef struct stack
{STDataType* a;int top; //棧頂int capacity; //容量
}ST;//初始化棧
void STInit(ST* ps);
//銷毀棧
void STDestory(ST* ps);
//入棧(壓棧)
void STPush(ST* ps, STDataType x);
//出棧
void STPop(ST* ps);
//獲取棧頂元素
STDataType STTop(ST* ps);
//獲取棧中有效元素個數
int STSize(ST* ps);
//檢測棧是否為空,如果為空返回非零結果,如果不為空返回0
bool STEmpty(ST* ps);
此時我們可以開始實現頭文件接口中的內容了
初始化和銷毀棧
感覺沒什么好說的,注意下銷毀的free就行
//初始化棧
void STInit(ST* ps)
{assert(ps);ps->a = NULL;ps->top = ps->capacity = 0;
}
//銷毀棧
void STDestory(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}
入棧(壓棧)和出棧
注意在空間不夠的時候要動態開辟空間realloc,這里入空間開辟后返回的指針先用tmp接收是為了防止開辟失敗時找不到原來的內存空間,當開辟成功后再將新開辟的地址賦給ps->a,realloc同時也會自動釋放過去的空間。
//入棧
void STPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity) {int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//這里是三目操作符//下面別忘乘sizeof(STDataType)STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity*sizeof(STDataType));if (tmp == NULL) {perror("realloc tmp fail:");exit(1);}ps->a = tmp;ps->capacity = newcapacity;}ps->a[ps->top] = x;++ps->top;//入棧后最大元素數加一
}
//出棧
void STPop(ST* ps)
{assert(ps);//出棧時要保證棧中有元素assert(!STEmpty(ps));ps->top--;
}
獲取棧頂元素
棧頂元素其實就是top前一位,這里注意棧為空時不能獲取到元素
//獲取棧頂元素
STDataType STTop(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps->a[ps->top - 1];
}
獲取棧中有效元素個數和檢測棧是否為空
這里也是根據棧的top去判斷就行
//獲取棧中有效元素個數
int STSize(ST* ps)
{assert(ps);return ps->top;
}
//檢測棧是否為空,如果為空返回非零結果,如果不為空返回0
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}
體驗一下棧
//測試棧的代碼
#include"Stack.h"
int main()
{struct stack st;STInit(&st);STPush(&st, 1);STPush(&st, 2);STPush(&st, 3);STPush(&st, 4);while (!STEmpty(&st)) {printf("%d ", STTop(&st));STPop(&st);}printf("\n");STDestory(&st);return 0;
}
怎么說呢,棧就這么點內容,再多的沒有,簡單的結構應該大家都能理解,如果有疑問的朋友也歡迎再評論區提出,我也會盡我所能去提供幫助。
隊列
隊列的概念及結構
隊列的概念
隊列:只允許在一端進行插入數據操作,在另一端進行刪除數據操作的特殊線性表,隊列具有先進先出。FIFO(First In First Out)
入隊列(push):進行插入操作的一端稱為隊尾
出隊列(pop):進行刪除操作的一端稱為隊頭
隊列的具體結構
隊列也可以數組和鏈表的結構實現,使用鏈表的結構實現更優一些,因為如果使用數組的結構,出隊列在數組頭上出數據,效率會比較低。
所以這里我們講隊列鏈表結構的具體實現
下面是對隊列維護的具體結構
下面是關于隊列從隊頭出元素,隊尾進元素的過程。
手搓一個隊列(隊列的實現)
先放上要實現的接口,我放在頭文件Queue.h中
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
// 鏈式結構:表示隊列
typedef int QDataType;
//隊列的一個結點
typedef struct QListNode
{struct QListNode* _next;QDataType _data;
}QNode;
// 隊列的結構
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);
// 獲取隊列中有效元素個數
int QueueSize(Queue* q);
// 檢測隊列是否為空,如果為空返回非零結果,如果非空返回0
int QueueEmpty(Queue* q);
// 銷毀隊列
void QueueDestroy(Queue* q);
?初始化隊列
這個沒什么可說的,將維護隊列的指針初始化制空,size置零
// 初始化隊列
void QueueInit(Queue* q)
{assert(q);q->_front = NULL;q->_rear = NULL;q->size = 0;
}
隊尾入隊列
之前在實現鏈表的時候專門寫了一個CreateNode函數,是因為當時在鏈表頭尾中間各處插入時都需要用到。但是隊列這里不同,只有入隊列這一處用到了CreateNode,我們就大可不必再寫這個函數,直接寫在這個Push函數里就行。
在新結點開辟出來后,需要分兩種情況討論
- 隊列中無結點(_front 和 _rear 都為空):這種情況需要同時對_front和_rear做出調整
- 隊列中有結點:這時直接將新節點鏈接到 _rear 尾結點之后,同時新節點成為尾結點
// 隊尾入隊列
void QueuePush(Queue* q, QDataType data)
{assert(q);//需要新結點,直接創建QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL) {perror("malloc fail:");exit(1);}newnode->_data = data;newnode->_next = NULL;if (q->_front == NULL) {q->_front = newnode;q->_rear = newnode;}else {q->_rear->_next = newnode;q->_rear = newnode;}q->size++;
}
隊頭出隊列
這里注意_front和_rear兩個指針
這里需要分三種情況討論:
- 隊列為空:無法執行pop,assert斷言
- 隊列只有一個結點:釋放節點同時將隊列置空
- 隊列中有多個結點:將隊頭指針釋放,_front指向下一個結點(這里稍微注意下釋放順序,不要出現釋放之后還去訪問結點next的情況)
// 隊頭出隊列
void QueuePop(Queue* q)
{assert(q);assert(q->_front);if (q->size == 1) {//如果只有一個結點,直接釋放free(q->_front);q->_front = q->_rear = NULL;}else {QNode* pnext = q->_front->_next;free(q->_front);q->_front = pnext;}q->size--;
}
獲取隊列頭部元素和獲取隊列尾部元素
這里直接應用_front和_rear指針就可以
// 獲取隊列頭部元素
QDataType QueueFront(Queue* q)
{assert(q);assert(q->_front);return q->_front->_data;
}
// 獲取隊列隊尾元素
QDataType QueueBack(Queue* q)
{assert(q);assert(q->_rear);return q->_rear->_data;
}
獲取隊列有效元素個數和檢測隊列是否為空
獲取隊列有效元素可以直接運用上我們的size,size的大小即為有效元素個數,size為0時隊列為空
// 獲取隊列中有效元素個數
int QueueSize(Queue* q)
{assert(q);return q->size;
}
// 檢測隊列是否為空,如果為空返回非零結果,如果非空返回0
int QueueEmpty(Queue* q)
{assert(q);return q->size == 0;
}
銷毀隊列
這里稍微復雜一些,需要分三種情況討論:
- 隊列中無元素:直接返回,不用釋放了
- 隊列中有一個元素:釋放一次并置空指針,size置零
- 隊列中有多個元素:對照鏈表的銷毀方式銷毀,最后置空指針,size置零
// 銷毀隊列
void QueueDestroy(Queue* q)
{assert(q);if (q->_front == NULL)return;if (q->size == 1) {free(q->_front);}else {while (q->_front) {QNode* pnext = q->_front->_next;free(q->_front);q->_front = pnext;}}q->_front = q->_rear = NULL;q->size = 0;
}
體驗一下手搓的隊列
#include"Queue.h"
int main()
{Queue q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 3);QueuePush(&q, 5);QueuePush(&q, 7);QueuePush(&q, 9);while (!QueueEmpty(&q)) {printf("%d ", QueueFront(&q));QueuePop(&q);}printf("\n");QueueDestroy(&q);return 0;
}
隊列拓展之設計循環隊列
實際中我們有時還會使用一種隊列,叫循環隊列。如操作系統課程講解生產者消費者模型時可以就會使用循環隊列。
循環隊列的存儲數據量有一個上限,即容量一定,其邏輯結構圖大概是這樣的:
循環隊列可以使用數組實現,也可以使用循環鏈表實現:
我們將最后一個有效元素的下一位設計為尾,當front和tail相等的時候,就是隊列為空的時候。
就鏈表實現的循環隊列來說,相對比較復雜:如果你把有效數字的下一位當作尾,你將無法直接訪問到鏈表尾元素;如果你把尾元素當作有效數字末尾,還得去區分隊列只有一個元素和沒有元素的情況,以及tail和front重合時是隊列是滿的還是空的。同時鏈表實現的隊列還無法直接算出有效數字個數,雖然這時你也許可以存一個size專門來記錄有效數字個數。
或許在你給鏈表設計一大堆解決方案之前,可以來看看用順序結構來設計環形鏈表,你會發現,之前的一系列問題在順序結構面前已經不復存在。
你可以通過下標直接訪問到有效數字的上一位和下一位,你可以通過tail和front的相對位置直接計算出有效數字個數,你更可以單憑front和tail的相對位置來判斷環形隊列此時是滿的還是空的。
如果大家已經有思路想法,可以先來看看這道題:622. 設計循環隊列 - 力扣(LeetCode)
那么,我們接下來看看用順序表設計循環隊列的方案吧
對于循環隊列的結構設計
上圖中注意專門預留空間解決假溢出問題,當(rear + 1)%(k + 1) == front 時,隊列為滿;當rear == front 時,隊列為空。這里(rear + 1)%(k + 1)是對下標的一種處理方式,使其邏輯結構為一個環,下標數字范圍在(0 ~ k)。
下面我們來實現循環隊列的一些功能函數
循環隊列初始化
注意在malloc的時候多開了1的空間預留,開始將front和rear都置零,obj中的k置為n,這里的n指的是要開環形隊列能容納有效元素的大小
//MyCircularQueue(k): 構造器,設置隊列長度為 k
MyCircularQueue* myCircularQueueCreate(int n) {MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj->a = (int*)malloc(sizeof(int) * (n + 1));if (obj->a == NULL) {perror("malloc fail:");exit(1);}obj->front = 0;obj->rear = 0;obj->k = n;return obj;
}
檢查循環隊列是否為空和是否為滿
當(rear + 1)%(k + 1) == front 時,隊列為滿;當rear == front 時,隊列為空
//isEmpty(): 檢查循環隊列是否為空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->front == obj->rear;
}//isFull(): 檢查循環隊列是否已滿
bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->rear + 1) % (obj->k + 1) == obj->front;
}
循環隊列尾插入數據
如果隊列已滿則返回false,插入失敗
//enQueue(value): 向循環隊列插入一個元素。如果成功插入則返回真
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if (myCircularQueueIsFull(obj))return false;obj->a[obj->rear] = value;obj->rear = (obj->rear + 1) % (obj->k + 1);return true;
}
循環隊列頭刪除數據
如果隊列為空則返回false,刪除失敗
//deQueue(): 從循環隊列中刪除一個元素。如果成功刪除則返回真
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj))return false;obj->front = (obj->front + 1) % (obj->k + 1);return true;
}
循環隊列頭部和尾部獲取元素
這里獲取尾部元素需要經行一定的處理,rear的前一位 = (rear -?1 +?k + 1)%(k + 1)
取模這部分大家可以拿出草稿紙畫一畫,其實也不難理解
//Front: 從隊首獲取元素。如果隊列為空,返回 -1
int myCircularQueueFront(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj))return -1;return obj->a[obj->front];
}//Rear: 獲取隊尾元素。如果隊列為空,返回 -1
int myCircularQueueRear(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj))return -1;return obj->a[(obj->rear + obj->k) % (obj->k + 1)];
}
釋放循環隊列
這里釋放就行
//Free:釋放空間
void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);
}
以上就是循環隊列的內容,如果大家對鏈表實現循環隊列有興趣,可以自己在電腦上敲敲試試,雖然邏輯相比順序表實現復雜一些,不過同樣是可行的。也可以返回去做做那道力扣循環隊列實現的題目,鞏固一下所學。
結語
到這里棧和隊列的內容基本上就結束了,本篇文章講解了棧和隊列的概念和結構,并用C語言進行了模擬實現,最后拓展了循環隊列的概念結構以及循環隊列的實現。如果本篇博客對你有幫助的話,還請多多支持博主,后續博主還會產出更多有意思的內容?
有疑問或者博文有錯誤可以評論區提出或者私信我哦~