1
\$\begingroup\$

Exercise: Design a Stack

A Stack is a data structure for storing a list of elements in a LIFO (last in, first out) fashion. Design a class called Stack with three methods.

void Push(object obj)
object Pop()
void Clear()

The Push() method stores the given object on top of the stack. We use the “object” type here so we can store any objects inside the stack. Remember the “object” class is the base of all classes in the .NET Framework. So any types can be automatically upcast to the object. Make sure to take into account the scenario that null is passed to this object. We should not store null references in the stack. So if null is passed to this method, you should throw an InvalidOperationException. Remember, when coding every method, you should think of all possibilities and make sure the method behaves properly in all these edge cases. That’s what distinguishes you from an “average” programmer.

The Pop() method removes the object on top of the stack and returns it. Make sure to take into account the scenario that we call the Pop() method on an empty stack. In this case, this method should throw an InvalidOperationException. Remember, your classes should always be in a valid state and used properly. When they are misused, they should throw exceptions. Again, thinking of all these edge cases, separates you from an average programmer. The code written this way will be more robust and with less bugs.

The Clear() method removes all objects from the stack.

We should be able to use this stack class as follows:

var stack = new Stack();

stack.Push(1);
stack.Push(2);
stack.Push(3);

Console.WriteLine(stack.Pop());
Console.WriteLine(stack.Pop());
Console.WriteLine(stack.Pop());

The output of this program will be

3
2
1

This was the task assigned to me. Following is my code.

using System;

namespace Exercise
{
    class Program
    {
        static void Main()
        {
            var stack = new Stack();

            stack.Push(1);
            stack.Push(2);
            stack.Push(3);

            Console.WriteLine(stack.Pop());
            Console.WriteLine(stack.Pop());
            Console.WriteLine(stack.Pop());
        }
    }
}
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace Exercise
{
    internal class Stack : IEnumerable
    {
        private object _object;
        private List<object> list = new List<object>();

        public IEnumerator GetEnumerator()
        {
            while (list.Any())
                yield return Pop();
        }

        internal object Pop()
        {
            if (list.Count == 0)
                throw new InvalidOperationException("Cannot use .Pop() if list count equals 0.");

            _object = list.FirstOrDefault();

            list.RemoveAt(0);

            return _object;
        }

        internal void Push(object obj)
        {
            _object = obj;

            if (_object == null)
                throw new InvalidOperationException("Cannot use .Push() if object is null.");

            list.Insert(0, _object);
        }

        internal void Clear()
        {
            if (list.Count == 0)
                throw new InvalidOperationException("Cannot use .Clear() if list is empty.");

            list.Clear();
        }

        public void Print()
        {
            if (list.Count == 0)
                throw new InvalidOperationException("Stack is empty.");

            foreach (var s in list)
            {
                Console.WriteLine(s);
            }
        }
    }
}

I'm a beginner in C#. Is there anything left to improve on with this that is within the boundaries of what the instructions expect? Any advice or suggestions if anything to teach me something new would be great. Thank you for all the help so far on this site.

\$\endgroup\$
4
\$\begingroup\$

Questions:

  1. Why do you use the class field _object? Does it serve any real purpose that a method-local variable cannot?
  2. Why do you implement IEnumerable?
  3. (only consider this if you have a decent understanding of concurrency issues, and want to practice) How can you make this code thread-safe?

Suggestions:

  1. Several method throw exceptions in unexceptionable scenarios. Why do you blow up if I want to print or clear an empty stack? That's like having the waiter shoot herself if I try to order food right as the kitchen has closed.
  2. When you're done with the exercise, consider making your stack generic. Casting from object is so old-school C#.
  3. Consider improving your error messages. For one, "Cannot use .Pop() if list count equals 0." could be something like: "Cannot pop an element off an empty stack".
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 1. _object = list.FirstOrDefault(); and all other calls. If you know of a way to replace this then by all means explain please? No, I cannot remove the throw exceptions because the lesson requested it. I am questioning whether you read this completely before responding. 2. I did so for the obvious reason, to get Print() to work. If you have a suggestion to how to make it thread safe then enlighten me. I was hoping someone would point stuff out so I could learn something new. \$\endgroup\$ – Milliorn Mar 31 at 23:56
  • 1
    \$\begingroup\$ @Milliorn it seems you didn't understand the observation hidden inside question 1. The vast majority of questions in this answer seem to be rhethorical \$\endgroup\$ – Vogel612 Apr 1 at 0:11
  • \$\begingroup\$ @Vogel612 if that is your opinion then by all means do explain it please. \$\endgroup\$ – Milliorn Apr 1 at 1:46
  • \$\begingroup\$ @Milliorn the lesson requests throwing exception when pushing null and when popping empty stack. There is no indication that Print method should throw for empty stack nor there Is indication that Print method should exist. Also no indication that Clear should throw. Nor there Is indication that stack should be enumerable, nor there Is indication that it should be cleared when enumerated. \$\endgroup\$ – slepic Apr 1 at 6:23
  • \$\begingroup\$ github.com/chrisvasqm/csharp-intermediate @slepic \$\endgroup\$ – Milliorn Apr 1 at 16:08
3
\$\begingroup\$

You have posted several such exercises before, and I have commented on them as well. First let's state the good: you are performing such exercises to improve your C# and .NET skills. But I have noticed a pattern that if someone questions you on why you do some things a certain, you quickly take refuge under the blanket of that's what the exercise states. But you also do things such as Print() all on your own. To me, this seems to be conflicting goals among (1) you want to learn and improve, (2) you want to follow the strict letter of the exercise when it suits you, and (3) when it suits you, you want to diverge from the exercise. This conflict may contribute to frustration others have when attempting to help you.

What caught my eye about your implementation was 2 notable things: (1) you rely heavily upon LINQ, and (2) you perform more expensive Insert(0, item) than to Add(item) to the end of list.

I take issue with Pop() because of FirstOrDefault. Not because it's LINQ, although you do not need to use any LINQ at all in your solution. Rather it's what it means. First off, you check for emptiness that is Count == 0. It would be better, i.e. more direct than for you to take list[0] because that's what the stack expects. FirstorDefault just happens to return the first item for you, but what it really means is iterate over this list and find the first item that matches the predicate (and a null predicate means any item). While it just happens to be that list[0] and FirstOrDefault works for you, they really mean 2 different things to someone reading your code.

Besides those observations, I would add the following remarks:

  • The internal methods really should be public.
  • _object does not need to be a class field or property. It should be local to a method.
  • I see no crime in clearing an empty list. It may be pointless but it's less expensive than throwing an exception for it. The edge case to consider would be if list was null, but it won't be.

  • I would prefer to override ToString() instead of Print().

  • Console writes take a small bit of overhead, so it would be best to avoid repeated calls for every item in the list. You can compose the string once with a fast StringBuilder and then write or return the string once. Whether you write that string to the console or a log file is up to a developer using your stack.

EDIT

In light of @HenrikHansen 's answer about GetEnumerator, I have changed my answer to provide a custom enumerator. I see some discussion between Henrik and @sleptic, so let me add some context.

Microsoft has this to say about Stack.GetEnumerator :

Enumerators can be used to read the data in the collection, but they cannot be used to modify the underlying collection.

Also, out of furthering my own skills and providing a better answer, I borrowed some code from Microsoft's Stack implementation, which uses an array BTW.

With that said, I offer the following modifications with updated code which now includes a better GetEnumerator:

public class StackV1 : IEnumerable
{
    private List<object> list = new List<object>();
    private int _version = 0; // used to keep in-sync with enumerator

    public Enumerator GetEnumerator()
    {
        return new Enumerator(this);
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return new Enumerator(this);
    }

    public object Pop()
    {
        if (list.Count == 0)
        {
            throw new InvalidOperationException("Empty stack.  There is nothing to Pop().");
        }

        // Pop by removing from end of list.
        var index = list.Count - 1;
        var item = list[index];
        list.RemoveAt(index);

        _version++;

        return item;
    }

    public void Push(object item)
    {
        if (item == null)
        {
            throw new InvalidOperationException($"{nameof(item)} is null.  There is nothing to Push().");
        }

        _version++;

        // Push by adding to end of list.
        list.Add(item);
    }

    public void Clear()
    {
        // list will never be null, and it should not be a crime to clear an empty list.
        if (list.Count > 0)
        {
            list.Clear();
            _version++;
        }
    }

    public int Size => list.Count;

    // The original exercise did not require a Print() or ToString() method.
    public override string ToString()
    {
        if (list.Count == 0)
        {
            return "{ empty stack }"; // or perhaps "{ }"
        }

        // Each Console.WriteLine has a tiny cost.  Let's try not even call it, but rather comnpose a string.
        // This honors the OP's order and display.
        var sb = new StringBuilder();
        for (var i = list.Count - 1; i >= 0; i--)
        {
            sb.AppendLine(list[i].ToString());
        }

        return sb.ToString();
    }

    // See https://referencesource.microsoft.com/#System/compmod/system/collections/generic/stack.cs,8865095e0bceeafd
    public struct Enumerator : IEnumerator
    {
        private StackV1 _stack;
        private int _version;
        private int _index;
        private object currentElement;

        internal Enumerator(StackV1 stack)
        {
            _stack = stack;
            _version = stack._version;
            _index = -2;
            currentElement = default(object);
        }

        public void Dispose()
        {
            _index = -1;
        }

        public bool MoveNext()
        {
            bool retval;
            if (_version != _stack._version)
            {
                throw new Exception("Out-of-sync Enumerator due to a modified Stack.");
            }
            if (_index == -2)
            {  // First call to enumerator.
                _index = _stack.Size - 1;
                retval = (_index >= 0);
                if (retval)
                {
                    currentElement = _stack.list[_index];
                }
                return retval;
            }
            if (_index == -1)
            {  // End of enumeration.
                return false;
            }

            retval = (--_index >= 0);
            currentElement = retval ? _stack.list[_index] : default(object);
            return retval;
        }

        public object Current
        {
            get
            {
                if (_index == -2)
                {
                    throw new Exception("Pointer is before top of the stack.");
                }
                if (_index == -1)
                {
                    throw new Exception("Pointer is past the bottom of the stack.");
                }
                return currentElement;
            }
        }

        public void Reset()
        {
            if (_version != _stack._version)
            {
                throw new Exception("Out-of-sync Enumerator due to the Stack being modified externally.");
            }
            _index = -2;
            currentElement = default(object);
        }
    }
}

Your original Print and my ToString list each item on a new line. My personal preference would be to list as a collection like "{ 3, 2, 1 }"

// However my personal option would be to list as "{ 3, 2, 1 }"
sb.Append("{ ");
var first = true;
for (var i = list.Count - 1; i >= 0; i--)
{
    var delimiter = first ? "" : ", ";
    sb.Append($"{delimiter}{list[i]}");
    if (first)
    {
        first = false;
    }
}
sb.Append(" }");

When I first looked at this exercise, I wondered why it was for Intermediates. It seemed too easy. After updating with a customer Enumerator, I can know see why its Intermediate.

The real fun would be to add generics for type-specific lists. However, I see the exercise says that will be covered in an advanced exercise. It's really not that much of a stretch and would be beneficial to the skills you wish to acquire.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Your observations are true. I am trying to figure it out whichever way I can. I added Print() because I wanted a way to see if not only what I was doing was correct, but to learn why I couldn't print Stack` with a foreach``` loop. My intent is not to be confusing, although I can see how I can confuse others an myself. If I rely on LINQ its simply because its what I am familiar with and not what might be what's best tool in my tool box. The expensive functions I use are just familiar/easy for me to find and implement. I ask for advice so I can learn what is optimal. \$\endgroup\$ – Milliorn Apr 2 at 21:05
  • \$\begingroup\$ I have refactored this code. This is the current state of it. link \$\endgroup\$ – Milliorn Apr 2 at 21:07
  • \$\begingroup\$ As for GetEnumerator that implementation I used to get Print to work was me looking through Stack Overflow post to see how to get this done. I was trying to literally get something to print. I had no idea if this was a good idea. At that point I was trying to get anything to work with something I don't quite understand yet. Thank you for posting your suggestions. I am reading them now an trying to figure out what to merge. \$\endgroup\$ – Milliorn Apr 2 at 21:11
  • 1
    \$\begingroup\$ You should not be using LINQ for this. Go for direct code. Do you want to check to see if your stack is empty? The most direct way to do this is check list.Count == 0. Compare that to list.Any() which means enumerate over this collection to see if it has any elements. The Pop() already ensures that no null elements are pushed on the stack, so really checking the Count is the most direct way to determine if the stack is empty or not. \$\endgroup\$ – Rick Davin Apr 2 at 22:01
  • 1
    \$\begingroup\$ @Milliorn Consider if you liked your custom stack so much that you wanted to publish it in a DLL for use within your organization. You would want other consumers of the DLL to see certain things from their own projects, and that's why you would favor public over internal for this particular application. \$\endgroup\$ – Rick Davin Apr 2 at 22:03
2
\$\begingroup\$

One thing the other answers don't address is your implementation of IEnumerable:

    public IEnumerator GetEnumerator()
    {
        while (list.Any())
            yield return Pop();
    }

An iterator is supposed to iterate over all elements in the collection, but it should never ever change the state of the collection. Your implementation actual pops all the items in the stack, so it is empty afterwards.

Using it like:

var stack = new Stack();

stack.Push(1);
stack.Push(2);
stack.Push(3);

foreach (var item in stack)
{
   Console.PrintLine(item);
}

will result in an empty stack, and I don't think that should be the case.

If the top of the stack is the head of the list, you can just return the enumerator from the list:

public IEnumerator GetEnumerator()
{
  return list.GetEnumerator();
}

You could make the private field list readonly to secure, that it is never set to null or anything else:

private readonly List<object> list = new List<object>();

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I would object that Iterator must not change state of the container. I would say it Is uncommon, maybe unintuitive, but not forbidden. If you write it in the doc and maybe give it an expressive name, ie an explicit class DestructiveStackEnumerator... It should be fine for devs who read docs. Also iterating a stack is not necesary to go from top to bottom. Again it may be more intuitive, but not mandatory. \$\endgroup\$ – slepic Apr 2 at 7:14
  • \$\begingroup\$ @slepic: I can only wish you all the best of luck :-) \$\endgroup\$ – Henrik Hansen Apr 2 at 7:26
  • \$\begingroup\$ Im not arguing that it is always good idea. I merely say that your claims are too strong. There sure are usecases where you want to iterate stack bottom to top, and/or in a destructive way. Though they may be much fewer, never say never. There is at least one widely used programming language in which a core stack implementation allows all of this by configuring the stack on instance level. \$\endgroup\$ – slepic Apr 2 at 10:37
  • 1
    \$\begingroup\$ @HenrikHansen One thing the other answers don't address is your implementation of IEnumerable: My implementation is based solely on me searching the web and trying to find something to work. but it should never ever change the state of the collection I had no idea that was the case and yes that is not desirable here. ``` public IEnumerator GetEnumerator() => list.GetEnumerator();``` Add that to my refactor. I really need to learn more about IEnumerable. Also changed list to be readonly. Good catch on that one. Thank you for and everyone else here for your help! \$\endgroup\$ – Milliorn Apr 2 at 21:53
  • 1
    \$\begingroup\$ @Henrik, thanks for the heads up on that. Apparently Microsoft takes a different philosophy on the capabilities of a stack. Fortunately, they also provide ToList(), so I can remain "pure." ;-) \$\endgroup\$ – Aron Apr 7 at 13:54
2
\$\begingroup\$

In reviewing the questions and answers it struck me that one way to simplify things would be to use linked list as the backing data structure instead of a List (which is based on an array). A LinkedList, allows adding and removing from the "head" in O(1) without concern for an index. Sample code is below.

Additional points:

  1. I agree with the others that a generic Stack<T> would be preferable.
  2. I also agree that _object would be better as a local variable.
  3. Rather than writing list.Count == 0 multiple times, I created the HasItems property.
  4. Adding the Top property allows the user to "peek" at the stack without popping.
  5. At first I implemented IEnumerable but upon further consideration I realized that I would say that the nature of a Stack is to push and pop. The argument could be made that adding enumeration to it changes it to a different data structure. This prompted me to remove IEnumerable and add ToList(). Now a user can convert it to an IEnumerable, and work with that however they please. I also added a comment about this to the earlier answer.

Here is the sample code:

using System;
using System.Collections.Generic;
using System.Linq;

public class App_Stack
{
    public void Run()
    {
        var stack = new Stack();
        Enumerable.Range(1, 10).ToList().ForEach(i => stack.Push(i));

        while (stack.HasItems)
        {
            Console.WriteLine(((int)stack.Pop()).ToString());
        }
    }
}

public class Stack 
{
    private LinkedList<object> list = new LinkedList<object>();

    public object Top => list.FirstOrDefault();
    public int Count => list.Count;        
    public bool HasItems => Count > 0;

    public void Push(object item) => list.AddFirst(item);

    ///if stack is empty returns null
    public object Pop()
    {            
        var item = Top;
        if (HasItems)
        {                
            list.RemoveFirst();                
        }
        else
        {
            Console.WriteLine("Stack is empty");
        }

        return item;
    }

    public void Clear() => list.Clear();

    public List<object> ToList() => list.ToList();
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks for your suggestions. I added your suggestion HasItems. Also added the Top property but why not public object Top => list[0];? link to latest code \$\endgroup\$ – Milliorn Apr 7 at 18:05
  • \$\begingroup\$ Hi, you're welcome. The risk with Top => list[0] is that when the list is empty it will throw an exception. \$\endgroup\$ – Aron Apr 7 at 21:26
  • \$\begingroup\$ So either I use that and handle an exception, or pass a null? Trying to make sure I am reading this right? (docs.microsoft.com/en-us/dotnet/api/…) \$\endgroup\$ – Milliorn Apr 7 at 21:55
  • 1
    \$\begingroup\$ Yes, FirstOrDefault() will return list[0] or null. \$\endgroup\$ – Aron Apr 7 at 23:46
  • 1
    \$\begingroup\$ Also for the record, to get the last item in a list you could use list.Last() (or list.LastOrDefault(). \$\endgroup\$ – Aron Apr 8 at 14:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.