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

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

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

一、棧的概念

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

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

壓棧：棧的插入操作叫做進棧\壓棧\入棧，入數(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ù)組元素個數(shù)（top-1為最后一個元素的下標）就是順序表的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);//訪問棧頂元素
int StackSize(ST* ps);//數(shù)組元素個數(shù)

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

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

三、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、棧的判空、訪問棧頂元素、棧內(nèi)元素個數(shù)

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)//數(shù)組元素個數(shù)
{
    assert(ps);
    return ps->top;
}

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

四、隊列的概念

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

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

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

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

五、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);//訪問隊頭數(shù)據(jù)
QDataType QueueBack(Queue* pq);//訪問隊尾數(shù)據(jù)

因為順序結(jié)構(gòu)不適合頭刪，這里使用單鏈表來實現(xiàn)隊列。

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

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

六、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、訪問隊頭、隊尾數(shù)據(jù)、統(tǒng)計隊列長度

int QueueSize(Queue* pq)//統(tǒng)計隊列長度
{
    assert(pq);
    return pq->size;
}
QDataType QueueFront(Queue* pq)//訪問隊頭數(shù)據(jù)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->head->data;
}
QDataType QueueBack(Queue* pq)//訪問隊尾數(shù)據(jù)
{
    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;
}

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

2、用隊列實現(xiàn)棧

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

出棧：隊列中只留一個元素，將其他元素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)//將非空元素導(dǎo)入到空隊列，留下最后一個
    {
        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);//訪問隊尾數(shù)據(jù)
    }
    else
    {
        return QueueBack(&obj->q2);//訪問隊尾數(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);
}

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

3、用棧實現(xiàn)隊列

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

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

出棧：如果第二個棧為空，則第一個棧中數(shù)據(jù)全部出棧至第二個棧，由第二個棧專門執(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);
}

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

4、設(shè)計循環(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ū)分隊列為空和為滿的情況，因為為空和未滿，首位下標是一樣的。

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

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

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

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

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

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

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

您可能感興趣的文章:

国产无遮挡裸体免费直播视频,久久精品国产蜜臀av,动漫在线视频一区二区,欧亚日韩一区二区三区,久艹在线免费视频,国产精品美女网站免费,正在播放 97超级视频在线观看,斗破苍穹年番在线观看免费,51最新乱码中文字幕

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

目錄

一、棧的概念

二、Stack.h

三、Stack.c

1、棧的初始化和銷毀

2、棧的進棧、出棧

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

四、隊列的概念

五、Queue.h

六、Queue.c

1、隊列的初始化和銷毀

2、隊列的入隊、出隊

3、隊列的判空

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

七、力扣中棧和隊列OJ題

1、有效的括號

2、用隊列實現(xiàn)棧

3、用棧實現(xiàn)隊列

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

相關(guān)文章

最新評論

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

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

常用在線小工具

国产无遮挡裸体免费直播视频,久久精品国产蜜臀av,动漫在线视频一区二区,欧亚日韩一区二区三区,久艹在线 免费视频,国产精品美女网站免费,正在播放 97超级视频在线观看,斗破苍穹年番在线观看免费,51最新乱码中文字幕

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

目錄

一、棧的概念

二、Stack.h

三、Stack.c

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

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

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

四、隊列的概念

五、Queue.h

六、Queue.c

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

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

3、隊列的判空

4、訪問隊頭、隊尾數(shù)據(jù)、統(tǒng)計隊列長度

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

1、有效的括號

2、用隊列實現(xiàn)棧

3、用棧實現(xiàn)隊列

4、設(shè)計循環(huán)隊列

相關(guān)文章

最新評論

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

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

常用在線小工具

国产无遮挡裸体免费直播视频,久久精品国产蜜臀av,动漫在线视频一区二区,欧亚日韩一区二区三区,久艹在线免费视频,国产精品美女网站免费,正在播放 97超级视频在线观看,斗破苍穹年番在线观看免费,51最新乱码中文字幕

一、棧的概念

二、Stack.h

1、棧的初始化和銷毀

2、棧的進棧、出棧

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

四、隊列的概念

五、Queue.h

六、Queue.c

1、隊列的初始化和銷毀

2、隊列的入隊、出隊

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

七、力扣中棧和隊列OJ題

3、用棧實現(xiàn)隊列

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