Java. Searching and sorting a stack

[XodoX]

I'm trying a practice problem from the book. It's 10 books with title, ISBN, and year. The input needs to be sorted by year and it needs to let you search for a book title.

class LinkedStack
{
    /**
       The Node class is used to implement the 
		 linked list.
    */
    
    private class Node
    {
        String value;
        Node next;
        Node(String val, Node n)
        {
            value = val; 
            next = n;
        }       
    }
    
    private Node top = null;  // Top of the stack
    
    /**
       The empty method checks for an empty stack.
       @return true if stack is empty, false otherwise.


    */
    
    public boolean empty()
    {
        return top == null;
    }
    
    /**
       The push method adds a new item to the stack.
       @param s The item to be pushed onto the stack.
    */
    
    public void push(String s)
    {
        top = new Node(s, top);
    }
    
    
    
    
    /**
       The toString method computes a string 
		 representation of the contents of the stack.
       @return The string representation of the 
		 stack contents.
    */
    
    public String toString()
    {
        StringBuilder sBuilder = new StringBuilder();
        Node p = top;
        while (p != null)
        {
            sBuilder.append(p.value);            
            p = p.next;
            if (p != null)
				   sBuilder.append("\n");
        }
        return sBuilder.toString();
    }
}


public class LinkedStack
{
   public static void main(String [ ] args)   
   {
       LinkedStack st = new LinkedStack();
       
       System.out.println("Contents of Stack:");
       st.push("Amy");
       st.push("Bob");
       st.push("Chuck");
       System.out.println(st);   
              
   }    
}

Would this work as basic frame? I do not need the tostring here, though, do I? I would do a loop to search for a title. And I'm not sure about how to sort it by year.

If not, I would appreciate if someone could show me where to find a basic frame for this. Then I could look at it and understand it, and then I could add the other things. I feel a little stupid because I don't seem to get it.

 

[chiro]

Hey XodoX.

For the sort, do you have to implement your own sort or use a standard sorting interface? Also you might want to take into account to sort things by a standardized case rather than the raw case data itself.

What I mean by the above is that instead of treating say "Xanadu" and "xanadu" differently, you treat them the same by converting them to all the same case in a temp structure and then sorting this. This is a practical implementation since you usually won't distinguish between "Xanadu", "XANADU", and "xanadu" in terms of places.

If you have a sorting interface, you usually pass a routine that determines how to tell whether something is "less than", "equal to", or "greater" than something else and the underlying sort routine will take care of the rest.

 

[XodoX]

Hey XodoX.

For the sort, do you have to implement your own sort or use a standard sorting interface? Also you might want to take into account to sort things by a standardized case rather than the raw case data itself.

What I mean by the above is that instead of treating say "Xanadu" and "xanadu" differently, you treat them the same by converting them to all the same case in a temp structure and then sorting this. This is a practical implementation since you usually won't distinguish between "Xanadu", "XANADU", and "xanadu" in terms of places.

If you have a sorting interface, you usually pass a routine that determines how to tell whether something is "less than", "equal to", or "greater" than something else and the underlying sort routine will take care of the rest.

Thanks. I will try it. Does that mean, though, that the stack frame is good? Can I go from there?

 

[chiro]

Thanks. I will try it. Does that mean, though, that the stack frame is good? Can I go from there?

For dynamic lists, you usually use what is called a linked-list and not a stack.

They are pretty much the same thing except the list also has a 'previous' pointer in each node and not just a 'next'.

The reason is that if you want to say 'delete' an entry in the middle of the list, then you simply delete that node and reconnect the 'next' and 'previous' to the right ones. Specifcally if we had say nodes 1-2-3 and we wanted to delete 2, then we would delete two and 1's 'next' node would point to 3 and 3's 'previous' node would point to 1.

If you do not have to use a stack structure, you could use a linked-list structure or even a binary tree structure to store your library. A binary tree structure can be used to automatically sort your data in a quick-way (which is useful for when you have a huge number of books).

If you have to use a stack for your assignment or homework then OK but if not I think you should add a 'previous' pointer and a delete function which will allow you to delete and add arbitrary books. Then with this you can automatically sort the list by calculating exactly where the book should go (i.e. in alphabetical order) and then just insert the book in the right place between existing books.

You can also have another list that sorts by date using the same idea (i.e. find where the book goes between and insert into this second list).

You will have two list data structures: a sorted one for title and a sorted one for date. Then to get the actual data, just use your toString routine exactly as you have written it.

 

[XodoX]

For dynamic lists, you usually use what is called a linked-list and not a stack.

They are pretty much the same thing except the list also has a 'previous' pointer in each node and not just a 'next'.

The reason is that if you want to say 'delete' an entry in the middle of the list, then you simply delete that node and reconnect the 'next' and 'previous' to the right ones. Specifcally if we had say nodes 1-2-3 and we wanted to delete 2, then we would delete two and 1's 'next' node would point to 3 and 3's 'previous' node would point to 1.

If you do not have to use a stack structure, you could use a linked-list structure or even a binary tree structure to store your library. A binary tree structure can be used to automatically sort your data in a quick-way (which is useful for when you have a huge number of books).

If you have to use a stack for your assignment or homework then OK but if not I think you should add a 'previous' pointer and a delete function which will allow you to delete and add arbitrary books. Then with this you can automatically sort the list by calculating exactly where the book should go (i.e. in alphabetical order) and then just insert the book in the right place between existing books.

You can also have another list that sorts by date using the same idea (i.e. find where the book goes between and insert into this second list).

You will have two list data structures: a sorted one for title and a sorted one for date. Then to get the actual data, just use your toString routine exactly as you have written it.

The book says stack with a linked list implementation. So that's what I want to do. Ugh, this sounds difficult. I can't even find a stack linked list frame so that I can go from there :(

 

[phylotree]

The book says stack with a linked list implementation. So that's what I want to do. Ugh, this sounds difficult. I can't even find a stack linked list frame so that I can go from there :(

Stack and Linked List are different data structures. You can use Linked List to implement a Stack, something like this,

class LinkedStack
{
    /**
       The Node class is used to implement the 
		 linked list.
    */
    
    private class Node
    {
        Node next;
        Node()
        {
            
        }       
    }
    private Node startNode, newNode, pNode;//etc
    public void Push()
    {
        newNode.next=NULL; //0
        if(startNode==NULL)
        {
            startNode=newNode;
        }
        else
        {
            pNode=startNode;
            while(pNode.next!=NULL)
            {
                 pNode=pNode.next;
                 pNode.next=newNode;
            }
        }
    }
    public Node Pop()
    {
         //do something similar to delete a node from the list then return the deleted node.
    }
    //other methods : sorting,searching
}