🏝?專欄：【數(shù)據(jù)結(jié)構(gòu)實戰(zhàn)篇】

🌅主頁：f狐o貍x

---

? ? ? ? ?在前面的文章中我們用C語言實現(xiàn)了棧的數(shù)據(jù)結(jié)構(gòu)，本期內(nèi)容我們將實現(xiàn)隊列的數(shù)據(jù)結(jié)構(gòu)

一、隊列的概念

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

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

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

二、隊列的實現(xiàn)

? ? ? ? 2.1 隊列的定義

? ? ? ? 動用你聰明的小腦袋想一想隊列的結(jié)構(gòu)是啥樣的，是不是從隊尾插入數(shù)據(jù)，再從隊頭輸出數(shù)據(jù)，那是不是在隊列的結(jié)構(gòu)里面需要一個頭結(jié)點，還需要一個尾節(jié)點，為了方便后面的操作，我們再加一個size變量來記錄當(dāng)前隊列的大小

typedef int QDatatype;typedef struct QueueNode
{QDatatype Data;struct QueueNode* next;
}QueueNode;typedef struct Queue
{struct QueueNode* head;struct QueueNode* tail;int size;
}Queue;

? ? ? ? 2.2 隊列的初始化

//初始化隊列
void QueueInit(Queue* pq)
{pq->size = 0;pq->head = NULL;pq->tail = NULL;
}

? ? ? ? 2.3 隊列入、出

? ? ? ? 其實這里就是簡單的尾插和頭刪

//隊列增
void QueuePush(Queue* pq, QDatatype x)
{QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc fail");return;}newnode->Data = x;newnode->next = NULL;if (pq->head == NULL){assert(pq->tail == NULL);pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}
//隊列刪
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));QueueNode* cur = pq->head;if (cur->next == NULL){free(cur);cur = NULL;}else{pq->head = pq->head->next;free(cur);cur = NULL;}pq->size--;
}

? ? ? ? 2.4 檢查隊列是否為空、隊列大小

//隊列大小
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}
//判斷隊列是否為空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}

? ? ? ? 2.5 返回隊頭、隊尾

//返回隊頭
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;
}

? ? ? ? 2.6 測試隊列

int main()
{Queue Q = { 0 };QueueInit(&Q);QueuePush(&Q, 1);QueuePush(&Q, 2);QueuePush(&Q, 3);QueuePush(&Q, 4);QueuePush(&Q, 5);QueuePush(&Q, 6);while (!QueueEmpty(&Q)){printf("%d ", QueueFront(&Q));QueuePop(&Q);}return 0;
}

? ? ? ? 運行結(jié)果如下：

三、實戰(zhàn)練習(xí)

? ? ? ? 學(xué)習(xí)了棧和隊列的數(shù)據(jù)結(jié)構(gòu)，我們現(xiàn)在就來練練手

? ? ? ? 3.1 有效的括號

? ? ? ? 力扣鏈接：有效的括號

? ? ? ? 給定一個只包括?'('，')'，'{'，'}'，'['，']'?的字符串?s?，判斷字符串是否有效

? ? ? ? 3.1.1題目分析

? ? ? ? 這個題可以用棧的結(jié)構(gòu)來完成這個題，如果字符串中是左括號 ‘ （ ’ ‘ [ ’ ‘ { ’，則正常入棧，如果字符串為右括號‘ )?’ ‘ ] ’ ‘ } ’，則將這個字符和棧頂元素對比，如果相等就進(jìn)行下一次循環(huán)，如果沒有匹配成功，則放回false，循環(huán)結(jié)束后，并且棧里沒有元素了，就返回true，記得在每次返回的時候?qū)⒖臻g釋放了，不要有內(nèi)存泄漏哈~

? ? ? ? 3.1.2 解題代碼

? ? ? ? 對了，因為這里用的是c語言，因此我們需要自己手搓一個棧，不過問題不大啦

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef int StackDataType;typedef struct stack
{int* StackData;int top;int capacity;
}ST;//初始化
void InitStack(ST* ps);
//銷毀
void DestoryStack(ST* ps);
//增加
void STPush(ST* ps, StackDataType x);
//刪除
void STPop(ST* ps);
//判斷是否為空
bool STEmpty(ST* ps);
//棧頂位置
StackDataType STTop(ST* ps);//初始化
void InitStack(ST* ps)
{assert(ps);ps->StackData = (StackDataType*)malloc(sizeof(StackDataType)*4);if (ps->StackData == NULL){perror("InitStack：：malloc");return;}ps->capacity = 4;ps->top = 0;
}//銷毀
void DestoryStack(ST* ps)
{assert(ps);free(ps->StackData);ps->StackData = NULL;ps->capacity = 0;ps->top = 0;
}//增加
void STPush(ST* ps, StackDataType x)
{assert(ps);if (ps->top == ps->capacity){StackDataType* tmp = (StackDataType*)realloc(ps->StackData,sizeof(StackDataType) * ps->capacity * 2);if(tmp == NULL){perror("STPush：：realloc");return;}ps->StackData = tmp;ps->capacity *= 2;}ps->StackData[ps->top] = x;ps->top += 1;}//刪除
void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));ps->top--;
}//判斷是否為空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}//棧頂位置
StackDataType STTop(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps->StackData[ps->top - 1];
}bool isValid(char* s) {ST st = {0};InitStack(&st);char* ps = s;while(*s){if(*s == '(' || *s == '[' || *s == '{'){STPush(&st, *s);//左括號入棧}else{if(STEmpty(&st)){DestoryStack(&st);return false;}char top = STTop(&st);STPop(&st);if((*s == ')' && top != '(') ||(*s == ']' && top != '[') ||(*s == '}' && top != '{')){DestoryStack(&st);return false;                }}s++;}bool ret = STEmpty(&st);DestoryStack(&st);return ret;
}

? ? ? ? 3.2 用隊列實現(xiàn)棧

? ? ? ? 力扣鏈接：用隊列實現(xiàn)棧

????????請你僅使用兩個隊列實現(xiàn)一個后入先出（LIFO）的棧，并支持普通棧的全部四種操作（push、top、pop?和?empty）

? ? ? ? 3.2.1 題目分析

? ? ? ? 題目要求我們用兩個隊列來實現(xiàn)棧的結(jié)構(gòu)，因此我們可以先隨便將數(shù)據(jù)輸入到一個隊列中，再把隊列一中的數(shù)據(jù)除了最后一個，全部轉(zhuǎn)移到另外一個空的隊列中，這樣就可以實現(xiàn)棧的操作

? ? ? ? ?3.2.2 解題代碼

? ? ? ? 這里也是同樣的需要我們手搓一個隊列出來，不過上面已經(jīng)實現(xiàn)過來，所以我們直接cv一下

typedef int QDatatype;typedef struct QueueNode
{QDatatype Data;struct QueueNode* next;
}QueueNode;typedef struct Queue
{struct QueueNode* head;struct QueueNode* tail;int size;
}Queue;//初始化隊列
void QueueInit(Queue* pq);
//銷毀隊列
void QueueDestroy(Queue* pq);
//隊列增
void QueuePush(Queue* pq, QDatatype x);
//隊列刪
void QueuePop(Queue* pq);
//隊列大小
int QueueSize(Queue* pq);
//判斷隊列是否為空
bool QueueEmpty(Queue* pq);
//返回隊頭
QDatatype QueueFront(Queue* pq);
//返回隊尾
QDatatype QueueBack(Queue* pq);//初始化隊列
void QueueInit(Queue* pq)
{pq->size = 0;pq->head = NULL;pq->tail = NULL;
}//銷毀隊列
void QueueDestroy(Queue* pq)
{assert(pq);QueueNode* cur = pq->head;while (cur){QueueNode* del = cur;cur = cur->next;free(del);}pq->head = NULL;pq->tail = NULL;pq->size = 0;
}
//隊列增
void QueuePush(Queue* pq, QDatatype x)
{QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc fail");return;}newnode->Data = x;newnode->next = NULL;if (pq->head == NULL){assert(pq->tail == NULL);pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}
//隊列刪
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq->head->next == NULL){free(pq->head);pq->head = NULL;}else{QueueNode* next = pq->head->next;free(pq->head);pq->head = next;}pq->size--;
}
//隊列大小
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}
//判斷隊列是否為空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}
//返回隊頭
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;
}typedef struct {Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {MyStack* pst = (MyStack*)malloc(sizeof(MyStack));if(pst == NULL){perror("myStackCreate::malloc");}QueueInit(&pst->q1);QueueInit(&pst->q2);return pst;
}void myStackPush(MyStack* obj, int x) {if(!QueueEmpty(&obj->q1)){QueuePush(&obj->q1,x);}else{QueuePush(&obj->q2,x);}
}int myStackPop(MyStack* obj) {Queue* emptyQ = &obj->q1;Queue* nonemptyQ = &obj->q2;if(!QueueEmpty(&obj->q1)){emptyQ = &obj->q2;nonemptyQ = &obj->q1;}while(QueueSize(nonemptyQ)>1){QueuePush(emptyQ,QueueFront(nonemptyQ));QueuePop(nonemptyQ);}int top = QueueFront(nonemptyQ);QueuePop(nonemptyQ);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);
}

? ? ? ? 本期內(nèi)容到這里就完啦，感謝大家觀看~

? ? ? ? 對了對了，留下你的三連吧，求你啦~ QAQ