C語言數據結構之棧和隊列的實現及應用

更新時間：2022年08月18日 09:26:50 作者：蔣靈瑜的筆記本

棧和隊列是一種數據結構，只規(guī)定了性質，并沒有規(guī)定實現方式。本文將以順序結構實現棧，鏈表方式實現隊列，感興趣的小伙伴快跟隨小編一起學習一下吧

一、棧的概念

棧：是一種特殊的線性表，其只允許在棧頂進行插入和刪除元素操作。

棧中的數據元素遵守后進先出LIFO（Last In First Out）的原則。

壓棧：棧的插入操作叫做進棧\壓棧\入棧，入數據在棧頂。

出棧：棧的刪除操作叫做出棧。出數據也在棧頂。

二、Stack.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int STDataType;
typedef struct stack
{
    STDataType* arr;
    int top;//數組元素個數（top-1為最后一個元素的下標）就是順序表的size
    int capacity;//總容量
}ST;
void StackInit(ST* ps);//初始化
void StackDestroy(ST* ps);//銷毀
void StackPush(ST* ps, STDataType x);//壓棧
void StackPop(ST* ps);//出棧
bool StackEmpty(ST* ps);//判斷棧是不是為空
STDataType StackTop(ST* ps);//訪問棧頂元素
int StackSize(ST* ps);//數組元素個數

以順序結構實現棧，本質上仍是一個順序表，只是這個順序表加上了棧先進后出的規(guī)則。

數組的頭是棧底，數組尾是棧頂。棧主要的壓棧、出棧、訪問棧頂等接口非常契合順序表的尾插、尾刪、隨機訪問的特點。

三、Stack.c

1、棧的初始化和銷毀

void StackInit(ST* ps)//初始化
{
    assert(ps);
    ps->arr = NULL;
    ps->top = ps->capacity = 0;
}
void StackDestroy(ST* ps)//銷毀
{
    assert(ps);
    free(ps->arr);
    ps->arr = NULL;
    ps->top = ps->capacity = 0;
}

和順序表的初始化、銷毀方式一樣

2、棧的進棧、出棧

void StackPush(ST* ps, STDataType x)//進棧
{
    assert(ps);
    //判斷擴容
    if (ps->top == ps->capacity)
    {
        int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
        STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
        if (tmp == NULL)
        {
            perror("realloc fail:\n");
            exit(-1);
        }
        ps->arr = tmp;
        ps->capacity = newCapacity;
    }
    ps->arr[ps->top] = x;
    ps->top++;
}
void StackPop(ST* ps)//出棧
{
    assert(ps);
    assert(!StackEmpty(ps));
    ps->top--;
}

進棧需要判斷棧的空間，空間不夠則需要擴容

出棧時，先判空，再將top--即可

3、棧的判空、訪問棧頂元素、棧內元素個數

bool StackEmpty(ST* ps)//判斷棧是不是為空
{
    assert(ps);
    return ps->top == 0;
}
STDataType StackTop(ST* ps)//訪問棧頂元素
{
    assert(ps);
    assert(!StackEmpty(ps));
    return ps->arr[ps->top - 1];
}
int StackSize(ST* ps)//數組元素個數
{
    assert(ps);
    return ps->top;
}

注意訪問棧頂元素這個接口，要先判斷棧是不是空。

四、隊列的概念

隊列：一端進行插入數據操作，另一端進行刪除數據操作的特殊線性表，隊列具有先進先出FIFO(First In First Out)的特點。

入隊列：進行插入操作的一端稱為隊尾

出隊列：進行刪除操作的一端稱為隊頭

隊列參照現實生活中的排隊

五、Queue.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int QDataType;
typedef struct QueueNode
{
    struct QueueNode* next;
    QDataType data;
}QNode;
typedef struct Queue
{
    QNode* head;
    QNode* tail;
    int size;//加個size，方便統(tǒng)計長度
}Queue;
void QueueInit(Queue* pq);//初始化
void QueueDestroy(Queue* pq);//銷毀
void QueuePush(Queue* pq,QDataType x);//入隊（尾插）
bool QueueEmpty(Queue* pq);//判斷隊列是否為空
void QueuePop(Queue* pq);//出隊（頭刪）
int QueueSize(Queue* pq);//統(tǒng)計隊列長度
QDataType QueueFront(Queue* pq);//訪問隊頭數據
QDataType QueueBack(Queue* pq);//訪問隊尾數據

因為順序結構不適合頭刪，這里使用單鏈表來實現隊列。

結構體QNode用于模擬單鏈表，結構體Queue中存放了單鏈表的頭、尾指針、鏈表節(jié)點個數。使用Queue來操縱單鏈表。

單鏈表的頭head是隊頭（頭刪出數據），tail是隊尾（尾插錄數據）

六、Queue.c

1、隊列的初始化和銷毀

void QueueInit(Queue* pq)//初始化
{
    assert(pq);
    pq->head = pq->tail = NULL;
    pq->size = 0;
}
void QueueDestroy(Queue* pq)//銷毀
{
    assert(pq);
    QNode* cur = pq->head;
    //逐個銷毀釋放空間
    while (cur)
    {
        QNode* del = cur;
        cur = cur->next;
        free(del);
    }
    pq->head = pq->tail = NULL;
}

和單鏈表的銷毀方式一樣，注意銷毀時需要逐個節(jié)點銷毀。

2、隊列的入隊、出隊

void QueuePush(Queue* pq, QDataType x)//入隊,尾插
{
    assert(pq);
    //創(chuàng)建一個新節(jié)點
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
    if (newnode == NULL)
    {
        perror("malloc fail:\n");
        exit(-1);
    }
    newnode->data = x;
    newnode->next = NULL;
    //隊列為空時的尾插和不為空的尾插
    if (QueueEmpty(pq))
        pq->head=pq->tail = newnode;
    else
    {
        pq->tail->next = newnode;
        pq->tail = newnode;
    }
    pq->size++;
}
void QueuePop(Queue* pq)//出隊（頭刪）
{
    assert(pq);
    assert(!QueueEmpty(pq));
    QNode* next = pq->head->next;
    free(pq->head);
    pq->head = next;
    pq->size--;
}

入隊：尾插一個節(jié)點

出隊：頭刪一個節(jié)點

3、隊列的判空

bool QueueEmpty(Queue* pq)//判斷隊列是否為空
{
    assert(pq);
    return pq->head == NULL;
}

4、訪問隊頭、隊尾數據、統(tǒng)計隊列長度

int QueueSize(Queue* pq)//統(tǒng)計隊列長度
{
    assert(pq);
    return pq->size;
}
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;
}

訪問接口，注意先判空。

七、力扣中棧和隊列OJ題

1、有效的括號

使用隊列來解決，創(chuàng)建一個棧，碰到左括號將其進棧，碰到右括號則訪問棧頂元素，不相符則為false，迭代比較相符則為true

bool isValid(char * s){
    ST st;
    StackInit(&st);
    while(*s)
    {
        if(*s=='('||*s=='{'||*s=='[')
        {
            StackPush(&st,*s);//壓棧
        }
        else//比較時的情況
        {
            if(StackEmpty(&st))
                return false;  
            else if(StackTop(&st)=='('&&*s!=')')//訪問棧頂元素
            {
                return false;
            }
            else if(StackTop(&st)=='{'&&*s!='}')
            {
                return false;
            }
            else if(StackTop(&st)=='['&&*s!=']')
            {
                return false;
            }
            StackPop(&st);
        }
        ++s;
    }
    if(!StackEmpty(&st))
        return false;
    StackDestroy(&st);
    return true;
}

注：上述代碼還需要將棧的實現的代碼拷貝一份上去。

2、用隊列實現棧

入棧：選擇非空隊列進行入棧

出棧：隊列中只留一個元素，將其他元素Pop至另一個隊列，再對那個遺留的元素執(zhí)行出隊列操作即可模擬出棧動作

typedef struct {
    Queue q1;
    Queue q2;
} MyStack;
MyStack* myStackCreate() {
    MyStack* obj=(MyStack*)malloc(sizeof(MyStack));
    QueueInit(&obj->q1);
    QueueInit(&obj->q2);
    return obj;
}
 
void myStackPush(MyStack* obj, int x) {
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);//入隊,尾插
    }
    else
    {
        QueuePush(&obj->q2,x);//入隊,尾插
    }
}
 
int myStackPop(MyStack* obj) {
    Queue* empty=&obj->q1;
    Queue* unEmpty=&obj->q2;
    if(QueueEmpty(&obj->q2))
    {
        empty=&obj->q2;
        unEmpty=&obj->q1;
    }
    while(QueueSize(unEmpty)>1)//將非空元素導入到空隊列，留下最后一個
    {
        QueuePush(empty,QueueFront(unEmpty));//入隊,尾插
        QueuePop(unEmpty);//出隊（頭刪）
    }
    int top=QueueFront(unEmpty);
    QueuePop(unEmpty);//出隊（頭刪）
    return top;
}
 
int myStackTop(MyStack* obj) {
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);//訪問隊尾數據
    }
    else
    {
        return QueueBack(&obj->q2);//訪問隊尾數據
    }
}
 
bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}
 
void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);//銷毀
    QueueDestroy(&obj->q2);//銷毀
    free(obj);
}

注：上述代碼還需要將隊列的實現的代碼拷貝一份上去。

3、用棧實現隊列

現在有兩個棧，第一個棧用于入棧、出棧至第二個棧的操作，第二個棧僅用于出棧操作。

入棧：在第一個棧中壓入數據

出棧：如果第二個棧為空，則第一個棧中數據全部出棧至第二個棧，由第二個棧專門執(zhí)行出棧操作。等第二個棧再次為空，再次執(zhí)行上述動作

MyQueue* myQueueCreate() {
    MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&obj->st1);
    StackInit(&obj->st2);
    return obj;
}
 
void myQueuePush(MyQueue* obj, int x) {
    StackPush(&obj->st1, x);//壓棧
}
 
int myQueuePop(MyQueue* obj) {
    if(StackEmpty(&obj->st2))
    {
        while(!StackEmpty(&obj->st1))
        {
            StackPush(&obj->st2, StackTop(&obj->st1));//壓棧
            StackPop(&obj->st1);
        }
    }
    int val=StackTop(&obj->st2);
    StackPop(&obj->st2);
    return val;
}
 
int myQueuePeek(MyQueue* obj) {
    if(StackEmpty(&obj->st2))
    {
        while(!StackEmpty(&obj->st1))
        {
            StackPush(&obj->st2, StackTop(&obj->st1));//壓棧
            StackPop(&obj->st1);
        }
    }
    return StackTop(&obj->st2);
}
 
bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->st1)&&StackEmpty(&obj->st2);
}
 
void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->st1);
    StackDestroy(&obj->st2);
    free(obj);
}

注：上述代碼還需要將棧的實現的代碼拷貝一份上去。

4、設計循環(huán)隊列

typedef struct {
    int* arr;
    int front;//記錄首
    int tail;//記錄尾的下一個
    int capacity;//用于處理邊界問題的一個變量
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->arr=(int*)malloc(sizeof(int)*(k+1));
    obj->front=obj->tail=0;
    obj->capacity=k+1;//這里一定要寫成k+1，寫成k的話,后續(xù)處理邊界問題要額外考慮分支情況
    return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front==obj->tail;
}
 
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->tail+1)%(obj->capacity)==obj->front;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
        return false;
    obj->arr[obj->tail]=value;
    obj->tail++;
    obj->tail%=obj->capacity;
    return true;
}
 
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return false;
    obj->front++;
    obj->front%=obj->capacity;
    return true;
}
 
int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;
    return obj->arr[obj->front];
}
 
int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;
    return obj->arr[(obj->tail-1+obj->capacity)%obj->capacity];
}
void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->arr);
    obj->arr=NULL;
    free(obj);
}

因為循環(huán)隊列無法區(qū)分隊列為空和為滿的情況，因為為空和未滿，首位下標是一樣的。

所以這道題有兩種解法，計數確定?？諚M，或者多開辟一個空間。本題采用后者。

可選的數據結構也有兩種，順序和鏈表。本題采用順序。

上表為隊列滿的情況，無法再執(zhí)行插入。運用順序表，本題的難點在于如何處理tail和front在數組尾部的情況。

強烈建議在初始化的接口中將capacity定義為k+1，因為入隊出隊接口中%capacity后，可以同時滿足正常和極端位置下的情況。（詳見代碼，一讀就懂，后續(xù)讀者可以逝一下將capacity定義為k，感受下區(qū)別）

capacity定義為k時的代碼如下：

typedef struct {
    int* arr;
    int front;//記錄首
    int tail;//記錄尾的下一個
    int capacity;//總容量
} MyCircularQueue;
 
 
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->arr=(int*)malloc(sizeof(int)*(k+1));
    obj->front=obj->tail=0;
    obj->capacity=k;
    return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front==obj->tail;
}
 
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->tail+1)%(obj->capacity+1)==obj->front;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
        return false;
    obj->arr[obj->tail]=value;
    obj->tail++;
    if(obj->tail>obj->capacity)
        obj->tail=obj->tail%obj->capacity-1;
    return true;
}
 
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return false;
    obj->front++;
    if(obj->front>obj->capacity)
        obj->front=obj->front%obj->capacity-1;
    return true;
}
 
int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;
    return obj->arr[obj->front];
}
 
int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;
    if(obj->tail!=0)
        return obj->arr[(obj->tail-1+obj->capacity)%obj->capacity];
    return obj->arr[obj->capacity];
}
void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->arr);
    obj->arr=NULL;
    free(obj);
}

主要區(qū)別就是入隊出隊代碼，常規(guī)情況和邊界情況不能統(tǒng)一。

以上就是C語言數據結構之棧和隊列的實現及應用的詳細內容，更多關于C語言棧隊列的資料請關注腳本之家其它相關文章！

您可能感興趣的文章:

淺析C/C++中的可變參數與默認參數
C支持可變參數的函數，這里的意思是C支持函數帶有可變數量的參數，最常見的例子就是我們十分熟悉的printf()系列函數。我們還知道在函數調用時參數是自右向左壓棧的
2013-09-09
Java?C++?算法題解拓展leetcode670最大交換示例
這篇文章主要介紹了Java?C++算法題解拓展leetcode670最大交換示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪
2022-09-09
C++結構體與類的區(qū)別詳情
這篇文章主要介紹了C++結構體與類的區(qū)別，C++中的struct對C中的struct進行了擴充，它已經不再只是一個包含不同數據類型的數據結構了，它已經獲取了太多的功能。下面我們一起進入文章倆姐具體內容,需要的朋友也可以參考一下
2021-11-11
C/C++函數指針深入探究
函數指針是一個指針變量,它可以存儲函數的地址,然后使用函數指針,下面這篇文章主要給大家介紹了關于C語言進階教程之函數指針的相關資料,需要的朋友可以參考下
2022-08-08
C++實現模擬shell命令行(代碼解析)
這篇文章主要介紹了C++實現模擬shell命令行,本文通過實例代碼進行命令行解析，代碼簡單易懂，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下
2021-12-12
C++中getline()和get()的方法淺析
大家都知道作為C++獲取輸入流的方法，幾乎在任何一本資料書上getline()方法和get()方法都作為入門級的方法進行講述，即便如此，筆者在學習C++的過程中仍經常忘記這二者的使用要點，可能也有C++的初學者對這兩個方法還心存疑慮，本篇文章就這兩個方法的使用進行簡要闡述。
2016-10-10
Qt 鼠標/觸屏繪制平滑曲線(支持矢量/非矢量方式)
這篇文章主要介紹了Qt 鼠標/觸屏繪制平滑曲線(支持矢量/非矢量方式),文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧
2020-04-04
C語言數據結構之單向鏈表詳解分析
鏈表可以說是一種最為基礎的數據結構了，而單向鏈表更是基礎中的基礎。鏈表是由一組元素以特定的順序組合或鏈接在一起的，不同元素之間在邏輯上相鄰，但是在物理上并不一定相鄰。在維護一組數據集合時，就可以使用鏈表，這一點和數組很相似
2021-11-11
Qt實現數據導出到xls的示例代碼
導入導出數據到csv由于語法簡單，適用場景有限，于是本文將為大家介紹Qt如何實現導出數據到xls，感興趣的小伙伴可以跟隨小編一起試一試
2022-01-01
C++核心編程之內存分區(qū)詳解
這篇文章主要為大家詳細介紹了C++核心編程之內存分區(qū)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助
2022-03-03

亚洲乱码中文字幕综合,中国熟女仑乱hd,亚洲精品乱拍国产一区二区三区,一本大道卡一卡二卡三乱码全集资源,又粗又黄又硬又爽的免费视频

軟件下載

源碼下載

軟件編程

網絡編程

在線工具

數據庫

CMS

常用工具

C語言數據結構之棧和隊列的實現及應用

目錄

一、棧的概念

二、Stack.h

三、Stack.c

1、棧的初始化和銷毀

2、棧的進棧、出棧

3、棧的判空、訪問棧頂元素、棧內元素個數

四、隊列的概念

五、Queue.h

六、Queue.c

1、隊列的初始化和銷毀

2、隊列的入隊、出隊

3、隊列的判空

4、訪問隊頭、隊尾數據、統(tǒng)計隊列長度

七、力扣中棧和隊列OJ題

1、有效的括號

2、用隊列實現棧

3、用棧實現隊列

4、設計循環(huán)隊列

相關文章

最新評論

大家感興趣的內容

最近更新的內容

常用在線小工具

C語言數據結構之棧和隊列的實現及應用

目錄

一、棧的概念

二、Stack.h

三、Stack.c

1、棧的初始化和銷毀

2、棧的進棧、出棧

3、棧的判空、訪問棧頂元素、棧內元素個數

四、隊列的概念

五、Queue.h

六、Queue.c

1、隊列的初始化和銷毀

2、隊列的入隊、出隊

3、隊列的判空

4、訪問隊頭、隊尾數據、統(tǒng)計隊列長度

七、力扣中棧和隊列OJ題

1、有效的括號

2、用隊列實現棧

3、用棧實現隊列

4、設計循環(huán)隊列

相關文章

最新評論

大家感興趣的內容

最近更新的內容

常用在線小工具

一、棧的概念

二、Stack.h

三、Stack.c

1、棧的初始化和銷毀

2、棧的進棧、出棧

3、棧的判空、訪問棧頂元素、棧內元素個數

五、Queue.h

六、Queue.c

1、隊列的初始化和銷毀

2、隊列的入隊、出隊

3、隊列的判空

4、訪問隊頭、隊尾數據、統(tǒng)計隊列長度

七、力扣中棧和隊列OJ題

1、有效的括號

2、用隊列實現棧

3、用棧實現隊列