наилучшие элементы сворачивания сложности в стеке

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

думаю, я понимаю. И сложность - это 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) в худшем случае и O (N) на насчитайте.