How do you make your own implementation of stack w/out using built in stack

erm87

New member
Joined
Mar 14, 2018
Messages
2
Programming Experience
Beginner
Hello there!

I am a beginner currently taking a diploma course in computer science.

One of our exercises is to make a simple console program using stack .

The instruction notes:

Create the stack using your own implementation of arrays. Do not make use of the built in Stack for this. Also do not make use of the built in Arrays class.

And I am not quite sure what is meant by not using the built in stacks and arrays.

I would appreciate your comments and inputs.

Thanks and have a good day!
 

jmcilhinney

C# Forum Moderator
Staff member
Joined
Apr 23, 2011
Messages
3,813
Location
Sydney, Australia
Programming Experience
10+
A stack is a LIFO data structure, i.e. the last data to go in is the first data to come out. That is in contrast to a queue, which is FIFO, i.e. the first data to go in is the first data to come out. The standard operations for a stack are push (add data) and pop (remove data). You need to define a class with Push and Pop methods, where Push will accept a data item and add it to the top of the stack and Pop will remove the item at the top of the stack and return it. Internally, you would store the data in an array. How you manage that array is the point of the exercise. The two main options that come to mind are:

1. Each time an item is pushed onto the stack, create a new array that is one element larger than the existing array and copy all the existing elements across, then assign the new item to the last element. Each time an item is popped off the stack, do the inverse.
2. Do basically as for 1 but, instead of resizing every time, use an array that is initially larger than you need and store the index of the last element in use in a variable, then add more than one element to the array when you resize. As items are popped, you don't necessarily need to resize at all.

The collection classes in the .NET Framework use the second option. For instance, the List<T> class maintains an internal array that has (I believe) four elements by default. Each time an item is added that exceeds the size of the array, that size is doubled. The internal array is never resized down implicitly, but the class has a method to do it explicitly. I imagine that the Stack<T> works in much the same way.

Also note that the array resizing can be done more simply using the Array.Resize method, but that bolded text indicates that you cannot use that.
 
Top Bottom