網站首頁編程語言正文

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

作者：蔣靈瑜的筆記本 ? 更新時間： 2022-10-14 編程語言

一、棧的概念

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

棧中的數據元素遵守后進先出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);//數組元素個數

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

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

三、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，方便統計長度
}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);//統計隊列長度
QDataType QueueFront(Queue* pq);//訪問隊頭數據
QDataType QueueBack(Queue* pq);//訪問隊尾數據

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

結構體QNode用于模擬單鏈表，結構體Queue中存放了單鏈表的頭、尾指針、鏈表節點個數。使用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;
}

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

2、隊列的入隊、出隊

void QueuePush(Queue* pq, QDataType x)//入隊,尾插
{
    assert(pq);
    //創建一個新節點
    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--;
}

入隊：尾插一個節點

出隊：頭刪一個節點

3、隊列的判空

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

4、訪問隊頭、隊尾數據、統計隊列長度

int QueueSize(Queue* pq)//統計隊列長度
{
    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、有效的括號

使用隊列來解決，創建一個棧，碰到左括號將其進棧，碰到右括號則訪問棧頂元素，不相符則為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至另一個隊列，再對那個遺留的元素執行出隊列操作即可模擬出棧動作

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、用棧實現隊列

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

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

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

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、設計循環隊列

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的話,后續處理邊界問題要額外考慮分支情況
    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);
}

因為循環隊列無法區分隊列為空和為滿的情況，因為為空和未滿，首位下標是一樣的。

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

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

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

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

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

主要區別就是入隊出隊代碼，常規情況和邊界情況不能統一。

原文鏈接：https://blog.csdn.net/gfdxx/article/details/126397879

上一篇：windows?server設置FTP域用戶隔離的方法_FT
下一篇：VSCode連接實驗室服務器Xshell,Xftp向服務器傳

日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

網站首頁編程語言正文

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

目錄

一、棧的概念

二、Stack.h

三、Stack.c

1、棧的初始化和銷毀

2、棧的進棧、出棧

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

四、隊列的概念

五、Queue.h

六、Queue.c

1、隊列的初始化和銷毀

2、隊列的入隊、出隊

3、隊列的判空

4、訪問隊頭、隊尾數據、統計隊列長度

七、力扣中棧和隊列OJ題

1、有效的括號

2、用隊列實現棧

3、用棧實現隊列

4、設計循環隊列

相關推薦

日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

網站首頁 編程語言 正文

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

目錄

一、棧的概念

二、Stack.h

三、Stack.c

1、棧的初始化和銷毀

2、棧的進棧、出棧

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

四、隊列的概念

五、Queue.h

六、Queue.c

1、隊列的初始化和銷毀

2、隊列的入隊、出隊

3、隊列的判空

4、訪問隊頭、隊尾數據、統計隊列長度

七、力扣中棧和隊列OJ題

1、有效的括號

2、用隊列實現棧

3、用棧實現隊列

4、設計循環隊列

相關推薦

網站首頁編程語言正文