Transfer linked stack to array to sort and vice versa

Question

I have a linked stack BookStack which contains Nodes Book.I need to put the nodes in an Array to be sorted then put back again to stack. Additionally how could I sort alphabetically in C#? How could I implement it?

class Book
{
    private string title, author;
    private int ISBN;

    public Book(string a, string b, int c)
    {
        title = a;
        author = b;
        ISBN = c;
    }

    public string GetAuthor()
    {
        return author;
    }

    public string GetTitle()
    {
        return title;
    }

    public int GetISBN()
    {
        return ISBN;
    }
}

class NodeStack
{
    Node top;
    int count;

    public void Push(object o)
    {
        Node newTop = new Node();
        newTop.setValue(o);
        newTop.setNext(top);

        top = newTop;
        count++;

    }

    public object Pop()
    {
        object value = top.getValue();
        top = top.getNext();
        return value;
    }

    public object Peek()
    {
        return top.getValue();
    }

    public void Clear()
    {
        top = null;
        count = 0;
    }

    public int Count()
    {
        return count;
    }
}

Can't think of anything other than toArray(); but it won't work here

Is your goal to transfer to array and back, or to sort? Sorting can be done with a linked list (formally, the name for the data structure your stack uses is "singly linked list"), it doesn't require an array at all. — Ben Voigt, May 14 '17 at 21:45
Is there a reason why you are not using [`Stack`](https://msdn.microsoft.com/en-us/library/3278tedw.aspx) C# datatype? — Federico Dipuma, May 14 '17 at 21:47
This is similar to a linked list only in items are appended in reverse order. You can use merge sort. Check this article. You can apply same logic. http://www.geeksforgeeks.org/merge-sort-for-linked-list/ — Pratik Gaikwad, May 14 '17 at 21:47
@FedericoDipuma: Or since he wants to remove items in sort order instead of reverse insertion order, something like `SortedList` — Ben Voigt, May 14 '17 at 21:48
I think you need to rethink your design. Why are you not using so many of the available .net collections? What are you trying to achieve with `NodeStack` class? — CodingYoshi, May 14 '17 at 21:49
Pop each item of of the stack into a `List` (since it's easier to add to a `List`), create a descending-order query using Linq's `OrderBy`, then iterate and push the books back onto the stack. If you have _specific_ questions on how to do that then give it a try and show where you are stuck, otherwise the question is too broad. — D Stanley, May 14 '17 at 21:50
@DStanley: There's a [`Sort`](https://msdn.microsoft.com/en-us/library/3da4abas(v=vs.110).aspx) method directly on `List`, no need for slow (polymorphic) `OrderBy`. — Ben Voigt, May 14 '17 at 21:54
@BenVoigt What makes you say that iterating in a specific order is significantly slower that rearranging the items and _then_ iterating? — D Stanley, May 14 '17 at 21:55
@DStanley: Access through a enumerator (forward-only iterator) is definitely slower than indexed access. There's probably a version of `OrderBy` that notices that the object implements `IList` and uses indexing, but there's overhead in detecting that, there's overhead in building up a copy instead of sorting in-place, and access through `IList` is slower than non-virtual calls to `List`. — Ben Voigt, May 14 '17 at 21:57
I have to use a dynamic implementation for the Node Stack and Queue classes. I want to put them in an array because I have to implement a heap sort — Kevin, May 14 '17 at 22:13
@Kevin: Then use a `List`, D Stanley already mentioned how to transfer data between stack and list. And then run your heap sort on the list (it has random access like an array, we aren't talking about `LinkedList`) — Ben Voigt, May 14 '17 at 22:17
@Kevin. Those are important details to add to your question, but they make it obvious that it is a homework problem. What _specifically_ are you stuck on? The sorting? Creating an array? — D Stanley, May 14 '17 at 22:18
@Kevin - unless you _need_ an array specifically, a `List` is easier to add items to, and has much of the same functionality as an array. I would start with that and see where you get stuck. — D Stanley, May 15 '17 at 13:47

Transfer linked stack to array to sort and vice versa

0 Answers0