CODEWITHSUNDEEP
c++c++11stacktime-complexity
Tipok
Tipok

Reputation: 695

best complexity swap elements in stack

Sorry for my English. I need to swap some of the elements in the stack. Some elements have the same priorities, and therefore when the activation element. He had to stand on the first place among the elements with the same priority.

enter image description here

And to do this, I first delete an element from the stack, and then insert it again. But it turns out the complexity of O (n * 2). I understand correctly? It can be somehow better?

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

insert element:

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 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 elements:

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

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

So do good or bad?

Upvotes: 0

Views: 236

Answers (1)

Yevhen Kuzmovych
Yevhen Kuzmovych

Reputation: 12140

I think, I understand. And complexity is O(n*3) actually because find(), delete() and insert() are all O(n).

I'd suggest creating new stack in your swap() method:

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

}

This gives you O(n*2) worst case and O(n) on avarage.

Upvotes: 2

Related Questions