棧的特性

棧是一種遵循后進先出（LIFO）原則的數據結構。其基本操作包括：

• push：將元素添加到棧頂。
• pop：移除棧頂元素。
• peek：查看棧頂元素，但不移除。

棧排序的原理

棧排序的核心是使用兩個棧：一個原始棧（用于輸入數據）和一個輔助棧（用于排序過程）。通過這兩個棧的相互操作，可以實現數據的排序。

排序實現步驟

1. 初始化：創建兩個棧，stk（原始棧）和 tmpstk（輔助棧）。

2. 執行排序：

   • 當新元素需要加入原始棧 stk 時，先比較它與輔助棧 tmpstk 頂部元素的大小。
   • 如果輔助棧頂部的元素大于新元素，則將輔助棧的元素移動到原始棧，直至找到合適的位置為新元素騰出空間。
   • 將新元素放入輔助棧。
   • 最終，輔助棧 tmpstk 中的元素將按排序順序存放。

3. 完成排序：將輔助棧 tmpstk 的元素移回原始棧 stk，此時 stk 中的元素依排序順序排列。

代碼實現

1.在將新元素壓入棧的時候就進行排序

力扣（LeetCode）官網 - 全球極客摯愛的技術成長平臺

class SortedStack {
private:stack<int>stk;stack<int>tmpstk;
public:SortedStack() {}void push(int val) {// 將stk中小于val的元素移到tmpstkwhile (!stk.empty() && stk.top() < val) {tmpstk.push(stk.top());stk.pop();}// 將新元素val壓入stkstk.push(val);// 將tmpstk的元素回填到stk，保持stk的排序while (!tmpstk.empty()) {stk.push(tmpstk.top());tmpstk.pop();}}void pop() {if(!stk.empty())stk.pop();return;}int peek() {if(!stk.empty())return stk.top();return -1;}bool isEmpty() {return stk.empty();}
};

此代碼段展示了棧排序的具體實現。push 函數中的邏輯確保了每次插入新元素后，stk 都會按排序順序重新排列。

2.對一個已經壓入所有元素的棧的排序

while (!st.is_empty()) {int tmp = st.get_top(); st.pop();while (!tmpst.is_empty() && tmp <tmpst.get_top()) {st.push(tmpst.get_top());tmpst.pop();}tmpst.push(tmp);}while (!tmpst.is_empty() {st.push(tmpst.get_top());tmpst.pop();}

代碼解釋

1. 第一個 while 循環：該循環負責進行排序。

   • while (!st.is_empty())：當主棧 st 不為空時，執行循環體。
   • int tmp = st.get_top(); st.pop();：取出 st 棧頂元素并存儲在 tmp 中，然后將該元素從 st 彈出。
   • while (!tmpst.is_empty() && tmp < tmpst.get_top())：如果輔助棧 tmpst 不為空且 tmp 小于 tmpst 的棧頂元素，則執行內部循環。
     • st.push(tmpst.get_top());：將 tmpst 的棧頂元素移回 st。
     • tmpst.pop();：從 tmpst 彈出棧頂元素。
   • tmpst.push(tmp);：將 tmp 壓入 tmpst。

2. 第二個 while 循環：該循環將排序后的元素從 tmpst 移回 st。

   • while (!tmpst.is_empty())：當輔助棧 tmpst 不為空時，執行循環體。
   • st.push(tmpst.get_top());：將 tmpst 的棧頂元素壓入 st。
   • tmpst.pop();：從 tmpst 彈出棧頂元素。
3. 模擬過程

st: [4, 2, 3, 1] (棧頂是 1)
tmpst: []第一步：處理元素 1
從 st 彈出 1 (tmp = 1)。
tmpst 是空的，所以直接將 1 壓入 tmpst。st: [4, 2, 3] (棧頂是 3)
tmpst: [1]第二步：處理元素 3
從 st 彈出 3 (tmp = 3)。
tmpst 的棧頂元素 1 小于 3，所以不需要移動元素，直接將 3 壓入 tmpst。st: [4, 2] (棧頂是 2)
tmpst: [3, 1]第三步：處理元素 2
從 st 彈出 2 (tmp = 2)。
tmpst 的棧頂元素 3 大于 2，所以將 3 移回 st。現在 tmpst 的棧頂元素 1 小于 2，直接將 2 壓入 tmpst。st: [4, 3] (棧頂是 3)
tmpst: [2, 1]第四步：處理元素 3
從 st 彈出 3 (tmp = 3)。
tmpst 的棧頂元素 2 小于 3，不需要移動元素，直接將 3 壓入 tmpst。st: [4] (棧頂是 4)
tmpst: [3, 2, 1]第五步：處理元素 4
從 st 彈出 4 (tmp = 4)。
tmpst 的棧頂元素 3 小于 4，所以直接將 4 壓入 tmpst。st: []
tmpst: [4, 3, 2, 1]完成排序
將 tmpst 中的元素按順序移回 st，得到排序后的棧。
st: [1, 2, 3, 4] (棧頂是 4)
tmpst: []

優勢和局限性

• 優勢：棧排序提供了一種直觀理解排序邏輯的方法，同時也是對棧操作的良好練習。
• 局限性：棧排序的效率相對較低，特別是在處理大量數據時。它的時間復雜度為 O(n2)，不適合用于性能敏感的應用。