面試100 兩個棧實現一個隊列

18兩個棧實現一個隊列

一問題描述

兩個棧實現一個隊列的操作
appendTail

將要插入的元素push進s1。注意此處不需要，再把s2中的元素導入到s1了，因為s1和s2兩者的順序是相反的。

deleteHead
如果s2中的元素不為空，則直接彈出棧頂
若為空，則需要把s1中的元素依次push進s2中，并刪除s2中的棧頂

綜上
可以直接插入s1中元素，刪除時，若是s2為空，則需要把s1中的元素插入進s2中，然后對s2實行刪除操作。

二代碼如下

#include <iostream>

#include <stack>

#include <assert.h>

using namespace std ;

template <class T>

class CQueue

{

public :

CQueue() {}

~CQueue() {}

void appendTail(const T & node) ;

void deleteHead() ;

private :

stack <T> m_stack1 ;

stack <T> m_stack2 ;

} ;

template <class T>

void CQueue<T>::appendTail(const T & node) //添加尾部

{

m_stack1.push(node) ;

}

template <class T>

void CQueue<T>::deleteHead() //刪除頭部

{

if(!m_stack2.empty())

{

cout<<m_stack2.top()<<endl ;

m_stack2.pop() ;

}

else

{

assert(!m_stack1.empty()) ; //兩個棧都為空，則出現異常錯誤

while(!m_stack1.empty()) //將s1中的元素全部push進s2,最后在s2中=刪除棧頂

{

m_stack2.push(m_stack1.top()) ;

m_stack1.pop() ;

}

int main()

{

CQueue<int> queue ;

/* queue.appendTail(5) ;

queue.appendTail(4) ;

queue.appendTail(3) ;

queue.deleteHead() ;

queue.appendTail(2);

queue.appendTail(1);

queue.deleteHead() ;

system("pause") ;

return 0 ;

}

posted on 2011-05-18 10:16 kahn 閱讀(579) 評論(0) 編輯收藏引用所屬分類: 算法相關

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: 9-24MTK一面二面微軟筆試總結 2011-09-07xx移動創業公司筆試題編程之美2.7 最大公約數 O(n)實現刪除兩個數組中的共同元素編程之美1.9(二) 高效率地安排會面分組背包問題（六）二維背包問題（五）多重背包（三）完全背包問題 <二>

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

jake1036

My Links

Blog Stats

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜

面試100 兩個棧實現一個隊列

18兩個棧實現一個隊列