The most efficient way of Implementing given Stack

I have a Stack specification in mind which ---> * Can look at the object which has the highest(or lowest or so) value. * Every object on stack will be Comparable.

I would want to implement the following operations as quickly as possible

1. void push(E e);

2. void pop(E e);

3. E peekMidElement(); [size()/2)+1]

4. E peekHighestElement();

5. E peekLowestElement();

6. int size();

Efficiency has to be the center. What wo开发者_如何学编程uld be the recommended way? Ideas are welcome.

EDIT: All methods to be called as often. Moreover its the Time Effeciency that matters.

---

One of the way can be to implement the stack using an array. However this does impose a limit on the number of elements there can be in the stack (i.e. maximum size of the array is limited). Also you may needto allocate the space for the array (you can do some realloc magic to re-increase the size of the array if it is growing more)

The advantage of array implementation is that ... you will have to keep track of one variable which will be the top of the stack. And the peek middle is just a index into the array.

Hope this helps

Push: the top variable indicated the index into the array where the top element is ... when doing a push ... just store the value at the next element after top (of course after doing limit checks) .. and then you can increment the value of top

Pop: decrement top ... return the value at the (top + 1)

PeekMiddle: It will always be the array[top / 2]

PeekHighest: It will always be array[top]

PeekMiddle: It will always be array[0]

Size: return top

All of the above operation are O(1)

---

"Efficiency" is too general, especially in the face of 6 methods? CPU efficiency? Memory footprint? Is each function called the same number of times? How big is the stack on average?

In the total abstract, I would say that a singly-linked list would be a good idea, assuming (as seems plausible) that size and peekMidElement aren't often called.

---

If you know a good upper bound on stack size, using an array (as outlined in another answer) may be a reasonable thing to do. All six operations are O(1) and, if the stack often operates near its maximum size, storage per element is optimal.

On the other hand, if you don't know an upper bound on stack size, or if stack size usually will be small compared to the upper bound, then use a doubly-linked list, as described below. Again, all six operations are O(1). Storage per element is optimal if the stack operates near minimum size -- you won't have lots of unused array space sitting around. Note, memory allocation shown below as "new" and "free" can consist of malloc() and free() calls, or can be some common method for limiting overhead by using a pool of available nodes.

Let H point at head of list, T at tail, and M at middle. (M can be maintained in time O(1) per change, as below.) Initialize list size s=0 and mid-count m=0.

For your operations 1-6:

1. void push(E e):
   Make new node X with value e; ++s; if (s==1) set H=T=M=X and set links, else { attach X at H; set H=X; if m<(s/2+1) then { ++m and set M = M.next}}.

2. void pop(E e): if s<1 return null or error; else { get value e=H.e to return, set H=H.next, unlink and free H.prev, --s, if (s==0) H=T=M=null else if m>(s/2+1) then { --m and set M = M.prev}}.

3. E peekMidElement(); [size()/2)+1]: if M, return M.e else null

4. E peekHighestElement(): if H, return H.e (or T.e?) else null

5. E peekLowestElement(): if T, return T.e (or H.e?) else null

6. int size(): Return s

I don't know which end of the stack is "High"; do you see it as growing up, or growing down? Anyway, just fix ops 4 & 5 as you like, and change to names like peekHeadElement or peekFirstElement, etc.

---

An array implementation would be ideal in this scenario, though I am not sure if your description could still be called a stack. Some points to note while implementing it are as follows:

1. Push on the right end of the array. If you exceed the array capacity, you can allocate a new array, copy all the elements and delete the previous allocation. All this is automatically taken care of by some array-based container classes in most languages. However, there are ways to avoid most of this copying while expanding your stack's capacity which may involve loss of efficiency on some other operation.

2. If you maintain an index to mark the next insertion (i.e. push(E e)), pop() can be implemented as simple as "--;".

3. peekMiddle() would just be the element on (size/2)th index. I hope you are not looking for the median value instead.

4. For peekLowest(), simple solution would be to maintain a stack of minimums, i.e. when you push a value onto the stack, if it is the new minimum, push it onto the stack of minimums as well. This way, the topmost value on your stack of minimums will be the answer to peekLowest(). Of course, when you pop a value from the original stack, if it is the minimum value (as given by peekLowest()) pop it from the stack of minimums as well. A similar approach can be used for peekHighest().

With this simple implementation, you should be able to get O(1) running time for all the operations. For push(E e), O(1) is the amortised running time.