【數據結構】面試OJ題———棧|隊列|互相實現|循環隊列|括號匹配

1. 有效的括號

思路：

2.用隊列實現棧?

思路：

3.用棧實現隊列

思路：

?4.設計循環隊列

思路：

1. 有效的括號

20. 有效的括號 - 力扣（LeetCode）

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

有效字符串需滿足：

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

思路：

左右括號匹配，有兩個需要考慮的點；

1.括號順序問題；

2.括號數量問題；

1.括號順序問題：括號都有對應的左右邊，出現這樣的 ({)} 就是錯誤的；只有相應的左括號會有對應的右括號在旁邊；

棧：先進后出；一組括號，先比較的是最后輸入的左括號；所以棧滿足此功能；

隊列：先進先出；最先輸入的左括號應該是與最后輸入的右括號比較，所以隊列不滿足此功能；

2.括號順序問題：即使右括號都滿足了左括號，會有殘留問題，比如右括號多些，而此時空間已經為空；

我們構建一個棧的基本功能?；【數據結構】——棧|隊列（基本功能）-CSDN博客

// 支持動態增長的棧
typedef char STDataType;
typedef struct Stack
{STDataType* arr;	int top;		// 棧頂int capacity;  // 容量 
}Stack;// 初始化棧 
void StackInit(Stack* ps)
{assert(ps);assert(ps);ps->arr = NULL;ps->capacity = 0;ps->top = -1;	//表示棧頂元素
}// 入棧 
void StackPush(Stack* ps, STDataType data)
{//檢查容量if (ps->top + 1 == ps->capacity)	//top表示的是棧頂元素，先++top,再插入的，所以檢查+1位置是否可用{int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* newnode = (STDataType*)realloc(ps->arr,sizeof(STDataType) * newcapacity);assert(newnode);	//七匹狼式檢查是否開辟成功ps->arr = newnode;ps->capacity = newcapacity;}ps->top++;ps->arr[ps->top] = data;
}// 出棧 
void StackPop(Stack* ps)
{assert(ps);assert(ps->top >= 0);ps->top--;
}// 獲取棧頂元素 
STDataType StackTop(Stack* ps)
{assert(ps);assert(ps->top >= 0);return ps->arr[ps->top];
}// 檢測棧是否為空，如果為空返回非零結果，如果不為空返回0 
bool StackEmpty(Stack* ps)
{assert(ps);if (ps->top < 0)	//為空{return true;}else{return false;}
}// 銷毀棧 
void StackDestroy(Stack* ps)
{assert(ps);ps->capacity = 0;ps->top = -1;free(ps->arr);ps->arr = NULL;
}

當括號字符串所有左括號都存儲進棧中，當遇到右括號就開始逐個和棧頂括號比較；

?這里在于比較時，因為比較后還需要繼續比較，所以采取找到不符合的條件跳出循環；

在字符串循環結束后，要檢查是否棧為空

bool isValid(char* s) {Stack ps;StackInit(&ps);while(*s){//左括號入棧if(*s == '(' || *s == '{' || *s == '['){StackPush(&ps,*s);}//右括號與棧頂比較else{//檢查是否數量匹配,檢查棧是否還有元素,為空返回非0if(StackEmpty(&ps)){StackDestroy(&ps);return false;}//左右括號比較,不相等返回faslechar tmp = StackTop(&ps);StackPop(&ps); //移除棧頂元素if((tmp != '(' && *s == ')')||( tmp != '{' && *s == '}')|| (tmp != '[' && *s == ']')){StackDestroy(&ps);return false;}}++s;}bool tmp = StackEmpty(&ps);StackDestroy(&ps);return tmp;
}

2.用隊列實現棧?

225. 用隊列實現棧 - 力扣（LeetCode）

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

實現?MyStack?類：

void push(int x)?將元素 x 壓入棧頂。
int pop()?移除并返回棧頂元素。
int top()?返回棧頂元素。
boolean empty()?如果棧是空的，返回?true?；否則，返回?false?。

思路：

?棧是先進后出的結構，而隊列是先進先出的；

兩個隊列，數據存儲到隊列1中后，按照先進先出的結構，將size(元數個數)-1移動到隊列2中，再輸出隊列1的話，就實現了棧的結構，先進后出；

可以總結為：如果要輸入元素，就輸入到空隊列中

//將元素X壓入棧頂
void myStackPush(MyStack* obj, int x) {if(!QueueEmpty(&obj->q1))   //為空返回非0，取反{QueuePush(&obj->q1,x);}else{QueuePush(&obj->q2,x);}
}

如何找到棧頂元素呢，我們可以將不為空的隊列中 size(有效元素個數)-1個數據移動到空隊列中，再輸出原不為空的隊列；

我們采取假設法，找到不為空的隊列，假設某一隊列為empty，另外一個隊列為noempty；然后if條件判斷假設；?

//移除并返回棧頂元素
int myStackPop(MyStack* obj) {//將size-1個元素移動到 另一個空隊列中//假設q1隊列為空，q2不為空Queue* empty = &obj->q1;Queue* noempty = &obj->q2;//驗證假設if(!QueueEmpty(&obj->q1)){empty = &obj->q2;noempty = &obj->q1;}//將size-1個元素 移動到空隊列中while(QueueSize(noempty)>1){QueuePush(empty,QueueFront(noempty));QueuePop(noempty);}int top = QueueFront(noempty);    //此刻該隊列僅有需要的數據QueuePop(noempty);return top;}

?這兩個是這道題較為麻煩的函數，另外的函數需求因為較為簡單，我就直接碼上講解；

且這段代碼是這道題一半的代碼，另外一般就是隊列的基本功能實現代碼，可以去【數據結構】——棧|隊列（基本功能）-CSDN博客獲取完整的代碼，復制過來即可；

注：這里釋放內存是由里往外，因為結構定義了多重?

MyStack* myStackCreate() {MyStack* pst =  (MyStack*)malloc(sizeof(MyStack));QueueInit(&pst->q1);QueueInit(&pst->q2);return pst;
}//將元素X壓入棧頂
void myStackPush(MyStack* obj, int x) {if(!QueueEmpty(&obj->q1))   //為空返回非0，取反{QueuePush(&obj->q1,x);}else{QueuePush(&obj->q2,x);}
}
//移除并返回棧頂元素
int myStackPop(MyStack* obj) {//將size-1個元素移動到 另一個空隊列中//假設q1隊列為空，q2不為空Queue* empty = &obj->q1;Queue* noempty = &obj->q2;//驗證假設if(!QueueEmpty(&obj->q1)){empty = &obj->q2;noempty = &obj->q1;}while(QueueSize(noempty)>1){QueuePush(empty,QueueFront(noempty));QueuePop(noempty);}int top = QueueFront(noempty);QueuePop(noempty);return top;}
//返回棧頂元素
int myStackTop(MyStack* obj) {if(!QueueEmpty(&obj->q1))   //為空返回非0，取反{return QueueBack(&obj->q1);}else{return QueueBack(&obj->q2);}
}//如果棧是空，返回true，非空 返回fasle
bool myStackEmpty(MyStack* obj) {if(QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2))    //表示為空{return true;}elsereturn false;
}void myStackFree(MyStack* obj) {    //注意釋放順序QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);
}

3.用棧實現隊列

232. 用棧實現隊列 - 力扣（LeetCode）

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

實現?MyQueue?類：

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

思路：

?這道題和題2相似，要實現1先出去，就是先把入棧的元素全部移動到出棧中，就實現了隊列的結構；

與之不同的是：這邊需要把全部的數據移動到另一個棧；

可以定義兩個棧為：

pushst棧：用來數據存放的棧；

popst棧：用來輸出數據的棧；

1.需要獲得棧內數據時，先檢查popst棧是否為空，如果不為空，返回該棧數據即刻；

2.如果為空，先將pushst棧數據導入到popst棧內，在進行返回popst棧數據?

int myQueuePeek(MyQueue* obj) {if(!STEmpty(&obj->popst))   //popst棧有數據  直接返回棧頂元素{return STTop(&obj->popst);}else{//先將數據導入到popst棧while(!STEmpty(&obj->pushst)){STPush(&obj->popst,STTop(&obj->pushst));STPop(&obj->pushst);}//返回棧頂元素return STTop(&obj->popst);}
}

?注：這里和題2一樣，注意釋放順序

因為其他功能較為思路明了，解析過程會在代碼中解釋；?

棧函數接口實現功能代碼在【數據結構】——棧|隊列（基本功能）-CSDN博客

MyQueue* myQueueCreate() {MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));STInit(&obj->pushst);STInit(&obj->popst);return obj;
}void myQueuePush(MyQueue* obj, int x) {//數據進到pushst棧，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))   //popst棧有數據  直接返回棧頂元素{return STTop(&obj->popst);}else{//先將數據導入到popst棧while(!STEmpty(&obj->pushst)){STPush(&obj->popst,STTop(&obj->pushst));STPop(&obj->pushst);}//返回棧頂元素return STTop(&obj->popst);}
}bool myQueueEmpty(MyQueue* obj) {if(STEmpty(&obj->pushst) && STEmpty(&obj->popst)){return true;}elsereturn false;
}void myQueueFree(MyQueue* obj) {STDestrory(&obj->pushst);STDestrory(&obj->popst);free(obj);
}

?4.設計循環隊列

622. 設計循環隊列 - 力扣（LeetCode）

?設計你的循環隊列實現。循環隊列是一種線性數據結構，其操作表現基于 FIFO（先進先出）原則并且隊尾被連接在隊首之后以形成一個循環。它也被稱為“環形緩沖器”。

思路：

?這里有兩種數據結構可以選擇：數組和鏈表；

鏈表對后續的操作比較方便，但是不好控制，而且構建的時候也極為麻煩；

如果用數組需要考慮的是如何規避為滿和為空的判斷

采用數組的話，我們定義front，back；來進行判斷循環點；

這里的問題就是如何規避為滿和為空的問題；?

解決：1.可以定義一個size；在front == back的基礎上，size == 0 就是空

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? size ！= 0就是滿；

? ? ? ? 2. 可以多開辟一塊空間；動態空間；

多開辟一塊空間，這塊空間是動態移動的，但是不存儲數據；

當front == back時，就是空；

當 back+1 == front 就是滿，

這里因為數組如果在邊界點的話會導致越界，

所以采取取模來規范范圍；也達到了循環的條件

?這里需要注意的就是獲取最后一個結點；

因為back是指向最后一個數據的下一個位置；如果back在邊界 -1 有可能越界；

需要特殊處理規范這塊；

取模的操作：如果該數大于本身，就不會有影響；?

這里刪除和增加一個數據，都有可能引起越界；所以在對back front操作后，都要規范范圍；

取模實際空間大小?

typedef struct {int* parr;  //動態開辟int front;  //頭結點int back;   //指向尾結點的下一個int size;      //實際開辟的空間
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj->parr = (int*)malloc(sizeof(int)*(k+1));   //多開辟一塊空間obj->front = 0;obj->back = 0;obj->size= k+1;return obj;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->front == obj->back;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->back+1) % obj->size == obj->front;  //滿了返回真
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//先判斷是否滿了if(myCircularQueueIsFull(obj))  //滿了返回真return false;obj->parr[obj->back] = value;obj->back++;obj->back %= obj->size;return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {//判斷是否為空if(myCircularQueueIsEmpty(obj))return false;obj->front++;obj->front %= obj->size;return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;return obj->parr[obj->front];
}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;return obj->parr[(obj->back-1 + obj->size) % obj->size];
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->parr);free(obj);
}