怎么创建网站充值和提现账号,云南省建设工程信息网官网,建设项目环保备案登记网站,文章代写栈的特性
栈是一种遵循后进先出#xff08;LIFO#xff09;原则的数据结构。其基本操作包括#xff1a;
push#xff1a;将元素添加到栈顶。pop#xff1a;移除栈顶元素。peek#xff1a;查看栈顶元素#xff0c;但不移除。
栈排序的原理
栈排序的核心是使用两个栈LIFO原则的数据结构。其基本操作包括
push将元素添加到栈顶。pop移除栈顶元素。peek查看栈顶元素但不移除。
栈排序的原理
栈排序的核心是使用两个栈一个原始栈用于输入数据和一个辅助栈用于排序过程。通过这两个栈的相互操作可以实现数据的排序。
排序实现步骤 初始化创建两个栈stk原始栈和 tmpstk辅助栈。 执行排序 当新元素需要加入原始栈 stk 时先比较它与辅助栈 tmpstk 顶部元素的大小。如果辅助栈顶部的元素大于新元素则将辅助栈的元素移动到原始栈直至找到合适的位置为新元素腾出空间。将新元素放入辅助栈。最终辅助栈 tmpstk 中的元素将按排序顺序存放。 完成排序将辅助栈 tmpstk 的元素移回原始栈 stk此时 stk 中的元素依排序顺序排列。
代码实现
1.在将新元素压入栈的时候就进行排序
力扣LeetCode官网 - 全球极客挚爱的技术成长平台
class SortedStack {
private:stackintstk;stackinttmpstk;
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²)不适合用于性能敏感的应用。
