C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之棧和隊(duì)列的實(shí)現(xiàn)及應(yīng)用

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

棧和隊(duì)列是一種數(shù)據(jù)結(jié)構(gòu)，只規(guī)定了性質(zhì)，并沒有規(guī)定實(shí)現(xiàn)方式。本文將以順序結(jié)構(gòu)實(shí)現(xiàn)棧，鏈表方式實(shí)現(xiàn)隊(duì)列，感興趣的小伙伴快跟隨小編一起學(xué)習(xí)一下吧

一、棧的概念

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

棧中的數(shù)據(jù)元素遵守后進(jìn)先出LIFO（Last In First Out）的原則。

壓棧：棧的插入操作叫做進(jìn)棧\壓棧\入棧，入數(shù)據(jù)在棧頂。

出棧：棧的刪除操作叫做出棧。出數(shù)據(jù)也在棧頂。

二、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;//數(shù)組元素個(gè)數(shù)（top-1為最后一個(gè)元素的下標(biāo)）就是順序表的size
    int capacity;//總?cè)萘?
}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);//訪問(wèn)棧頂元素
int StackSize(ST* ps);//數(shù)組元素個(gè)數(shù)

以順序結(jié)構(gòu)實(shí)現(xiàn)棧，本質(zhì)上仍是一個(gè)順序表，只是這個(gè)順序表加上了棧先進(jìn)后出的規(guī)則。

數(shù)組的頭是棧底，數(shù)組尾是棧頂。棧主要的壓棧、出棧、訪問(wèn)棧頂?shù)冉涌诜浅Ｆ鹾享樞虮淼奈膊?、尾刪、隨機(jī)訪問(wèn)的特點(diǎn)。

三、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、棧的進(jìn)棧、出棧

void StackPush(ST* ps, STDataType x)//進(jìn)棧
{
    assert(ps);
    //判斷擴(kuò)容
    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--;
}

進(jìn)棧需要判斷棧的空間，空間不夠則需要擴(kuò)容

出棧時(shí)，先判空，再將top--即可

3、棧的判空、訪問(wèn)棧頂元素、棧內(nèi)元素個(gè)數(shù)

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

注意訪問(wèn)棧頂元素這個(gè)接口，要先判斷棧是不是空。

四、隊(duì)列的概念

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

入隊(duì)列：進(jìn)行插入操作的一端稱為隊(duì)尾

出隊(duì)列：進(jìn)行刪除操作的一端稱為隊(duì)頭

隊(duì)列參照現(xiàn)實(shí)生活中的排隊(duì)

五、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;//加個(gè)size，方便統(tǒng)計(jì)長(zhǎng)度
}Queue;
void QueueInit(Queue* pq);//初始化
void QueueDestroy(Queue* pq);//銷毀
void QueuePush(Queue* pq,QDataType x);//入隊(duì)（尾插）
bool QueueEmpty(Queue* pq);//判斷隊(duì)列是否為空
void QueuePop(Queue* pq);//出隊(duì)（頭刪）
int QueueSize(Queue* pq);//統(tǒng)計(jì)隊(duì)列長(zhǎng)度
QDataType QueueFront(Queue* pq);//訪問(wèn)隊(duì)頭數(shù)據(jù)
QDataType QueueBack(Queue* pq);//訪問(wèn)隊(duì)尾數(shù)據(jù)

因?yàn)轫樞蚪Y(jié)構(gòu)不適合頭刪，這里使用單鏈表來(lái)實(shí)現(xiàn)隊(duì)列。

結(jié)構(gòu)體QNode用于模擬單鏈表，結(jié)構(gòu)體Queue中存放了單鏈表的頭、尾指針、鏈表節(jié)點(diǎn)個(gè)數(shù)。使用Queue來(lái)操縱單鏈表。

單鏈表的頭head是隊(duì)頭（頭刪出數(shù)據(jù)），tail是隊(duì)尾（尾插錄數(shù)據(jù)）

六、Queue.c

1、隊(duì)列的初始化和銷毀

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

和單鏈表的銷毀方式一樣，注意銷毀時(shí)需要逐個(gè)節(jié)點(diǎn)銷毀。

2、隊(duì)列的入隊(duì)、出隊(duì)

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

入隊(duì)：尾插一個(gè)節(jié)點(diǎn)

出隊(duì)：頭刪一個(gè)節(jié)點(diǎn)

3、隊(duì)列的判空

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

4、訪問(wèn)隊(duì)頭、隊(duì)尾數(shù)據(jù)、統(tǒng)計(jì)隊(duì)列長(zhǎng)度

int QueueSize(Queue* pq)//統(tǒng)計(jì)隊(duì)列長(zhǎng)度
{
    assert(pq);
    return pq->size;
}
QDataType QueueFront(Queue* pq)//訪問(wèn)隊(duì)頭數(shù)據(jù)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->head->data;
}
QDataType QueueBack(Queue* pq)//訪問(wèn)隊(duì)尾數(shù)據(jù)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->tail->data;
}

訪問(wèn)接口，注意先判空。

七、力扣中棧和隊(duì)列OJ題

1、有效的括號(hào)

使用隊(duì)列來(lái)解決，創(chuàng)建一個(gè)棧，碰到左括號(hào)將其進(jìn)棧，碰到右括號(hào)則訪問(wèn)棧頂元素，不相符則為false，迭代比較相符則為true

bool isValid(char * s){
    ST st;
    StackInit(&st);
    while(*s)
    {
        if(*s=='('||*s=='{'||*s=='[')
        {
            StackPush(&st,*s);//壓棧
        }
        else//比較時(shí)的情況
        {
            if(StackEmpty(&st))
                return false;  
            else if(StackTop(&st)=='('&&*s!=')')//訪問(wèn)棧頂元素
            {
                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;
}

注：上述代碼還需要將棧的實(shí)現(xiàn)的代碼拷貝一份上去。

2、用隊(duì)列實(shí)現(xiàn)棧

入棧：選擇非空隊(duì)列進(jìn)行入棧

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

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);//入隊(duì),尾插
    }
    else
    {
        QueuePush(&obj->q2,x);//入隊(duì),尾插
    }
}
 
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)//將非空元素導(dǎo)入到空隊(duì)列，留下最后一個(gè)
    {
        QueuePush(empty,QueueFront(unEmpty));//入隊(duì),尾插
        QueuePop(unEmpty);//出隊(duì)（頭刪）
    }
    int top=QueueFront(unEmpty);
    QueuePop(unEmpty);//出隊(duì)（頭刪）
    return top;
}
 
int myStackTop(MyStack* obj) {
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);//訪問(wèn)隊(duì)尾數(shù)據(jù)
    }
    else
    {
        return QueueBack(&obj->q2);//訪問(wèn)隊(duì)尾數(shù)據(jù)
    }
}
 
bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}
 
void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);//銷毀
    QueueDestroy(&obj->q2);//銷毀
    free(obj);
}

注：上述代碼還需要將隊(duì)列的實(shí)現(xiàn)的代碼拷貝一份上去。

3、用棧實(shí)現(xiàn)隊(duì)列

現(xiàn)在有兩個(gè)棧，第一個(gè)棧用于入棧、出棧至第二個(gè)棧的操作，第二個(gè)棧僅用于出棧操作。

入棧：在第一個(gè)棧中壓入數(shù)據(jù)

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

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);
}

注：上述代碼還需要將棧的實(shí)現(xiàn)的代碼拷貝一份上去。

4、設(shè)計(jì)循環(huán)隊(duì)列

typedef struct {
    int* arr;
    int front;//記錄首
    int tail;//記錄尾的下一個(gè)
    int capacity;//用于處理邊界問(wèn)題的一個(gè)變量
} 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ù)處理邊界問(wèn)題要額外考慮分支情況
    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);
}

因?yàn)檠h(huán)隊(duì)列無(wú)法區(qū)分隊(duì)列為空和為滿的情況，因?yàn)闉榭蘸臀礉M，首位下標(biāo)是一樣的。

所以這道題有兩種解法，計(jì)數(shù)確定棧空棧滿，或者多開辟一個(gè)空間。本題采用后者。

可選的數(shù)據(jù)結(jié)構(gòu)也有兩種，順序和鏈表。本題采用順序。

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

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

capacity定義為k時(shí)的代碼如下：

typedef struct {
    int* arr;
    int front;//記錄首
    int tail;//記錄尾的下一個(gè)
    int capacity;//總?cè)萘?
} 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ū)別就是入隊(duì)出隊(duì)代碼，常規(guī)情況和邊界情況不能統(tǒng)一。

以上就是C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之棧和隊(duì)列的實(shí)現(xiàn)及應(yīng)用的詳細(xì)內(nèi)容，更多關(guān)于C語(yǔ)言棧隊(duì)列的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章:

欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

軟件下載

源碼下載

軟件編程

網(wǎng)絡(luò)編程

在線工具

數(shù)據(jù)庫(kù)

CMS

常用工具

C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之棧和隊(duì)列的實(shí)現(xiàn)及應(yīng)用

目錄

一、棧的概念

二、Stack.h

三、Stack.c

1、棧的初始化和銷毀

2、棧的進(jìn)棧、出棧

3、棧的判空、訪問(wèn)棧頂元素、棧內(nèi)元素個(gè)數(shù)

四、隊(duì)列的概念

五、Queue.h

六、Queue.c

1、隊(duì)列的初始化和銷毀

2、隊(duì)列的入隊(duì)、出隊(duì)

3、隊(duì)列的判空

4、訪問(wèn)隊(duì)頭、隊(duì)尾數(shù)據(jù)、統(tǒng)計(jì)隊(duì)列長(zhǎng)度

七、力扣中棧和隊(duì)列OJ題

1、有效的括號(hào)

2、用隊(duì)列實(shí)現(xiàn)棧

3、用棧實(shí)現(xiàn)隊(duì)列

4、設(shè)計(jì)循環(huán)隊(duì)列

相關(guān)文章

最新評(píng)論

大家感興趣的內(nèi)容

最近更新的內(nèi)容

常用在線小工具

C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之棧和隊(duì)列的實(shí)現(xiàn)及應(yīng)用

目錄

一、棧的概念

二、Stack.h

三、Stack.c

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

2、棧的進(jìn)棧、出棧

3、棧的判空、訪問(wèn)棧頂元素、棧內(nèi)元素個(gè)數(shù)

四、隊(duì)列的概念

五、Queue.h

六、Queue.c

1、隊(duì)列的初始化和銷毀

2、隊(duì)列的入隊(duì)、出隊(duì)

3、隊(duì)列的判空

4、訪問(wèn)隊(duì)頭、隊(duì)尾數(shù)據(jù)、統(tǒng)計(jì)隊(duì)列長(zhǎng)度

七、力扣中棧和隊(duì)列OJ題

1、有效的括號(hào)

2、用隊(duì)列實(shí)現(xiàn)棧

3、用棧實(shí)現(xiàn)隊(duì)列

4、設(shè)計(jì)循環(huán)隊(duì)列

相關(guān)文章

最新評(píng)論

大家感興趣的內(nèi)容

最近更新的內(nèi)容

常用在線小工具

1、棧的初始化和銷毀

2、棧的進(jìn)棧、出棧

3、棧的判空、訪問(wèn)棧頂元素、棧內(nèi)元素個(gè)數(shù)

四、隊(duì)列的概念

五、Queue.h

六、Queue.c

1、隊(duì)列的初始化和銷毀

2、隊(duì)列的入隊(duì)、出隊(duì)

3、隊(duì)列的判空

4、訪問(wèn)隊(duì)頭、隊(duì)尾數(shù)據(jù)、統(tǒng)計(jì)隊(duì)列長(zhǎng)度

七、力扣中棧和隊(duì)列OJ題

2、用隊(duì)列實(shí)現(xiàn)棧

4、設(shè)計(jì)循環(huán)隊(duì)列