一、有效的括號

題目鏈接：

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

題目的要求很簡單，就是要求我們判斷其輸入的括號字符串是否是有效的括號，那么我們要如何判斷呢？

我們可以這樣，我們遍歷出傳入的字符串，然后我們創建一個棧，然后如果這個字符是組左括號，那么我們就讓其入棧，然后如果是右括號，那么我們就取棧頂的元素和這個右括號進行對比，如果匹配那么就出棧，不匹配的話那么就說明這個字符串不是有效的括號，然后繼續進行比較，直到字符串遍歷完，那么我們字符串遍歷完后，是否就表示我們的這個括號是有效的呢？

并不是，我們還有一種情況，就是我們的字符串全是左括號，那么我們可以在最后進行判斷棧，如果棧不為空，那么就說明我們的字符串是無效的括號，那么我們要是為全是右括號的情況呢？

那么我們都是右括號的話，那么我們再取棧頂元素這里就會造成越界訪問了，所以我們再判斷到其字符不是左邊括號的時候，那么我們進入要其是右邊括號的情況，那么我們要先判斷棧內不為空才行。

那么我們可以將我們前面學習的棧的功能的代碼復制到oj平臺中，然后我們再寫題目中的函數。

二、用隊列實現棧

?題目鏈接：

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

上面的題目也很好理解，就是要我們使用兩個隊列來實現棧的功能，我們經過前面的學習都知道我們的隊列是先進先出，棧是先進后出，隊列是一端進，另外一端出，然后棧是只能從棧頂入棧和出棧。其他的兩個是差不多的。那么我們改如何使用兩個隊列來實現棧的功能呢？我們主要是要想辦法將我們入隊列的數據可以反過來出隊列，不過我們發現其不要求我們出棧要在一個隊列，我們要兩個隊列進行配合。

例如我們現在要入1，2，3，4。四個數據，那么我們的入隊列的順序為1->2->3->4，我們現在希望其出隊列的順序為4->3->2->1，那么我們改如何實現呢？

我們可以這樣，我們每次要出棧都是要出的入隊列最晚的數據，那么我們可以這樣，我們每次入棧，都將其先入到一個非空的隊列中，然后我們要出棧的時候，那么我們就將從出隊列那一端的前size-1個數據按照?入隊列的順序，將其轉移到另外一個空隊列，那么我們要出棧就對原來那個隊列進行出棧，那么就可以實現我們的先進先出的功能了。

我們這里需要使用很多隊列的功能，那么我們將我們前面完成的隊列的功能的函數都復制到oj平臺上。

首先我們要先創建兩個隊列，題目中提供了這個結構體，那么我們在這個結構體中創建兩個隊列成員即可。

然后我們要對我們的兩個隊列進行初初始化：

下面我們就要對數據進行入棧，我們提到了，我們入棧的話是將數據存儲到非空的隊列中，那么我們直接進行判斷隊列是否為空，不為空我們就調用我們的入隊的函數即可。

然后就是我們的出棧了，我們出棧，實際上是出的非空隊列的隊尾的元素，那么我們就先將非空隊列的隊尾前面的元素移動到空隊列中，然后再出隊，那么就可以完成出棧了。

然后就到我們的取棧頂元素，其實就是我們當前不為空的隊列的隊尾的元素：

然后就是我們的判斷當前棧是否為空：那么我們就判斷兩個隊列即可，首先我們這個棧要為空的話，那么我們就需要兩個隊列都為空，那么我們就返回teur，那么就是我們的判隊列為空的函數，當隊列為空的時候能返回true，然后兩個要都為空，所以我們使用一個與邏輯即可。

然后就剩下我們的銷毀棧啦，那么我們直接調用我們銷毀隊列的函數，將兩個隊列進行銷毀，然后再將這個棧結構也銷毀即可。

?

三、用棧實現隊列

題目鏈接：232. 用棧實現隊列 - 力扣（LeetCode）?

上面我們是使用隊列實現棧，現在這個題目就要求我們使用棧實現隊列啦，那么我們要如何實現呢?

我們的棧是先進后出，隊列是先進先出，那么我們此時就要兩個棧進行配合，實現先進先出的功能，那么我們是否可以和上面隊列實現棧一樣呢？

基本的邏輯是一樣，還是兩個棧之間進行數據的倒，但是我們此時不是輪流進行倒了，我們是指定一個棧專門用來實現先進先出，那么具體是咋樣呢？

我們先將數據入第一個棧，然后我們就保留棧底的元素，然后我們就從棧頂開始出棧到另外一個棧，然后第一個棧就只有棧底的元素了，那么此時再出棧，此時的數據就是這個隊列出隊的數據，然后我們第二個棧，此時的棧底是原來棧頂的元素，那么我們此時就要將第二個棧倒回去，然后再重新進行上面的操作嗎？

其實不用，我們此時就可以直接對第二個棧進行出棧即可，因為此時我們的第二個棧的方向和一開始不同的了。

下面我們舉個例子來理解：

比如我們入第一個棧的順序為1->2->3->4，那么我們執行第一個操作后，我們的第二個棧從棧頂到棧底的順序為2->3->4，那么我們此時就直接按照順序進行出棧，那么就是我們的隊列啦，那么我們的邏輯就是，我們判斷第二個棧是否為空，如果不為空，那么我們就直接出棧，如果為空，那么我們就將專門用來入隊的棧，出棧到第二個棧中。

下面我們來實現一下：

首先我們將我們前面學習的棧的代碼進行拷貝復制一下，然后我們一步一步實現題目的要求。

我們題目第一個函數，要求實現隊列的初始化，我們就在函數中創建一個隊列，然后我們隊列結構體是由兩個棧組成的，然后我們對兩個棧初始化即可，那么我們就調用我們的棧初始化函數即可。

下面就是我們的入隊函數，我們就直接將數據入棧到pushST即可。

出隊我們上面將到了：

下面就是我們的取隊頭元素，其實就將pushST棧的元素移動到popST棧中，那么此時的棧頂的元素就是隊頭的元素了。

下面為判斷當前隊列是否為空，如果隊列為空那么就返回true，如果不為空就返回false。?

然后就是隊列的銷毀，那么我們就直接銷毀棧，然后銷毀這個隊列即可：

四、循環隊列?

題目鏈接：

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

?循環隊列是啥，題目已經講的很清楚啦，那么我們該如何進行循環呢？

我們題目提到我們的循環隊列是一種線性數據結構，那么我們就使用數組進行實現，那么我們創建一個循環隊列結構體，其中包括，一個數組，一個記錄我們隊頭的位置，一個記錄我們的隊尾，一個是我們的數組的有效容量。

然后我們數據的插入就從隊尾的位置插入，數據的刪除就從我們的對頭進行刪除，那么就實現了我們的先進先出。?

然后我們要如何判斷當前隊列是空，還是滿的呢？

空的情況我們很容易想到，就是我們的front==rear的時候，那么我們的隊列就為空的，那么滿的情況呢？我們走一遍循環就知道，當我們的rear走完一遍循環后，我們要對其進行取隊長的余數，然后raer就回到了0的位置，那么此時rear和front其實也還是相等的，那么咋辦呢？

我們可以創建capacity+1個空間，那么我們的隊列滿的情況就是（rear+1）*(capacity+1)==front的時候就為隊列滿的情況。

判斷是否為空：

判斷是否滿：

往循環隊列中插入數據：

?刪除循環隊列的元素：

取隊頭元素：

取隊尾元素，這里我們就要注意，就是我們的rear此時要是在我們的0的位置的時候，那么我們對其-1那么就變成-1了，那么就越界訪問了，所以我們要特殊處理：

?銷毀循環隊列：

?那么整體代碼如下：

?

運行結果：

?