娄底网站建设79ldgoogle收录查询
栈的特性
栈是一种遵循后进先出（LIFO）原则的数据结构。其基本操作包括：
push：将元素添加到栈顶。pop：移除栈顶元素。peek：查看栈顶元素，但不移除。
栈排序的原理
栈排序的核心是使用两个栈：一个原始栈（用于输入数据）和一个辅助栈（用于排序过程）。通过这两个栈的相互操作，可以实现数据的排序。
排序实现步骤
-
初始化：创建两个栈，
stk（原始栈）和tmpstk（辅助栈）。 -
执行排序：
- 当新元素需要加入原始栈
stk时，先比较它与辅助栈tmpstk顶部元素的大小。 - 如果辅助栈顶部的元素大于新元素，则将辅助栈的元素移动到原始栈，直至找到合适的位置为新元素腾出空间。
- 将新元素放入辅助栈。
- 最终，辅助栈
tmpstk中的元素将按排序顺序存放。
- 当新元素需要加入原始栈
-
完成排序：将辅助栈
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();}代码解释
-
第一个 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。
-
第二个 while 循环：该循环将排序后的元素从
tmpst移回st。while (!tmpst.is_empty())：当辅助栈tmpst不为空时，执行循环体。st.push(tmpst.get_top());：将tmpst的栈顶元素压入st。tmpst.pop();：从tmpst弹出栈顶元素。
- 模拟过程
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²)，不适合用于性能敏感的应用。