Designing a data structure acts like improved stack

Question

I have been asked to design a data structure which will act like a stack, not limited in size, which will support the following methods, with given run-time restrictions.

push(s) - push s to the data structure - O(1)
pop() - remove and return the last element inserted O(1)
middle() - return the element (without removing) with index n/2 by insertion order where n is the current amount of elements in the data structure. - O(1)
peekAt(k) - return the kth element by insertion order (the bottom of the stack is k=1) - O(log(k))

I thought of using linked list, and always keep a pointer to the middle element, but then I had problem with implemnting peekAt(k). any ideas how can I implement this?

Answer 1

If the O(1) restriction can be relaxed to amortized O(1), a typical variable-length array implementation will do. When you allocate space for the array of current length N, reserve say N extra space at the end. Once you grow beyond this border, reallocate with the new size following the same strategy, copy the old contents there and free the old memory. Of course, you will have to maintain both the allocated and the actual length of your stack. The operations middle and peekAt can be done trivially in O(1).

Conversely, you may also shrink the array if it occupies less than 1/4 of the allocated space if the need arises.

All operations will be amortized O(1). The precise meaning of this is that for any K stack operations since the start, you will have to execute O(K) instructions in total. In particular, the number of reallocations after N pushes will be O(log(N)), and the total amount of elements copied due to reallocation will be no more than 1 + 2 + 4 + 8 ... + N <= 2N = O(N).

---

This can be done asymptotically better, requiring non-amortized O(1) for each operation, provided that the memory manager's allocate and free perform in O(1) for any size. The basic idea is to maintain the currently allocated stack and the 2x bigger future stack, and to start preparing the bigger copy in advance. Each time you push a value onto the present stack, copy two more elements into the future stack. When the present stack is full, all of its elements will be already copied into the future stack. After that, discard the present stack, declare that the future stack is now the present stack, and allocate a new future stack (currently empty, but allocated 2x bigger than the current one).

If you also need shrinking, you can maintain a smaller copy in a similar fashion when your stack occupies between 1/2 and 1/4 of the allocated space.

As you can see by the description, while this may be theoretically better, it is generally slower since it has to maintain two copies of the stack instead of one. However, this approach can be useful if you have a strict realtime O(1) requirement for each operation.

Answer 2

The implementation using a doubly linked list makes sense to me. Push and Pop would be implemented as it is usually done for a stack; The access to the 'middle' element would be done with an additional reference which would be updated on Push and Pop, depending on whether the number of contained elements would change from even to odd or vice versa. The peekAt Operation could be done using binary search.