Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

Implement My Own Stack As A Linkedlist?

linked list stack

  • Please log in to reply
24 replies to this topic

#13 An Alien

An Alien

    CC Addict

  • Senior Member
  • PipPipPipPipPip
  • 323 posts
  • Programming Language:Java
  • Learning:C, Java, PHP, Python, JavaScript, Lisp, Transact-SQL, Others

Posted 27 June 2012 - 01:42 AM

Okay, did some research and put together bits of info from tuts together to create this class:
import java.util.LinkedList;
public class Stack<E> {
private LinkedList<E> MyList;
private int top = -1;

public Stack(){
  MyList = new LinkedList<E>();
}

public void push(E obj) {
		MyList.addFirst(obj);
		top++;
}
public E pop() {
		if (top == -1) {
				return null; // stack is empty
		}
		E temp = MyList.getFirst();
		MyList.removeFirst();
		top--;
		return temp;
}

public boolean isEmpty(){
		return top == -1;
}
public int size() {
		 return MyList.size();
}

}

  • 0

#14 wim DC

wim DC

    Roar

  • Expert Member
  • PipPipPipPipPipPipPipPip
  • 2681 posts
  • Programming Language:Java, JavaScript, PL/SQL
  • Learning:Python

Posted 27 June 2012 - 01:43 AM

Yup, that seems about right.

Removing/Searching isn't too hard. Just loop over the whole list, and compare the book ID with whatever the user entered. If it's equal, simply remove it.
  • 0

#15 An Alien

An Alien

    CC Addict

  • Senior Member
  • PipPipPipPipPip
  • 323 posts
  • Programming Language:Java
  • Learning:C, Java, PHP, Python, JavaScript, Lisp, Transact-SQL, Others

Posted 27 June 2012 - 01:53 AM

This isn't related to stacks/linkedLists. Scanner is giving me problems again. I'm getting the input mismatch exception because my professor typed it in the text file so wrong. Here's the txt file contents:

38176,Java For Beginners,2011,Jane Doe
29181,Home Sweet Home,2010,Elva Smith
49819,C++ Programming,2011,James Doe
12524,Developing Servlets,2009,Mary Hall
35002,JavaScript Language,2010,Marty Love
23675,Java Data Structures,2011,Jane Loveless
25317,C# for Dummy,2008,Ava Lang


scanner.nextInt() gives me exception. scanner.next() gives reads the ID and the first word of title like this: "29181,Home" because there's no whitespace. I'm not allowed the edit the text file either. What should I do?
  • 0

#16 wim DC

wim DC

    Roar

  • Expert Member
  • PipPipPipPipPipPipPipPip
  • 2681 posts
  • Programming Language:Java, JavaScript, PL/SQL
  • Learning:Python

Posted 27 June 2012 - 01:58 AM

You can set the delimter with the method "useDelimiter"
  • 0

#17 An Alien

An Alien

    CC Addict

  • Senior Member
  • PipPipPipPipPip
  • 323 posts
  • Programming Language:Java
  • Learning:C, Java, PHP, Python, JavaScript, Lisp, Transact-SQL, Others

Posted 27 June 2012 - 02:10 AM

Thanks, that worked. But the ID and the year are ints so I need to parse them. This gives me numberFormatException:
int id = Integer.parseInt(in.next().trim());

Edit: NVM, it was a silly mistake.
  • 0

#18 wim DC

wim DC

    Roar

  • Expert Member
  • PipPipPipPipPipPipPipPip
  • 2681 posts
  • Programming Language:Java, JavaScript, PL/SQL
  • Learning:Python

Posted 27 June 2012 - 02:14 AM

Shouldn't be happening. Print out what in.next() is, so you can see what you try to parse.

It possibly fails after the first line, cause your delimiter also needs to include a newline

delimiter: "[,\n]"

Depending on the file, it may also be
delimiter: "[,(\r\n)]"
  • 0

#19 An Alien

An Alien

    CC Addict

  • Senior Member
  • PipPipPipPipPip
  • 323 posts
  • Programming Language:Java
  • Learning:C, Java, PHP, Python, JavaScript, Lisp, Transact-SQL, Others

Posted 27 June 2012 - 02:45 AM

Having trouble. It looks like the data is incomplete somehow.

I implemented a to string method and there's probably a simpler way to do it, so maybe that's what's causing the problem. Main class (when I use the toString):
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Main {
public static void main(String[] args) throws FileNotFoundException {
  Stack<Book> stack = new Stack<Book>();
 
  File file = new File("bookrecs.txt");
  Scanner in = new Scanner(file);
  in.useDelimiter(",");
  while(in.hasNext()){
   //System.out.println(in.next());
   int id = Integer.parseInt(in.next().trim());
   String title = in.next();
   int year = Integer.parseInt(in.next().trim());
   String author = in.nextLine();
   stack.push(new Book(id, title, year, author));
  }
 
  System.out.println("Books have been entered in Stack...");
 
  System.out.println("Books:");
 
  System.out.println(stack.toString());
}
}

See toString() method in stack class:

import java.util.LinkedList;
public class Stack<E> {
private LinkedList<E> MyList; 
private int top = -1;

public Stack(){
  MyList = new LinkedList<E>();
}

public void push(E obj) {
	    MyList.addFirst(obj);
	    top++;
}
public E pop() {
	    if (top == -1) {
			    return null; // stack is empty
	    }
	    E temp = MyList.getFirst();
	    MyList.removeFirst();
	    top--;
	    return temp;
}

public boolean isEmpty(){
	    return top == -1;
}
public int getSize() {
		 return MyList.size();
}
public void removeID(int id){
  for(E b : MyList){
   if(((Book) <img src='http://forum.codecall.net/public/style_emoticons/<#EMO_DIR#>/cool.png' class='bbc_emoticon' alt='B)' />.getID() == id ){
    MyList.remove(<img src='http://forum.codecall.net/public/style_emoticons/<#EMO_DIR#>/cool.png' class='bbc_emoticon' alt='B)' />;
    top--;
   }
  }
}

public String toString(){
  int x = getSize();
  String tostring = ">null here<";
  for(int y = x-1; y > 0; y--){
   tostring+= MyList.get(y).toString()+ "\n";
  }
  return (tostring);
 
}
}

  • 0

#20 wim DC

wim DC

    Roar

  • Expert Member
  • PipPipPipPipPipPipPipPip
  • 2681 posts
  • Programming Language:Java, JavaScript, PL/SQL
  • Learning:Python

Posted 27 June 2012 - 03:43 AM

So... what does it print?
  • 0

#21 mctim

mctim

    CC Addict

  • Advanced Member
  • PipPipPipPipPip
  • 110 posts

Posted 27 June 2012 - 10:32 PM

Okay, but what about LinkedList. My stack is going to be actually a linkedList, right? How do I do that?


Reading now. But the first tutorial is using a vector instead of a linkedList? Can you also show me how to use a LinkedList too please?


Are you supposed to use java.util.LinkedList, or are you supposed to make your own? If the the former you can use the addFirst method to "push" and the removeFirst method to "pop" and all the sudden you'll have your stack. However, if you think that is the case I would ask my teacher first because that seems like too simple of an **ignment. Secondly, in the strictest sense, stacks do not have a search method. It doesn't typically make sense to search through a stack. That being said, if you are trying to see if your stack contains some particular object pop all the objects off into another stack until you find your object.Once you've done that you'll be able to recreate the original stack by popping the objects off the new stack back onto the old stack.

I would delete this but because I didn't realize we were on to the second page when I posted it, sorry guys.
  • 0

#22 mctim

mctim

    CC Addict

  • Advanced Member
  • PipPipPipPipPip
  • 110 posts

Posted 27 June 2012 - 11:01 PM

File file = new File("bookrecs.txt");
Scanner in = new Scanner(file);

Instead of doing that I'd do something like this, I think you'll find it alot simpler
File file = new File("bookrecs.txt");
FileReader fr = new FileReader(file);
BufferedReader buff = new BufferedReader(fr);
//you'l have to figure out how to see if you have another line but..
String line = buff.readLine();
String[] attributes = line.split(",");
//Now you have an array containing every comma separated value on the line
//For instance, this line: 38176,Java For Beginners,2011,Jane Doe
//would return an array that looks like this {"38176", "Java For Beginners", "2011", "Jane Doe"}

  • 0

#23 An Alien

An Alien

    CC Addict

  • Senior Member
  • PipPipPipPipPip
  • 323 posts
  • Programming Language:Java
  • Learning:C, Java, PHP, Python, JavaScript, Lisp, Transact-SQL, Others

Posted 28 June 2012 - 04:07 PM

Lol, I just found out that I had to also implement my own LinkedList which I am doing now but I'm having trouble. Please take a look at my LinkedList implementation. I think there are problems in get(int index) and/or remove() methods.

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Main {
public static void main(String[] args) throws FileNotFoundException {
Stack<Book> stack = new Stack<Book>();
Book b;
File file = new File("bookrecs.txt");
Scanner in = new Scanner(file);
in.useDelimiter(",");
while(in.hasNext()){
//System.out.println(in.nextInt());
int id = Integer.parseInt(in.next().trim());
String **le = in.next();
int year = Integer.parseInt(in.next().trim());
String author = in.nextLine();
stack.push(b = new Book(id, **le, year, author));
//System.out.println(b.toString());
}


System.out.println(stack.toString());
boolean cont = true;
do{
int id;
in = new Scanner(System.in);
System.out.println("Please enter ID of book you'd like to remove:");
id = in.nextInt();
stack.removeID(id);
System.out.println("Stack removed!");
System.out.println(stack.toString());
System.out.println("Would you like to continue? (y/n)");
String contstring = in.next();
if(contstring.equals("n"))
cont = false; System.out.println("Exiting....Goodbye.");
}while(cont);
}
}


public class Stack<E> {
private LinkedList<Book> MyList;
private int top = -1;

public Stack(){
MyList = new LinkedList<Book>();
}

public void push(Book obj) {
	 MyList.addFirst(obj);
	 top++;
}
public Book pop() {
	 if (top == -1) {
			 return null; // stack is empty
	 }
	 Book temp = MyList.getFirst();
	 MyList.removeFirst();
	 top--;
	 return temp;
}

public boolean isEmpty(){
	 return top == -1;
}
public int getSize() {
		 return MyList.size();
}
public void removeID(int id){
for (int i = 0; i < MyList.size(); i++) {
	 if(((Book) MyList.get(i)).getID()==id){
	 MyList.remove(i);
	 break;
	 }
}
}

public String toString(){
int x = getSize();
String tostring = "";
for(int y = x-1; y >= 0; y--){
tostring+= MyList.get(y).toString()+ "\n";
}
return (tostring);

}
}



import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class LinkedList<E> {

	    static Node first = null;    
	    static Node last  = null;  
	    static int count = 0;

    public static void main(String[] args) throws FileNotFoundException {
        
        File file = new File("bookrecs.txt");
	    Scanner in = new Scanner(file);
        in.useDelimiter(",");

	    
	    //add book recs to list:
        while(in.hasNext()){

            //System.out.println(in.next());
            int id = Integer.parseInt(in.next());
            String **le = in.next();
            int year = Integer.parseInt(in.next().trim());
            String author = in.nextLine();
            
            Book b;
            b = new Book(id, **le, year, author);
            Node e = new Node();
            e.element = b;
            
            if(first == null){
                first = e;
                count = 1;
            }
            else {			    
                first.previous = e;	   // last.prev is another node so link them.
                first.previous.index = first.index++;

		    }
            e.next = first;
		    first = e;			    // Update last to match new bookrec.
		    count++;
		    
	    }
        
	    for (Node e = first; e != null; e = e.previous) {
		    System.out.println(e.element);
	    }

        
    }

    
    

    public void addFirst(Book <img src='http://forum.codecall.net/public/style_emoticons/<#EMO_DIR#>/cool.png' class='bbc_emoticon' alt='B)' /> {
            
        Node e = new Node();
        e.element = b;
        
        if(first == null){
            first = e;
            first.index = 0;
            count = 0;
        }
        else {			    
            first.previous = e;	   // last.prev is another node so link them.
            first.previous.index = first.index++;
	    }
        e.next = first;             //next node of new first is updated to old first
	    first = e;			    // Update first to match new bookrec.
	    count++;
	    
        
    }

    public E getFirst() {
        
        return (E) first;
    }

    public void removeFirst() {
        
        first = first.next;
        count--;
        
    }

    public int size() {
        // TODO Auto-generated method stub
        return count;
    }

    public void remove(int i) {
        if(get(i) == null){
            System.out.println("remove(i): i not found in LinkedList");
            count--;
        }
        else{
            
        }
        
    }

    public Book get(int y) {
	    for (Node e = first; e != null; e = e.next) {
		    if(e.index == y){
		        return (Book) e.element;
		    }
		    else{
		        e.index++;
		    }
	    }
	    return null;
    }
	    
   
	    
        
        
    }



datafile:

38176,Java For Beginners,2011,Jane Doe
29181,Home Sweet Home,2010,Elva Smith
49819,C++ Programming,2011,James Doe
12524,Developing Servlets,2009,Mary Hall
35002,JavaScript Language,2010,Marty Love
23675,Java Data Structures,2011,Jane Loveless
25317,C# for Dummy,2008,Ava Lang


  • 0

#24 mctim

mctim

    CC Addict

  • Advanced Member
  • PipPipPipPipPip
  • 110 posts

Posted 29 June 2012 - 09:50 AM

2 things, First off why do you have so many mains? You have like 3 cl**es that have a method main, that's just bad practice. Secondly, where is your node cl**? Nobody is gonna be able to help much without that. That all being said I see a few things that raise alarms with me right off hand. Your LinkedList is generic however your addFirst method and get method use Books. Add first should take a parameter of type E and get should return E. Secondly I'm not sure It's a good Idea to let the nodes keep track of what index they are at. For instance,
else {						 
					    first.previous = e;	    // last.prev is another node so link them.
					    first.previous.index = first.index++;
}
That wont work. Your liable to have a whole linked list after the first node and none of those nodes will have their indexes updated, and It is not a good idea to propagate down the list updating node indexes everytime you add an element. Another thing i see is this:
if(first == null){
					    first = e;
					    first.index = 0;
					    count = 0;
}
That doesn't make sense at all. When you add your first element your count becomes 1 not 0. That's pretty much all I can tell you for now.
  • 0





Also tagged with one or more of these keywords: linked list, stack

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download