The introduction of the extract in O (1)

Question

Possible duplicate:
Implement a queue in which push_rear (), pop_front () and get_min () are all constant-time operations.

I need to implement a FIFO data structure in which the amortized cost of Enqueue, Dequeue and Extract-Min is O (1).

I thought about using a regular queue that would have O (1) enqueue and dequeue using linked lists and then for Extract-Min. I would go through the array to get min and delete it. it will cost O (n), and this will not lead to depreciation of the cost of O (1).

Any help or tips would be appreciated.

Answer 1

, node . Enqueue() , :

void enqueue( data_t val )
{
  back->m_data = val; // back is a pointer to the end of the queue.

  // m_Min should be initialized with a large value.
  if (back->m_data <= m_Min->m_data)
  {
    m_Min = back;
  }
  else // => back->m_data > m_Min->m_data
  {
    swap(back->m_data, m_Min->m_data);
    m_Min = back;
  }
}

, , dequeue extract_min O (1).

data_t dequeue( )
{
  data_t front_data = front->m_data;

  prev_front = front;
  front = front->next;

  dump prev_front;
  return front_data;
}

, front m_Min, , .

data_t min()
{
  return m_Min->m_data;
}

EDIT:. if-block enqueue() . enqueue() . node, min ( node ).

, 5, 3, 7, 1, 4, 6, 8.

1.
front -> 5 <- back
         ^min

2.
front -> 5 3 <- back.
         ^min

front -> 5 3 <- back.
           ^min

3.
front -> 5 3 7 <- back
           ^min

front -> 5 7 3 <- back
             ^min

4.
front -> 5 7 3 1 <- back
             ^min

front -> 5 7 3 1 <- back
               ^min

5.
front -> 5 7 3 1 4 <- back
               ^min

front -> 5 7 3 4 1 <- back
                 ^min

6.
front -> 5 7 3 4 1 6 <- back
                 ^min

front -> 5 7 3 4 6 1 <- back
                   ^min

7.
front -> 5 7 3 4 6 1 8 <- back
                   ^min

front -> 5 7 3 4 6 8 1 <- back
                     ^min

, 3 , :

front -> 4 6 8 1 <- back
               ^min

, , front min, , min.

Answer 2

.

dequeue, en-Queue de-Queue O (1). . , , deq.push_back() stack.push(); :

Enqueue: , , , , . O (1)
Dequeue: dequeue, , , , dequed , , . O (1).
Extract-Min: , . O (1)