堆棧中最佳複雜性交換元素

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); 
    } 
} 

delete元素：

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

我想我明白了。實際上覆雜度爲O（n * 3），因爲find(),delete()和insert()都是O（n）。

我建議你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）。