stack with array

We can implement stack with array or linked list. In this page, we will discuss three different approaches to do so.

• 1. with static array

  2. with dynamic array

  3. with dynamic array using template

Dynamic Array

The definition stackArrayD is fairly straightforward. Client can create stackArrayD of any size (default is 100). Only push and pop functions are supported. The list is where we store the dynamic array. Note that we need to have the constructor to create the dynamic storage and initialize the empty stack. We also need the destructor to recycle the storage.

Static Array

The stackArrayS definition is simpler, but it is a fixed size stack. We create MAX_SIZE of array inside our object. Try to do a sizeof comparison between stackArrayS and stackArrayD. Note that the constructor does not create storage, but we still need it to initialize "top". There is no need to have the destructor though. The internal static array will be reclaimed by system when the stackArrayS objects go out of scope.

Dynamic Array with Template implementation

The above two implementations have a common deficiency: it is created for one type of stack element (double in this case). If we need to have a student or stock stack, then we will need to change the code. In most industry applications I know, that's not much an issue. But, academically, template is the solution. The following example implements dynamic stackArray with template.

Note that both definition and implementation code are in the same .h file. Try to compare this code with stackArrayD code above. Are they the same? very much so. Are they different? yes, especially how it is used. Our test code shows all three approaches.

Using stackArray

The main.cpp invokes three different stackArrays: stk, d, s. stk is integer stack, the other two are double stack.

• 1. if we do stackArrayTPT<double>, then stk and d will be identical

  2. other than declarations, all three have identical functions

  3. user can control the size of stk and d, but not s

  4. did you notice that the size of stk and d are the same, but s is a lot bigger. How do you tell? Why?

  5. from debugging's point of view, s is easier to see what's on the stack, right? Every element in list shows up.

Discussions

• • static array vs dynamic array.....It depends on the application environment. Static is certainly easier to implement and debug. But, if the element is huge, it always incurs a copy.

  • if you go for dynamic array... remember the deep copy thing?

  • can I do static template? of course you can. try it.

  • template vs non-template ... that's a bigger question. My opinion is that in real life, I rather use existing standard template library (STL) instead of creating one. There is a very nice stack template in STL.

  • oh, one more thing. Have you tried to separate template code into two files (.h and .cpp) just like what we did with the stackArrayD and stackArrayS? What happens? Can it compile? Why?