4.棧的完整代碼

Stack.h

#pragma once
#include<stdio.h>
#include<malloc.h>
#include<stdbool.h>
#include<assert.h>typedef int  STDateType;typedef struct Stack
{STDateType* a;int top;int capacity;
}Stack;//棧的初始化
void StackInit(Stack* ps);
//棧的銷毀
void StackDestroy(Stack* ps);
//入棧
void StackPush(Stack* ps, STDateType x);
//出棧
void StackPop(Stack* ps);
//棧的個數(shù)
int StackSize(Stack* ps);
//棧是否為空
bool StackEmpty(Stack* ps);
//取出棧頂?shù)臄?shù)據(jù)
STDateType StackTop(Stack* ps);

Stack.c

#define _CRT_SECURE_NO_WARNINGS 1#include"Stack.h"//棧的初始化
void StackInit(Stack* ps)
{assert(ps);ps->a = (STDateType*)malloc(sizeof(STDateType) * 4);if (ps->a == NULL){perror("malloc fail");return;}ps->top = 0;ps->capacity = 4;
}
//棧的銷毀
void StackDestroy(Stack* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = 0;ps->capacity = 0;
}
//入棧
void StackPush(Stack* ps, STDateType x)
{assert(ps);if (ps->top == ps->capacity){STDateType* tmp = (STDateType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDateType));if (tmp == NULL){perror("realloc fail");return;}ps->a = tmp;ps->capacity *= 2;}ps->a[ps->top] = x;ps->top++;
}
//出棧
void StackPop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));ps->top--;
}
//棧的個數(shù)
int StackSize(Stack* ps)
{assert(ps);return ps->top;
}
//棧是否為空
bool StackEmpty(Stack* ps)
{assert(ps);return ps->top == 0;
}
//取出棧頂?shù)臄?shù)據(jù)
STDateType StackTop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));return ps->a[ps->top - 1];
}

Test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
void TestStack1()
{Stack s;StackInit(&s);StackPush(&s, 1);StackPush(&s, 2);StackPush(&s, 3);StackPush(&s, 4);StackPush(&s, 5);printf("%d\n", StackSize(&s));while (!StackEmpty(&s)){printf("%d ", StackTop(&s));StackPop(&s);}StackDestroy(&s);
}
int main()
{TestStack1();return 0;
}

5.有效的括號

題目鏈接：力扣

題目解析：對于這道題，最簡單的方法就是使用一個棧來記錄左括號，如果是左括號，則入棧，如果不是左括號，先取出棧頂?shù)脑?#xff0c;并出棧。然后將棧頂元素與當(dāng)前的字符進行比較。如果滿足錯誤條件，則銷毀棧后直接返回即可。

如果可以匹配，則直接讓s++即可。最后當(dāng)所有字符串遍歷完成以后，然后根據(jù)棧是否為空，返回即可

typedef char STDateType;typedef struct Stack
{STDateType* a;int top;int capacity;
}Stack;
//棧的初始化
void StackInit(Stack* ps)
{assert(ps);ps->a = (STDateType*)malloc(sizeof(STDateType) * 4);if (ps->a == NULL){perror("malloc fail");return;}ps->top = 0;ps->capacity = 4;
}
//棧的銷毀
void StackDestroy(Stack* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = 0;ps->capacity = 0;
}
//入棧
void StackPush(Stack* ps, STDateType x)
{assert(ps);if (ps->top == ps->capacity){STDateType* tmp = (STDateType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDateType));if (tmp == NULL){perror("realloc fail");return;}ps->a = tmp;ps->capacity *= 2;}ps->a[ps->top] = x;ps->top++;
}
//棧是否為空
bool StackEmpty(Stack* ps)
{assert(ps);return ps->top == 0;
}
//出棧
void StackPop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));ps->top--;
}
//棧的個數(shù)
int StackSize(Stack* ps)
{assert(ps);return ps->top;
}//取出棧頂?shù)臄?shù)據(jù)
STDateType StackTop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));return ps->a[ps->top - 1];
}
bool isValid(char * s){Stack st;StackInit(&st);while(*s!='\0'){if( (*s=='(')||(*s=='[')||(*s=='{')){StackPush(&st,*s);}else{if(StackEmpty(&st)){StackDestroy(&st);return false;}char p=StackTop(&st);StackPop(&st);if( ((*s!=')')&&(p=='('))|| ((*s!=']')&&(p=='['))||((*s!='}')&&(p=='{'))){StackDestroy(&st);return false;}}s++;}bool ret =StackEmpty(&st);StackDestroy(&st);return ret;
}

二、隊列

1.隊列的概念及結(jié)構(gòu)

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

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

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

?

2.隊列的實現(xiàn)方案

對于隊列的實現(xiàn)，我們?nèi)匀挥謨煞N方法可以選擇，一種是鏈表形式，一種是順序表形式

如果采用順序表來實現(xiàn)的話，我們會發(fā)現(xiàn)頭刪操作時間復(fù)雜度較高。

如果采用鏈表來實現(xiàn)的話，我們發(fā)現(xiàn)找尾部結(jié)點的時間復(fù)雜度較高，但是我們可以多定義一個結(jié)點來隨時知道尾部結(jié)點的地址。這樣就可以優(yōu)化掉找尾的時間復(fù)雜度。而且對于計算隊列長度的話，我們也可以多定義一個變量size，我們在刪除和插入數(shù)據(jù)的時候調(diào)整好size的大小。就可以優(yōu)化掉計算隊列長度的時間復(fù)雜度

這里我們也產(chǎn)生一個新的問題，對于單鏈表，能否多定義一個指針來控制尾部的地址，從而優(yōu)化找尾的時間復(fù)雜度。

其實是不行的，對于尾插顯然可以優(yōu)化，但是對于尾刪就不可以了。因為他需要找前一個結(jié)點的地址。

對于單鏈表我們也可以使用一個變量size，用來優(yōu)化計算單鏈表長度的時間復(fù)雜度

綜上所述，我們發(fā)現(xiàn)采用鏈表的結(jié)構(gòu)是最優(yōu)的。這個鏈表有一些不同的是，我們需要使用頭尾兩個指針以及一個size變量來進行優(yōu)化，既然如此，那么我們就最好使用一個結(jié)構(gòu)體來連接這些變量。否則傳參的時候我們需要傳三個以上的變量。

typedef int QDateType;typedef struct QNode
{QDateType data;struct QNode* next;
}QNode;typedef  struct Queue
{QNode* head;QNode* tail;int size;
}Queue;

3.隊列的實現(xiàn)

1.初始化隊列

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

如上代碼所示，我們直接傳結(jié)構(gòu)體的地址就可以了。

2.隊尾入數(shù)據(jù)

//申請一個結(jié)點
QNode* BuyQNode(QDateType x)
{QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");return NULL;}newnode->next = NULL;newnode->data = x;return newnode;
}
//隊尾入隊列
void QueuePush(Queue* q, QDateType x)
{assert(q);QNode* newnode = BuyQNode(x);if (q->tail == NULL){q->head = q->tail = newnode;}else{q->tail->next = newnode;q->tail = q->tail->next;}q->size++;
}

隊尾入數(shù)據(jù)的話，與單鏈表的入數(shù)據(jù)思路是一致的，我們先申請一個結(jié)點，然后判斷這個鏈表是否為空，如果為空，則特殊處理，否則正常尾插即可

3.隊頭出數(shù)據(jù)

//隊頭出隊列
void QueuePop(Queue* q)
{assert(q);assert(q->head);QNode* first = q->head->next;free(q->head);q->head = first;q->size--;if (q->head == NULL){q->tail = NULL;}
}

對于出數(shù)據(jù)，與單鏈表是一樣的，但是我們需要特別注意尾指針，如果刪了隊列最后一個結(jié)點后隊列為空，那么需要將尾結(jié)點置為空

4.獲取頭部尾部數(shù)據(jù)

//獲取隊列頭部元素
QDateType QueueFront(Queue* q)
{assert(q);assert(q->head);return q->head->data;
}
//獲取隊列尾部元素
QDateType QueueBack(Queue* q)
{assert(q);assert(q->head);return q->tail->data;
}

對于這兩個函數(shù)，基本思路是一樣的，我們先判斷鏈表不為空，然后直接返回數(shù)據(jù)即可

5.獲取隊列中的有效元素的個數(shù)

//獲取隊列中的有效元素個數(shù)
int QueueSize(Queue* q)
{assert(q);return q->size;
}

對于這段代碼，我們直接返回size即可

6.檢測隊列是否為空

//檢測隊列是否為空
bool QueueEmpty(Queue* q)
{assert(q);return q->head == NULL;
}

這段代碼也很簡單，直接返回這個判斷條件即可

7.銷毀隊列

//銷毀隊列
void QueueDestroy(Queue* q)
{assert(q);QNode* cur = q->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}q->head = q->tail = NULL;q->size = 0;
}

銷毀隊列的方法與單鏈表的銷毀是一樣的，我們需要注意的是，別忘記置空head和tail以及size。

4.隊列實現(xiàn)的完整代碼

Queue.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<stdbool.h>
#include<assert.h>typedef int QDateType;typedef struct QNode
{QDateType data;struct QNode* next;
}QNode;typedef  struct Queue
{QNode* head;QNode* tail;int size;
}Queue;//初始化隊列
void QueueInit(Queue* q);
//隊尾入隊列
void QueuePush(Queue* q, QDateType x);
//隊頭出隊列
void QueuePop(Queue* q);
//獲取隊列頭部元素
QDateType QueueFront(Queue* q);
//獲取隊列尾部元素
QDateType QueueBack(Queue* q);
//獲取隊列中的有效元素個數(shù)
int QueueSize(Queue* q);
//檢測隊列是否為空
bool QueueEmpty(Queue* q);
//銷毀隊列
void QueueDestroy(Queue* q);

Queue.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"//初始化隊列
void QueueInit(Queue* q)
{assert(q);q->head = NULL;q->tail = NULL;q->size = 0;
}
//申請一個結(jié)點
QNode* BuyQNode(QDateType x)
{QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");return NULL;}newnode->next = NULL;newnode->data = x;return newnode;
}
//隊尾入隊列
void QueuePush(Queue* q, QDateType x)
{assert(q);QNode* newnode = BuyQNode(x);if (q->tail == NULL){q->head = q->tail = newnode;}else{q->tail->next = newnode;q->tail = q->tail->next;}q->size++;
}
//隊頭出隊列
void QueuePop(Queue* q)
{assert(q);assert(q->head);QNode* first = q->head->next;free(q->head);q->head = first;q->size--;if (q->head == NULL){q->tail = NULL;}
}
//獲取隊列頭部元素
QDateType QueueFront(Queue* q)
{assert(q);assert(q->head);return q->head->data;
}
//獲取隊列尾部元素
QDateType QueueBack(Queue* q)
{assert(q);assert(q->head);return q->tail->data;
}
//獲取隊列中的有效元素個數(shù)
int QueueSize(Queue* q)
{assert(q);return q->size;
}
//檢測隊列是否為空
bool QueueEmpty(Queue* q)
{assert(q);return q->head == NULL;
}
//銷毀隊列
void QueueDestroy(Queue* q)
{assert(q);QNode* cur = q->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}q->head = q->tail = NULL;q->size = 0;
}

Test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"void TestQueue1()
{Queue pq;QueueInit(&pq);QueuePush(&pq, 1);QueuePush(&pq, 2);QueuePush(&pq, 3);QueuePush(&pq, 4);QueuePush(&pq, 5);printf("%d \n", QueueSize(&pq));while (!QueueEmpty(&pq)){printf("%d ", QueueFront(&pq));QueuePop(&pq);}QueueDestroy(&pq);
}
int main()
{TestQueue1();return 0;
}

本期內(nèi)容就到這里了

如果對你有幫助的話，不要忘記點贊加收藏哦！！！