スタック内の最も複雑なスワップ要素

Question

私の英語のために申し訳ありません。私はスタック内のいくつかの要素を交換する必要があります。 いくつかの要素は同じ優先順位を持ち、したがって起動要素がある場合。彼は同じ優先順位で要素の中の最初の場所に立つ必要があった。

そして、これを行うには、私が最初にスタックから要素を削除し、再度挿入してください。しかし、O（n * 2）の複雑さが分かります。私は正しく理解していますか？それは何とか良いことができますか？

typedef std::shared_ptr<AdaptedWidget> window_ptr; 
std::stack<window_ptr> m_windowsStack; 

インサート要素：

Insert with sorting by - int priority 
void WindowManager::insertToStack(window_ptr window) 
{ 
    if (!m_windowsStack.empty() && window->priority() <= m_windowsStack.top()->priority()) 
    { 
     auto top = m_windowsStack.top(); 
     m_windowsStack.pop(); 
     insertToStack(window); 
     m_windowsStack.push(top); 
    } 
    else 
    { 
     m_windowsStack.push(window); 
    } 
} 

削除エレメント：

void WindowManager::deleteWindow(std::string title) 
{ 
    if (!m_windowsStack.empty()) 
    { 
     auto top = m_windowsStack.top(); 

     if(top->windowTitle().toStdString() != title) 
     { 
      m_windowsStack.pop(); 
      deleteWindow(title); 
     } 
     else 
     { 
      m_windowsStack.pop(); 
      return; 
     } 
     m_windowsStack.push(top); 
    } 
} 

スワップエレメント：

void WindowManager::swapWindowSamePriority(std::string title) 
{ 
    auto window = findWindow(title); 

    if(window) 
    { 
     deleteWindow(title); 
     insertToStack(window); 
    } 
} 

いいですか悪いですか？

Answer 1

と思いますが、わかりました。 find(),delete()およびinsert()はすべてO（n）なので、複雑さはO（n * 3）です。

私はあなたのswap()方法で新しいスタックを作成することをお勧めしたい：

// example stack: 
// 1->1->2->*2*->2->2->3->3->4->5 
//   ^
//  element to move (swap) 
void WindowManager::swapWindowSamePriority(std::string title) 
{ 
    if (m_windowsStack.empty()) return; 

    std::stack<window_ptr> tempStack; // temporary stack 
    while(title != m_windowsStack.top()->windowTitle().toStdString()) 
     // searching for needed element and moving element to tempStack 
     tempStack.push(m_windowsStack.pop()); 

    auto window = m_windowsStack.pop(); // found window. 

    // m_windowsStack: 1->1->2 
    // window: *2* 
    // tempStack: 5->4->3->3->2->2 

    // at this moment in m_windowsStack you have elements that were before window 
    // and in tempStack - elements that were after it. 

    while(tempStack.top()->priority() == window->priority()) 
     // pushing back elements from tempStack to m_windowsStack while thay have same priority as found window 
     m_windowsStack.push(tempStack.pop()) 


    // m_windowsStack: 1->1->2->2->2 
    // window: *2* 
    // tempStack: 5->4->3->3 

    // at this moment we have moved all elements with the same priority as found window to m_windowsStack. 

    m_windowsStack.push(window) // pushing found window on top of elements with the same priority 

    // m_windowsStack: 1->1->2->2->2->*2* <-- that we needed 
    // tempStack: 5->4->3->3 

    while(!tempStack.empty()) 
     // moving remaining elements from tempStack to m_windowsStack 
     m_windowsStack.push(tempStack.pop()) 

    // m_windowsStack: 1->1->2->2->2->*2*->3->3->4->5 
    // tempStack: empty 

} 

これは、あなたはO（n * 2）avarage上最悪のケースとO（n）を提供します。