如何通过栈实现另一个栈的排序功能示例？

本文共计1064个文字，预计阅读时间需要5分钟。

题目：使用C++实现栈的排序算法

简述：本文通过一个具体的实例讲述了如何使用C++中的一个栈来实现另一个栈的排序。以下为详细内容：

1. 问题背景： - 我们有一个栈，其元素类型为整型。 - 现在需要将这个栈中的元素从小到大排序。

2. 解决方案： - 使用一个辅助栈来实现排序。 - 具体步骤如下：

a. 创建一个辅助栈。

b. 从原栈中逐个取出元素，并与辅助栈顶元素比较。

c. 如果辅助栈为空，或者当前元素小于辅助栈顶元素，则将当前元素压入辅助栈。

d. 如果当前元素大于辅助栈顶元素，则将辅助栈中的所有元素依次弹出，并压入原栈，直到找到比当前元素小的元素，然后将当前元素压入辅助栈。

e. 重复步骤b-d，直到原栈为空。

f. 将辅助栈中的元素依次弹出，并压入原栈，完成排序。

3. 代码示例：

cpp#include #include

void sortStack(std::stack& s1, std::stack& s2) { while (!s1.empty()) { int temp=s1.top(); s1.pop(); while (!s2.empty() && s2.top() > temp) { s1.push(s2.top()); s2.pop(); } s2.push(temp); }}

int main() { std::stack s1={5, 2, 9, 1, 5, 6}; std::stack s2;

sortStack(s1, s2);

while (!s2.empty()) { std::cout <

return 0;}

4. 总结： - 通过使用辅助栈，我们可以实现栈的排序。 - 这种方法简单且易于理解，适合初学者学习。

本文实例讲述了C++用一个栈实现另一个栈的排序算法。分享给大家供大家参考，具体如下：

题目：

一个栈中元素类型为整型，现在想将该栈从顶到底按从小到大的顺序排序，只许申请一个辅助栈。

除此之外，可以申请新的变量，但不能申请额外的数据结构。如何完成排序？

算法C++代码：

class Solution { public: //借助一个临时栈排序源栈 static void sortStackByStack(stack<int>& s) { stack<int>* sTemp = new stack<int>; while (!s.empty()) { int cur = s.top(); s.pop(); //当源栈中栈顶元素大于临时栈栈顶元素时，将临时栈中栈顶元素放回源栈 //保证临时栈中元素自底向上从大到小 while (!sTemp->empty() && cur > sTemp->top()) { int temp = sTemp->top(); sTemp->pop(); s.push(temp); } sTemp->push(cur); } //将临时栈中的元素从栈顶依次放入源栈中 while (!sTemp->empty()) { int x = sTemp->top(); sTemp->pop(); s.push(x); } } };

测试用例程序：

#include <iostream> #include <stack> using namespace std; class Solution { public: //借助一个临时栈排序源栈 static void sortStackByStack(stack<int>& s) { stack<int>* sTemp = new stack<int>; while (!s.empty()) { int cur = s.top(); s.pop(); //当源栈中栈顶元素大于临时栈栈顶元素时，将临时栈中栈顶元素放回源栈 //保证临时栈中元素自底向上从大到小 while (!sTemp->empty() && cur > sTemp->top()) { int temp = sTemp->top(); sTemp->pop(); s.push(temp); } sTemp->push(cur); } //将临时栈中的元素从栈顶依次放入源栈中 while (!sTemp->empty()) { int x = sTemp->top(); sTemp->pop(); s.push(x); } } }; void printStack(stack<int> s) { while (!s.empty()) { cout << s.top() << " "; s.pop(); } cout << endl; } int main() { stack<int>* s = new stack<int>; s->push(5); s->push(7); s->push(6); s->push(8); s->push(4); s->push(9); s->push(2); cout << "排序前的栈：" << endl; printStack(*s); Solution::sortStackByStack(*s); cout << "排序后的栈：" << endl; printStack(*s); system("pasue"); }

运行结果：

排序前的栈： 2 9 4 8 6 7 5 排序后的栈： 9 8 7 6 5 4 2

希望本文所述对大家C++程序设计有所帮助。