C++使用一個棧實現(xiàn)另一個棧的排序算法示例
更新時間：2017年05月10日 08:53:02 作者：難免有錯_
這篇文章主要介紹了C++使用一個棧實現(xiàn)另一個棧的排序算法,結合實例形式分析了C++借助輔助棧實現(xiàn)棧排序算法的相關操作技巧,需要的朋友可以參考下
本文實例講述了C++用一個棧實現(xiàn)另一個棧的排序算法。分享給大家供大家參考，具體如下：
題目：
一個棧中元素類型為整型，現(xiàn)在想將該棧從頂?shù)降装磸男〉酱蟮捻樞蚺判?，只許申請一個輔助棧。
除此之外，可以申請新的變量，但不能申請額外的數(shù)據(jù)結構。如何完成排序？
算法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++程序設計有所幫助。
相關文章
淺談C語言中strcpy,strcmp,strlen,strcat函數(shù)原型
下面小編就為大家?guī)硪黄獪\談C語言中strcpy,strcmp,strlen,strcat函數(shù)原型。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-04-04
匯編語言中有一種移位指令叫做循環(huán)左移（ROL）,下面這篇文章主要給大家介紹了關于C語言字符串左旋的兩種實現(xiàn)方法,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下2023-02-02
這篇文章主要為大家詳細介紹了C語言實現(xiàn)十六進制轉換為十進制的方法，文中的示例代碼講解詳細，具有一定的借鑒價值，需要的可以參考一下2022-11-11
這篇文章主要為大家詳細介紹了C語言鏈表實現(xiàn)學生管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-06-06
在Qt中使用QChart類可以快速繪制一個圖表出來,比如折線圖、餅圖、柱狀圖等,本文就來為大家介紹一下如何利用QChart繪制簡單的面積圖吧2024-11-11
棧和隊列，嚴格意義上來說，也屬于線性表，因為它們也都用于存儲邏輯關系為 "一對一" 的數(shù)據(jù)，但由于它們比較特殊，因此將其單獨作為一章，做重點講解2022-04-04
這篇文章主要介紹了深入解析C++編程中類的封裝特性,是C++入門學習中的基礎知識,需要的朋友可以參考下2015-09-09
這篇文章主要介紹了C++編程中的友元函數(shù)和友元類,屬于較為冷僻的知識,在實際開發(fā)中較少使用,需要的朋友可以參考下2015-09-09
這篇我要講的是如何使用c++11改進命令模式，感興趣的朋友可以看下2013-11-11
C語言中的內聯(lián)函數(shù)(inline)與宏定義(#define)詳細解析
內聯(lián)函數(shù)與宏本質上是兩個不同的概念如果程序編寫者對于既要求快速，又要求可讀的情況下，則應該將函數(shù)冠以inline2013-09-09