最新国产好看的视频,伊人天堂AV在线,国产Aaaaaa视频,蜜臀视频在线观看一区,人妻av色图,密臀久久久精品影片,青青视频免费观看毛片,久草在线观看视,国产三级精品色情在线

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

 更新時間：2022年08月18日 09:26:50   作者：蔣靈瑜的筆記本  
棧和隊列是一種數(shù)據(jù)結(jié)構(gòu)，只規(guī)定了性質(zhì)，并沒有規(guī)定實(shí)現(xiàn)方式。本文將以順序結(jié)構(gòu)實(shí)現(xiàn)棧，鏈表方式實(shí)現(xiàn)隊列，感興趣的小伙伴快跟隨小編一起學(xué)習(xí)一下吧

棧和隊列是一種數(shù)據(jù)結(jié)構(gòu)，只規(guī)定了性質(zhì)，并沒有規(guī)定實(shí)現(xiàn)方式。

本文以順序結(jié)構(gòu)實(shí)現(xiàn)棧，鏈表方式實(shí)現(xiàn)隊列。

一、棧的概念

棧：是一種特殊的線性表，其只允許在棧頂進(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ù)組元素個數(shù)（top-1為最后一個元素的下標(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);//訪問棧頂元素
int StackSize(ST* ps);//數(shù)組元素個數(shù)

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

數(shù)組的頭是棧底，數(shù)組尾是棧頂。棧主要的壓棧、出棧、訪問棧頂?shù)冉涌诜浅Ｆ鹾享樞虮淼奈膊濉⑽矂h、隨機(jī)訪問的特點(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ò)容

出棧時，先判空，再將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;
}

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

四、隊列的概念

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

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

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

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

五、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ù)

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

結(jié)構(gòu)體QNode用于模擬單鏈表，結(jié)構(gòu)體Queue中存放了單鏈表的頭、尾指針、鏈表節(jié)點(diǎn)個數(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é)點(diǎn)銷毀。

2、隊列的入隊、出隊

void QueuePush(Queue* pq, QDataType x)//入隊,尾插
{
    assert(pq);
    //創(chuàng)建一個新節(jié)點(diǎn)
    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é)點(diǎn)

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

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)建一個棧，碰到左括號將其進(jìn)棧，碰到右括號則訪問棧頂元素，不相符則為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;
}

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

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

入棧：選擇非空隊列進(jì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);
}

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

3、用棧實(shí)現(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);
}

注：上述代碼還需要將棧的實(shí)現(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);
}

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

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

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

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

強(qiáng)烈建議在初始化的接口中將capacity定義為k+1，因?yàn)槿腙牫鲫牻涌谥?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)之棧和隊列的實(shí)現(xiàn)及應(yīng)用的詳細(xì)內(nèi)容，更多關(guān)于C語言 棧 隊列的資料請關(guān)注腳本之家其它相關(guān)文章！

相關(guān)文章

  • C/C++ INI文件操作實(shí)現(xiàn)代碼

    C/C++ INI文件操作實(shí)現(xiàn)代碼

    本文章主要為分享C/C++ INI文件操作實(shí)現(xiàn)代碼，增加注釋和修復(fù)了一些問題。這里給出完整的實(shí)現(xiàn)文件，在需要的地方包含該頭文件就好了
    2020-02-02
  • c++ signal實(shí)現(xiàn)發(fā)送信號

    c++ signal實(shí)現(xiàn)發(fā)送信號

    這篇文章主要為大家詳細(xì)介紹了c++ signal實(shí)現(xiàn)發(fā)送信號的相關(guān)知識,文中的示例代碼講解詳細(xì),具有一定的學(xué)習(xí)價值,感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下
    2024-01-01
  • opencv4.5.4+VS2022開發(fā)環(huán)境搭建的實(shí)現(xiàn)

    opencv4.5.4+VS2022開發(fā)環(huán)境搭建的實(shí)現(xiàn)

    本文主要介紹了opencv4.5.4+VS2022開發(fā)環(huán)境搭建的實(shí)現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下
    2022-02-02
  • C++繼承介紹

    C++繼承介紹

    C++繼承可以是單一繼承或多重繼承，每一個繼承連接可以是public,protected,private也可以是virtual或non-virtual
    2013-01-01
  • C語言學(xué)生成績管理系統(tǒng)小設(shè)計

    C語言學(xué)生成績管理系統(tǒng)小設(shè)計

    這篇文章主要為大家詳細(xì)介紹了C語言學(xué)生成績管理系統(tǒng)小設(shè)計，具有一定的參考價值，感興趣的小伙伴們可以參考一下
    2018-01-01
  • C語言循環(huán)語句之重復(fù)執(zhí)行特定的代碼塊

    C語言循環(huán)語句之重復(fù)執(zhí)行特定的代碼塊

    在C語言中分支和循環(huán)語句是實(shí)現(xiàn)條件執(zhí)行和重復(fù)執(zhí)行的重要工具,下面這篇文章主要給大家介紹了關(guān)于C語言循環(huán)語句之重復(fù)執(zhí)行特定的代碼塊的相關(guān)資料,文中通過代碼介紹的非常詳細(xì),需要的朋友可以參考下
    2024-01-01
  • C++左值和右值學(xué)習(xí)筆記

    C++左值和右值學(xué)習(xí)筆記

    這篇文章主要為大家介紹了C++左值和右值學(xué)習(xí)筆記的重點(diǎn)講解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
    2023-10-10
  • C++實(shí)現(xiàn)LeetCode(66.加一運(yùn)算)

    C++實(shí)現(xiàn)LeetCode(66.加一運(yùn)算)

    這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(66.加一運(yùn)算),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下
    2021-07-07
  • C語言深入探究自定義類型之結(jié)構(gòu)體與枚舉及聯(lián)合

    C語言深入探究自定義類型之結(jié)構(gòu)體與枚舉及聯(lián)合

    今天我們來學(xué)習(xí)一下自定義類型，自定義類型包括結(jié)構(gòu)體、枚舉、聯(lián)合體，小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考
    2022-05-05
  • ACE反應(yīng)器(Reactor)模式的深入分析

    ACE反應(yīng)器(Reactor)模式的深入分析

    本篇文章是對ACE反應(yīng)器(Reactor)模式進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下
    2013-05-05

最新評論

沂源县| 广丰县| 郴州市| 安福县| 武宁县| 沛县| 巴楚县| 黄平县| 锦州市| 措美县| 宁武县| 郓城县| 安国市| 南乐县| 隆昌县| 屏东市| 久治县| 濉溪县| 顺昌县| 福建省| 永定县| 威海市| 新巴尔虎右旗| 南丹县| 杭锦旗| 三河市| 图们市| 蕲春县| 武胜县| 靖西县| 龙南县| 乐陵市| 青川县| 舞阳县| 平度市| 张家口市| 林口县| 闻喜县| 冕宁县| 阿瓦提县| 庄河市|