beste Komplexität Swap-Elemente im Stapel

Question

Entschuldigung für mein Englisch. Ich muss einige der Elemente im Stapel tauschen. Einige Elemente haben die gleichen Prioritäten und daher das Aktivierungselement. Er musste auf dem ersten Platz unter den Elementen mit der gleichen Priorität stehen.

Und dies zu tun, ich zum ersten Mal ein Element aus dem Stapel löschen und es dann wieder ein. Aber es stellt sich die Komplexität von O (n * 2) heraus. Ich verstehe korrekt? Es kann irgendwie besser sein?

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

Einsatzelement:

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

löschen Element:

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

Swap-Elemente:

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

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

Also gut oder schlecht?

Answer 1

Ich denke, ich verstehe. Und die Komplexität ist tatsächlich 0 (n * 3), weil find(), und insert() alle O (n) sind.

würde ich neuen Stack in Ihrem swap() Verfahren zu schaffen vorschlagen:

// 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 

} 

Dies gibt Sie O (n * 2) im schlechtesten Fall und O (n) auf durchschnittlich.