數據結構棧和隊列力扣例題AC—

20. 有效的括號

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

有效字符串需滿足：

左括號必須用相同類型的右括號閉合。
左括號必須以正確的順序閉合。
每個右括號都有一個對應的相同類型的左括號。

AC

typedef char STDataType;
typedef struct Stack
{STDataType* a;int top; //標識棧頂位置，元素數量int capacity; //棧的容量
}ST;void STInit(ST* pst);
void STDestory(ST* pst);
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);STDataType STTop(ST* pst);
bool STEmpty(ST* pst);
int STSize(ST* pst);void STInit(ST* pst)
{assert(pst);pst->a = NULL;pst->capacity = 0;// 1.表示top指向棧頂元素的下一個位置pst->top = 0;// 2.表示top指向棧頂元素//pst->top = -1; // top為0的話不清楚是top為0還是空，因此空的時候給-1//位置(下標)   top     0     1//數值        -1(空)   0     1//top = 1指向棧頂元素的下一個位置}void STDestory(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->top = pst->capacity = 0;}void STPush(ST* pst, STDataType x)
{assert(pst);if (pst->top == pst->capacity){int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2; //如果棧的當前容量為0，將其設為4，否則將其擴大為當前容量的兩倍STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);if (tmp == NULL){perror("realloc fail");return;}pst->a = tmp; //將原來棧中數據的指針更新為新的內存空間的指針pst->capacity = newcapacity;}pst->a[pst->top] = x;pst->top++;
}void STPop(ST* pst)
{assert(pst);assert(pst->top > 0);pst->top--;
}STDataType STTop(ST* pst)
{assert(pst);assert(pst->top > 0);return pst->a[pst->top - 1];
}bool STEmpty(ST* pst)
{assert(pst);return pst->top == 0;
}int STSize(ST* pst)
{assert(pst);return pst->top;}bool isValid(char* s) {ST st;STInit(&st);while(*s){if(*s == '(' || *s == '[' || *s == '{'){STPush(&st,*s);}else{// 這種情況是右括號多，現在有右括號，但是現在存左括號的棧里是空的if(STEmpty(&st)){STDestory(&st);return false;}// 棧里面取左括號進行判斷char top = STTop(&st);STPop(&st);if((*s == ')' && top != '(')|| (*s == ']' && top != '[')|| (*s == '}' && top != '{')){return false;}}++s;}// 若左右括號數量不相同，棧里可能還會有括號，上述只能解決可以對應的// 棧為空，返回真，說明數量也匹配，這行解決左括號多，右括號少的情況bool ret = STEmpty(&st);STDestory(&st);return ret;
}

代碼思路

這道題使用C解題，需要創建一個棧，但是使用C++可以直接用棧，暫時先使用C語言解題，因此上述代碼實現了棧的功能（手搓哈哈哈，后續會更新C++版本），具體解題函數為最后一個。在棧里存儲左括號，如果遍歷到了左括號就入棧，遍歷到了右括號，就拿出棧里最后一個入棧的，也就是離該右括號最近的左括號進行判斷是不是相匹配的，這一步判斷由于是字符，所以需要將情況都列出來，然后只要不匹配就返回false，若果匹配s就繼續下一個判斷，但是在該左括號判斷后一定要出棧。

但是有種情況是右括號比左括號多，遍歷到了右括號，此時存左括號的棧是空的，這時候直接返回false，所以這里需要檢測棧是否為空，返回前需要將棧清空，否則有可能發生內存泄漏。

還有一種情況是左括號比右括號多，在右括號都遍歷完以后，棧內依舊存著左括號，因此在可以匹配的括號都判斷以后，需要檢測棧內是否為空，然后將棧清空。最后返回值使用了棧是否為空的判斷返回值ret，因為如果ret為true，就說明棧確實是空的，匹配正好都對應，符合題目要求，而返回false說明棧不空，左括號還有多余的，不是匹配的。

另外在創建實例的時候，要注意不能使用和形參一樣的變量，這段代碼中使用的是st，因為函數傳參寫的是s，否則會分不清到底是存儲需要入棧的左括號還是指向字符數組的指針。

225. 用隊列實現棧

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

AC

typedef int QDataType;
typedef struct QueueNode
{QDataType val;struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* phead; // 頭指針QNode* ptail; // 尾指針int size;
}Queue;void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}void QueueDestory(Queue* pq)
{assert(pq);QNode* cur = pq->phead;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");return;}newnode->val = x;newnode->next = NULL;if (pq->ptail == NULL){pq->ptail = pq->phead = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}void QueuePop(Queue* pq)
{assert(pq);// 空節點assert(pq->phead);QNode* del = pq->phead;pq->phead = pq->phead->next;free(del);// 一個節點的時候，phead向前走// del被free，ptail此時和del指的是一個節點，如果free，就變成了野指針if (pq->phead == NULL){pq->ptail = NULL;}pq->size--;
}QDataType QueueFront(Queue* pq)
{assert(pq);// 空節點assert(pq->phead);return pq->phead->val;
}QDataType QueueBack(Queue* pq)
{assert(pq);// 空節點assert(pq->phead);return pq->ptail->val;
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL;
}int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}//上述代碼為隊列的實現
//下邊開始用隊列實現棧的邏輯typedef struct {Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {MyStack* pst = (MyStack*)malloc(sizeof(MyStack));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;}// 非空隊列前N-1個導入空隊列，最后一個就是棧頂元素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) {QueueDestory(&obj->q1);QueueDestory(&obj->q2);free(obj);
}/*** Your MyStack struct will be instantiated and called as such:* MyStack* obj = myStackCreate();* myStackPush(obj, x);* int param_2 = myStackPop(obj);* int param_3 = myStackTop(obj);* bool param_4 = myStackEmpty(obj);* myStackFree(obj);
*/

代碼思路

棧和隊列的區別就是先進先出和后進先出，用隊列實現棧，假設現在隊列內已經入隊 1 2 3 4 5 ，要出隊的話必定是 1 2 3 4 5，現在是棧進行出棧，那么就是 5 4 3 2 1，此題給了我們兩個隊列，當我們要出棧，也就是讓 5 先出，就可以把隊列 1 中的 1 2 3 4 依次出隊，并同時入隊列 2，然后彈出 5，接著再將隊列 2 中的 1 2 3 出隊列并入隊列 1，彈出 4……依次這樣交替執行，就可以用兩個隊列實現棧了。（雖然這道題實際上并沒有什么卵用，但是邏輯結構真的很鍛煉人，我也是只清楚大致思路，代碼一團糟，可參考力扣官方給的解題代碼）

232. 用棧實現隊列

請你僅使用兩個棧實現先入先出隊列。隊列應當支持一般隊列支持的所有操作（push、pop、peek、empty）：

實現 MyQueue 類：

void push(int x) 將元素 x 推到隊列的末尾
int pop() 從隊列的開頭移除并返回元素
int peek() 返回隊列開頭的元素
boolean empty() 如果隊列為空，返回 true ；否則，返回 false

AC

typedef int STDataType;
typedef struct Stack
{STDataType* a;int top; //標識棧頂位置，元素數量int capacity; //棧的容量
}ST;void STInit(ST* pst);
void STDestroy(ST* pst);
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);STDataType STTop(ST* pst);
bool STEmpty(ST* pst);
int STSize(ST* pst);void STInit(ST* pst)
{assert(pst);pst->a = NULL;pst->capacity = 0;pst->top = 0;
}void STDestroy(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->top = pst->capacity = 0;
}void STPush(ST* pst, STDataType x)
{assert(pst);if (pst->top == pst->capacity){int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2; //如果棧的當前容量為0，將其設為4，否則將其擴大為當前容量的兩倍STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);if (tmp == NULL){perror("realloc fail");return;}pst->a = tmp; //將原來棧中數據的指針更新為新的內存空間的指針pst->capacity = newcapacity;}pst->a[pst->top] = x;pst->top++;
}void STPop(ST* pst)
{assert(pst);assert(pst->top > 0);pst->top--;
}STDataType STTop(ST* pst)
{assert(pst);assert(pst->top > 0);return pst->a[pst->top - 1];}bool STEmpty(ST* pst)
{assert(pst);return pst->top == 0;
}int STSize(ST* pst)
{assert(pst);return pst->top;
}//上述代碼為棧的實現
//下邊開始用棧實現隊列的邏輯typedef struct {ST pushst;ST popst;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));STInit(&obj->pushst);STInit(&obj->popst);return obj;
}void myQueuePush(MyQueue* obj, int x) {STPush(&obj->pushst, x);
}int myQueuePop(MyQueue* obj) {int front = myQueuePeek(obj);STPop(&obj->popst);return front;
}int myQueuePeek(MyQueue* obj) {if(STEmpty(&obj->popst)){// 倒數據過來while(!STEmpty(&obj->pushst)){STPush(&obj->popst, STTop(&obj->pushst));STPop(&obj->pushst);}}return STTop(&obj->popst);
}bool myQueueEmpty(MyQueue* obj) {return STEmpty(&obj->pushst) && STEmpty(&obj->popst);
}void myQueueFree(MyQueue* obj) {STDestroy(&obj->pushst);STDestroy(&obj->popst);free(obj);
}

代碼思路

用棧實現隊列，假設現在棧內已經入隊 1 2 3 4 5 ，要出棧的話必定是 5 4 3 2 1，現在是隊列進行出隊列，那么就是 1 2 3 4 5 ，此題給了我們兩個棧，當我們要出隊列，也就是讓 1 先出，就可以把棧 1 中的 5 4 3 2 依次出棧，并同時入棧 2，然后彈出 1，接著棧 2 中的 5 4 3 2 出棧就已經是隊列需要的順序了，執行棧2的出棧就是整個隊列的出隊機制了。Peek是查隊列頭部元素，那就是棧2的頂部元素，棧1如果為空直接返回棧2的頂部元素，不為空先pop到棧2再返回。說實話棧實現隊列更容易一些，到這里邏輯比隊列實現棧清楚許多了