数据结构——栈与栈排序

栈的特性

栈是一种遵循后进先出（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的元素移到tmpstk
    while (!stk.empty() && stk.top() < val) {
        tmpstk.push(stk.top());
        stk.pop();
    }

    // 将新元素val压入stk
    stk.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(n²)，不适合用于性能敏感的应用。