3

Suppose we implement a stack using a dynamically allocated array. If the array fills, we are faced with a dilemma. From among the following choices, select the one that best describes our strategy for handling a filled array.

(a) We declare a new array, twice as big as the original, and copy the data into the new space for a total cost of O(n), over a sequence of n pushes.

(b) We declare another array and keep track of which of the two (or more) arrays contain the current top of the stack in a private member of the stack class. This costs us O(1) per push.

(c) For some fixed k, we create a new array of size n + 2^k and copy the data into the new space for an average cost of O(1) per push operation.

(d) We avoid implementing a stack using a dynamically allocated array, because it is inefficient to have to reallocate memory.

(e) None of these answers is a reasonable response.

I'm pretty sure the correct answer is a, but I dont understand why that would be the best one over the others? Are the others even practical? They seem ok to me. For example, c is almost the same thing as `a, no? Why is doubling more advantageous then increasing by a constant amount? What about the other options-why dont they work?

tvanfosson
  • 524,688
  • 99
  • 697
  • 795
Snowman
  • 31,411
  • 46
  • 180
  • 303
  • 1
    Why doubling is more advantageous: http://stackoverflow.com/questions/5232198/why-does-an-stl-vectors-capacity-grow-exponentially/5232342#5232342 – Cubbi Apr 05 '11 at 03:09
  • uh...homeowrk? Take home test? – Alex Apr 05 '11 at 03:09
  • 2
    @Alex - homework is allowed, but the manner of answer is different (at least for me). – tvanfosson Apr 05 '11 at 03:10
  • @tvanfossen Yeah, I know, but homework should be tagged as such IMHO. – Alex Apr 05 '11 at 03:12
  • 1
    @Alex - which I've done. I don't think @bitmoe was attempting to hide it, just didn't tag it that way. – tvanfosson Apr 05 '11 at 03:13
  • 1
    Well its not really homework. Its a question from an old exam I'm reviewing with for my upcoming exam. I already knew the answer was a since we went over it in review but I didnt really catch the reason. I posted it here hoping for clarification. – Snowman Apr 05 '11 at 03:17

2 Answers2

3

Say your stack was 128 elements and you ended up having to store 4096 elements in it. How many times would you have to resize the array when doubling vs. extending it by a constant 128 items each time?

tvanfosson
  • 524,688
  • 99
  • 697
  • 795
1

This looks like homework and possibly a take-home test, so I'll deliberately leave something out of my answers.

a) Attempt to supply proof for the O(n) claim. Compare with your proof for b).

b) How do you store the set of subarrays in use? (It's turtle's all the way down.)

c) Attempt to supply proof for the O(1) assertion. Compare with your proof for a).

d) All alternatives have their own inefficiencies. Compare them. Note that in real-time programming you can't use a dynamically reallocated array, and you must use something like a linked list. Why?

e) If any of the above are reasonable, this is trivially false. And vice versa.

btilly
  • 43,296
  • 3
  • 59
  • 88