*
The moose likes Java in General and the fly likes Stacks and Queue Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Murach's Java Servlets and JSP this week in the Servlets forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "Stacks and Queue" Watch "Stacks and Queue" New topic
Author

Stacks and Queue

William Koch
Ranch Hand

Joined: Sep 26, 2012
Posts: 76
I have no idea where to start with this homework exercise. I am not asking or looking for someone to give me the solution to please do not do so. I need helpful hints and guidance that will help me come upon the answer myself. If anyone is interested in helping I have included the HTML file that has the instructions and the Java Project folder that has the java files in it. They are in a .rar archive at the following link:
http://www.filebox.com/3ykyx843grcz Thanks a bunch.

-Will
Devaka Cooray
ExamLab Creator
Saloon Keeper

Joined: Jul 29, 2008
Posts: 3013
    
  35

William,

It's less likely that people here would actually grab that file and read the instructions given in it. A better way to get more people to answer your question is isolating your problem and narrowing the question. I however finally managed to download it after getting busted with that damn popups and danged ads all over. As what I can see in the document, instructions are given from the scratch starting from using "New->Class" to add a class to the given project - I think you better go with these instructions at the first place and come back if you find something is overwhelming you.


Founder of ExamLab and Systemup
See how I can help you to become an awesome programmer
Kemal Sokolovic
Bartender

Joined: Jun 19, 2010
Posts: 825
    
    5

You'll hardly get an answer that will be more useful to you than the document you already have. It's pretty straightforward. On the other hand, you need to TellTheDetails for the specific part of your assignment you're having problem with, ShowSomeEffort (not posting it here before you probably even started working on it).

I just ran through the text, and it's pretty clear. You are given a Pool interface with methods that should be implemented in your Stack and Queue classes. Before you jump to implementation, you must know what's the behavior of these structures.

Stack (LIFO - Last In First Out) is a structure in which all operations are made at one end, referred to as top. So, basically, when you add (push) element to the stack you add it to top; when you remove (pop) it you remove the one from the top. Hence, top is the only directly accessible element of a stack. E.g. if you push values [A, B, C, D] to the stack in that order, when you pop them you'll get [D, C, B, A].
Queue (FIFO - First In First Out) is a structure in which the first value to go in is the first value to go out. When getting a value from the queue (dequeue) you're always getting an element that has been in the queue the longest. E.g. if you enqueue values [A, B, C, D] to the queue in that order, when you dequeue them you'll get [A, B, C, D].

Once you understand how these structures work, you can move to implementation. You can use whatever underlying structure for storing your values, e.g. ArrayList. Once you how each operation works:

As for Queue:


Not that hard, right? As for test scenarios, try to write some test on your own when you implement these, and come back if you encounter some difficulty.


The quieter you are, the more you are able to hear.
William Koch
Ranch Hand

Joined: Sep 26, 2012
Posts: 76
Thanks a bunch! I will be working on it tonight and I will post more if I run into problems.
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19649
    
  18

LinkedList works better for both stacks and queues. It's a lot more efficient for adding or removing elements at the start or end. The main advantage ArrayList provides, fast access to any element, is something you don't need in this case.


SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6
How To Ask Questions How To Answer Questions
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Rob Spoor wrote:LinkedList works better for both stacks and queues. It's a lot more efficient for adding or removing elements at the start or end.


For a strict LIFO (a stack), ArrayList is just as fast. It can even be made to be as fast for a FIFO, but that wouldn't really be worth the effort.
Kemal Sokolovic
Bartender

Joined: Jun 19, 2010
Posts: 825
    
    5

Rob Spoor wrote:LinkedList works better for both stacks and queues. It's a lot more efficient for adding or removing elements at the start or end. The main advantage ArrayList provides, fast access to any element, is something you don't need in this case.


In case where you push/pop elements at the beginning of the ArrayList (index 0), there might be a difference, but it's really significant with very large amount of data. It's the result of constant shifting other elements to the right when pushing, or to the left when popping the one from the beginning. But if you implement stack so you do all operations on last element of ArrayList, I don't agree with that point.
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 2982
    
    9
If you need both queue and stack operations (FIFO and LIFO), let's not forget ArrayDeque. It's great at everything except for insert/delete in the middle. Oh, and like ArrayList, operations are often in amortized constant time, not constant time. Which occasionally matters, but usually doesn't.
Seetharaman Venkatasamy
Ranch Hand

Joined: Jan 28, 2008
Posts: 5575

Mike Simmons wrote:If you need both queue and stack operations (FIFO and LIFO), let's not forget ArrayDeque.

doubly linkedlist[java.util.LinkedList] still can defend ArrayDeque Mike
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 2982
    
    9
Sure, LinkedList was already brought up by Rob. That's what I was responding to. For the general use case he cited (LIFO + FIFO), ArrayDeque is fully competitive with LinkedList. Which one is actually better depends on the exact details of the use case. ArrayDeque is often faster than LinkedList, as long as you don't mind the uneven timing coming from resizes, as "amortized" implies. And as long as you don't need any other functionality like inserting into the middle.

In fact I would say that for the general LIFO + FIFO case, it may be worth considering all four standard Deque implementations: LinkedList, ArrayDeque, ConcurrentLinkedDeque, and LinkedBlockingDeque. The point is, there's much more to collections nowadays than just ArrayList vs LinkedList.
William Koch
Ranch Hand

Joined: Sep 26, 2012
Posts: 76
So if I am going to use an ArrayList to do this. Do I need to specify an object that is going to be used. Or do the methods need to take in anything? Or can I just use the Pool object that contains type E object and have that be what gets passed in for the isEmpty() method?
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

William Koch wrote:So if I am going to use an ArrayList to do this. Do I need to specify an object that is going to be used. Or do the methods need to take in anything? Or can I just use the Pool object that contains type E object and have that be what gets passed in for the isEmpty() method?


That's up to you to decide, or your instructor. Your requirements may be that you accept only certain types, or that you accept any type simply as object, or that you accept any type or subtree of types using generics. Any of those can be accommodated, regardless of whether you back it with an ArrayList or one of the other classes.

Note also that I was not suggesting that you use ArrayList. It may or may not be appropriate. I don't know enough about your requirements to say. I was merely pointing out that if you're only doing LIFO, not FIFO, then it will perform about the same as a LinkedList.
William Koch
Ranch Hand

Joined: Sep 26, 2012
Posts: 76
Here is a copy of the requirements. They are below. I am fairly new to Java. I am switching from Ada and they threw me straight into a Data Structures class using Java. Any suggestions would be helpful.

Understand the Pool interface
The util package declares the Pool interface:

public interface Pool {
boolean isEmpty();
void add(E e);
E remove();
}

Pool is being used here in the sense of “pool of candidates” or “motor pool”, not “swimming pool” or “billiards”!

This interface is a generalization of stacks and queues. A Pool<E> is a container for holding elements (of type E) that are available to be chosen. You can add a new element to the pool (like pushing an element onto a stack or enqueueing an element in a queue), or remove an element from the pool (like popping an element off a stack or dequeueing an element from a queue).

However, the pool interface does not specify which element should be removed from the pool, so different implementations of the interface can make this choice in different ways. For example, a stack implementation should remove the most recently added element, whereas a queue implementation should remove the least recently added element.

All implementations of the remove method should throw NoSuchElementException when called on an empty pool. (See page 675 of the textbook for how to throw an exception.) The NoSuchElementException class is defined in the java.util package, so you'll probably want to include the line

import java.util.NoSuchElementException;

or (if you are using other parts of java.util as well)

import java.util.*;

somewhere before your class declaration and after the package declaration (if any).

Note that Pool is a simplified version of java.util.AbstractQueue, cut down to its bare essentials.

Important: All implementations of Pool must support all three methods in O(1) time.

(For implementations that use an array under the covers—such as an ArrayList or Vector—you can ignore the occasional linear time blip that happens when the underlying array is reallocated and copied, because the reallocations happen infrequently enough that the time averages out to O(1). For a more detailed discussion of this issue, see the section “Performance of the KWArrayList Algorithms” on page 86, which refers back to the reallocate() method on page 76.)
Develop and test the Stack class

Use the New Class wizard in Eclipse to create a new Stack class inside the util package that implements the Pool interface.

Click New → Class.
Fill in the Package field with util. (This step is new)
Fill in the Name field with Stack.
Next to the Interfaces box, click Add..., then select Pool - util. Click OK. (This step is new)
Click Finish.

Note that Java stores files in directories that mimic the package structure of the classes. Because the Stack class is in the util package, the new Stack.java file will be stored in the Pool/src/util directory.

Now, inside the new Stackclass, implement the three Pool methods so they provide the expected LIFO behavior.

Use the New JUnit Test Case wizard to make a new StackTest class in the Pool/test folder. Choose util.Stack as the Class under test. Important: Leave the Package field blank!

Create enough tests inside StackTest to give the mythical “reasonable person” confidence that your implementation is correct. Remember that each separate test will have the form

@Test
public void testXXX() {
...
}

See the Testing Advice section below for suggestions about how to test stacks and queues.

Because the StackTest class should not be inside the util package, you'll probably need to add the line

import util.Stack;

at the top of StackTest.java.
Develop and test the Queue class

Follow the same process as above to develop a Queue class with the expected FIFO behavior, and a QueueTest class to test it.
Save your test results

When you are ready to turn in the exercise, create a file with your test results.

From the shell, cd into the Pool directory in your workspace. (If you do an ls, you should see the bin, src, and test directories.)
Run the following command:

java -cp bin:/usr/local/junit/junit-4.11.jar org.junit.runner.JUnitCore StackTest QueueTest

This should print the test results to the screen.
Save the test results to a file by running the command

java -cp bin:/usr/local/junit/junit-4.11.jar org.junit.runner.JUnitCore StackTest QueueTest > testresults.txt

Instead of typing this from scratch, you can use an up-arrow to bring back the previous command, and then add “> testresults.txt” to the end of the line. This is called file redirection—it saves the text that would have been printed to the screen into a file instead.
You can verify the file contents by running

cat testresults.txt

to display the file on the screen.
Kemal Sokolovic
Bartender

Joined: Jun 19, 2010
Posts: 825
    
    5

William, I believe you've got enough guidelines to start working on your assignment. No need to post entire assignment here, those of us who wanted to read it did it at the link you provided. Still, nobody is going to implement it for you. You should start working on it and if you're stuck at some part feel free to ask again.
William Koch
Ranch Hand

Joined: Sep 26, 2012
Posts: 76
Ok so here is where I get stuck. Lets take isEmpty() and try and make it work if we implement Pool<E> as a stack for example. Because I am working with a Pool that holds type E or Pool<E>, does that mean the isEmpty method must have a field of type Pool and then check if the first index of the pool is null? I do not know how to work with a Pool so I was wondering how I can copy all its elements into an ArrayList? And then check if the bottom of the arraylist is null or not. Do I need to do this?
Kemal Sokolovic
Bartender

Joined: Jun 19, 2010
Posts: 825
    
    5

Pool is just an interface that you should implement. Read this tutorial to catch up with interfaces.
Interface specifies methods that your classes need to provide. So your Pool interface declares three methods you need to implement in your classes.
Methods don't have fields, but variables (local ones), and since Pool is interface you cannot (or should) have a variable of type Pool in your method.

ArrayList (or any other structure suggested during discussion) should just be used as an underlying structure to keep the values of your Stack/Queue. So, in your implementation you should have one field of that type. The way you manipulate (add or remove) data from that structure is actually what you should worry about in your implementation.

Since data field is used to keep the data currently on your stack, method isEmpty() of your stack would do the following: if the stack is empty return true, otherwise return false. The result is the same as if you would check if the data is empty or not, so you would have:

You have that method done, so I hope you got the concept now. You can now proceed with the implementation of other methods and then move to Queue class.
William Koch
Ranch Hand

Joined: Sep 26, 2012
Posts: 76
Thank you for that but I think I would like to try something a little different. But yes the way you put it helped explain the concept. Stack is already in the Java API.

Could I do the following:


I get a few errors when I do this though. Not sure why. The errors read as follows:
-E cannot be resolved to a type
-The type Stack is not generic; it cannot be parameterized with arguments <E>

Any ideas?

Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18501
    
  40

William Koch wrote:
Could I do the following:




Can you tell us what you are trying to do? As you can tell from the compile errors, this code isn't valid Java code (with generics). But we don't know what you are trying to do here.

Henry


Books: Java Threads, 3rd Edition, Jini in a Nutshell, and Java Gems (contributor)
William Koch
Ranch Hand

Joined: Sep 26, 2012
Posts: 76
Read the earlier posts please
William Koch
Ranch Hand

Joined: Sep 26, 2012
Posts: 76
@Kemal Sokolovic

How does this look for the stack and queue.

Also if anyone has any JUnit Test Cases (i.e. StackTest.java and QueueTest.Java) that would be awesome.









 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Stacks and Queue
 
Similar Threads
Where to learn Java Mobile
how do i compare row by row
Few questions for Ray
passed WLS 6.0 exam with 90%
Unable to add an element to an arraylist using extended class