1、棧
1.1 概念與結構
? ? ? ? 棧是一種特殊的線性表，只允許在固定的一端進行插入和刪除元素的操作。進行數據插入和刪除的一端稱為棧頂，另一端稱為棧底。棧里面的數據元素遵循后進先出的原則。棧的底層實現一般可以使用數組或者鏈表來實現，但數組的實現更優，因為空間消耗更少。
1.2 棧的實現
Stack.c
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>//定義棧的結構
typedef int STDataType;
typedef struct Stack
{STDataType* arr;int top; //指向棧頂的位置int capacity; //棧的容量
}ST;//初始化
void StackInit(ST* ps);//入棧——棧頂
void StackPush(ST* ps, STDataType x);//出棧——棧頂
void StackPop(ST* ps);//棧是否為空
bool StackEmpty(ST* ps);//取棧頂元素
STDataType StackTop(ST* ps);//獲取棧中有效元素個數
int StackSize(ST* ps);//銷毀
void StackDestroy(ST* ps);?Stack.h
#define _CRT_SECURE_NO_WARNINGS 1
#include "Stack.h"//初始化
void StackInit(ST* ps)
{ps->arr = NULL;ps->top = ps->capacity = 0;
}//入棧——棧頂
void StackPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){//增容int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}ps->arr[ps->top++] = x;
}//棧是否為空
bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}//出棧——棧頂
void StackPop(ST* ps)
{assert(!StackEmpty(ps));ps->top--;
}//取棧頂元素
STDataType StackTop(ST* ps)
{assert(!StackEmpty(ps));return ps->arr[ps->top - 1];
}//獲取棧中有效元素個數
int StackSize(ST* ps)
{return ps->top;
}//銷毀
void StackDestroy(ST* ps)
{if (ps->arr)free(ps->arr);ps->arr = NULL;ps->capacity = ps->top = 0;
}test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "Stack.h"void test01()
{ST st;StackInit(&st);StackPush(&st, 1);StackPush(&st, 2);StackPush(&st, 3);StackPush(&st, 4);while (!StackEmpty(&st)){STDataType top = StackTop(&st);printf("%d ", top);StackPop(&st);}StackDestroy(&st);
}int main()
{test01();return 0;
}1.3 棧的算法題
https://leetcode.cn/problems/valid-parentheses
?思路：借助數據結構——棧
遍歷字符串，（1）左括號進棧（2）遇到右括號，取棧頂元素與之比較，看是否匹配
//定義棧的結構
typedef char STDataType;
typedef struct Stack
{STDataType* arr;int top; //指向棧頂的位置int capacity; //棧的容量
}ST;//初始化
void StackInit(ST* ps)
{ps->arr = NULL;ps->top = ps->capacity = 0;
}//入棧——棧頂
void StackPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){//增容int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}ps->arr[ps->top++] = x;
}//棧是否為空
bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}//出棧——棧頂
void StackPop(ST* ps)
{assert(!StackEmpty(ps));ps->top--;
}//取棧頂元素
STDataType StackTop(ST* ps)
{assert(!StackEmpty(ps));return ps->arr[ps->top - 1];
}//獲取棧中有效元素個數
int StackSize(ST* ps)
{return ps->top;
}//銷毀
void StackDestroy(ST* ps)
{if (ps->arr)free(ps->arr);ps->arr = NULL;ps->capacity = ps->top = 0;
}
//---------------------以上是棧的實現代碼-------------------
//借助數據結構——棧
bool isValid(char* s)
{ST st;StackInit(&st);char* pi = s;while(*pi != '\0'){//左括號入棧if(*pi == '(' || *pi == '[' || *pi == '{'){StackPush(&st, *pi);}else{//判斷棧為空的情況if(StackEmpty(&st)){StackDestroy(&st);return false;}//右括號——取棧頂與*pi進行匹配char top = StackTop(&st);if((top == '(' && *pi != ')') || (top == '[' && *pi != ']') || (top == '{' && *pi != '}')){StackDestroy(&st);return false;}StackPop(&st);}pi++;}bool ret = StackEmpty(&st) ? true : false;StackDestroy(&st);return ret;
}2、隊列
2.1 概念與結構
? ? ? ? 只允許在一端進行插入數據操作，在另一端進行刪除數據操作的特殊線性表。隊列具有先進先出的特點。進行插入操作的一端稱為隊尾，進行刪除操作的一端稱為隊頭。那么，隊列底層結構該如何實現呢？如果用數組來實現，那么入隊操作時間復雜度為O(1)，出隊O(N)。如果用鏈表來實現，那么入隊O(N)，出隊O(1)。但是，我們可以定義一個隊尾指針pTail來優化，這樣入隊的時間復雜度就變為O(1)。所以我們采用鏈表來實現隊列。
2.2 隊列的實現?
Queue.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>typedef int QDataType;
//隊列結點的結構
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QueueNode;
//隊列的結構
typedef struct Queue
{QueueNode* phead;QueueNode* ptail;int size; //隊列中有效數據個數
}Queue;//初始化
void QueueInit(Queue* pq);//銷毀隊列
void QueueDestroy(Queue* pq);//入隊——隊尾
void QueuePush(Queue* pq, QDataType x);//出隊——隊頭
void QueuePop(Queue* pq);//隊列判空
bool QueueEmpty(Queue* pq);//取隊頭數據
QDataType QueueFront(Queue* pq);//取隊尾數據
QDataType QueueBack(Queue* pq);//隊列有效元素個數
int QueueSize(Queue* pq);Queue.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"//初始化
void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}//銷毀隊列
void QueueDestroy(Queue* pq)
{assert(pq);QueueNode* pcur = pq->phead;while (pcur){QueueNode* next = pcur->next;free(pcur);pcur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}//入隊——隊尾
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;//隊列為空if (pq->phead == NULL){pq->phead = pq->ptail = newnode;}else{//隊列非空pq->ptail->next = newnode;pq->ptail = pq->ptail->next;}pq->size++;
}//隊列判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL;
}//出隊——隊頭
void QueuePop(Queue* pq)
{assert(!QueueEmpty(pq));//只有一個結點，phead和ptail都要置為空if (pq->phead == pq->ptail){free(pq->phead);pq->phead = pq->ptail = NULL;}else{QueueNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}pq->size--;
}//取隊頭數據
QDataType QueueFront(Queue* pq)
{assert(!QueueEmpty(pq));return pq->phead->data;
}//取隊尾數據
QDataType QueueBack(Queue* pq)
{assert(!QueueEmpty(pq));return pq->ptail->data;
}//隊列有效元素個數
int QueueSize(Queue* pq)
{assert(pq);//第一種方式:遍歷鏈表(適用于不會頻繁調用隊列有效數據個數的場景)//QueueNode* pcur = pq->phead;//int size = 0;//while (pcur)//{// size++;// pcur = pcur->next;//}//return size;//第二種方式:適用于頻繁調用隊列有效數據個數的場景return pq->size;
}test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"void test01()
{Queue q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);int front = QueueFront(&q);int rear = QueueBack(&q);printf("front:%d\n", front);printf("rear:%d\n", rear);printf("size:%d\n", QueueSize(&q));
}int main()
{test01();return 0;
}
