Win a copy of Java 9 Revealed this week in the Features new in Java 9 forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

Compare first two elements of a stack  RSS feed

 
Aidan Johansson
Ranch Hand
Posts: 32
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello,
I would to write a method that accepts no arguments. This method has the following content:
1. If the top two elements on the stack are equal, then return true.
2. If the stack is null or has one element, return false.
3. Otherwise, if the top two elements are not equal, return false. Assume no element is null.

Here is my code.

Is this true?
Thank you.
 
Carey Brown
Bartender
Posts: 2603
40
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What is the class of 'top'?
this expression will compare the references to see if they both refer to the same instance. If you want to see if the contents are equal then use the equals() method. Note that if 'top' is an instance of one of the classes you implemented then you may have to implement the equals() method for that class.
 
Nguyen Tuyen
Greenhorn
Posts: 28
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What is the type of 'top'? I propose that 'top' is a stack, then:
In your first if statement: it will throw exception if top == null, because compiler will check first.
But if 'top' is a stack then you can not compare like this: because you cannot compare a stack with an element of it, it also wrong because stack do not have next() method!
 
Junilu Lacar
Sheriff
Posts: 10884
158
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Both previous responses are on the right track. My interpretation is that the question is trying to to see if the student knows how to use a combination of standard stack operations to do something that is not natively supported by a Stack.

So, first know what the standard stack operations are first. Then figure out which ones you can use in combination and in what order you would use them to check equality between the top two elements. Furthermore, the state of the stack must be the same after this operation is done as it was before.

Hint: a naive implementation is not going to be thread safe.
 
Aidan Johansson
Ranch Hand
Posts: 32
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I apologize. I forgot to inform you that I made a class call Stack but it actually works as a node. I define a node to have two slots: the first one is object and the next slots points to the next node. This class Stack implements a stack using a singly linked list. So I guess for my second comparison, I have to use:

Then:

Am I still right? Thanks.
 
Carey Brown
Bartender
Posts: 2603
40
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
--or--
You could implement equals() to internally access object, then you'd have:


This will probably mean that your "Base" class will also need to implement its own equals() method.
   
 
Aidan Johansson
Ranch Hand
Posts: 32
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you.
 
Junilu Lacar
Sheriff
Posts: 10884
158
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It's up to you to define the capabilities of the classes you create but for the purposes of learning data structures, a Stack is not defined the way you defined it. Sure, it can still use Nodes but a stack has a specific conceptualization associated with it.  The abstractions for a proper Stack implementation are limited to the top element, which is of course is accessed via a top() method and to certain operations you can perform on a stack, like push(), pop(), and peek().

If I were grading that code based on a learning goal of becoming familiar with Stack operations, then your code would fail. You are not using the Stack API; rather, you are using your intimate knowledge of the internal implementation of your data structure while totally ignoring the abstractions provided by a proper Stack.
 
Stephan van Hulst
Saloon Keeper
Posts: 7190
118
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Carey Brown wrote:--or--
You could implement equals() to internally access object

I don't like this approach because it implies that two nodes can be equal, even if the nodes that follow them do not. It's better to make this explicit by providing a different name, such as containsSameValue(Node other).

Hugh, don't use names like Base for generic type parameters. Use single capital letters, such as T.
 
Aidan Johansson
Ranch Hand
Posts: 32
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello,
I am supposed to compare the top two elements without changing the nature of the stack, i.e I am not supposed to use peek(), pop(), or push() as the way we implement those methods in class will change the date structures. We can define stack differently and it all depends on how we use it, so the method of implementation is different. This is what I think. Thank you for sharing your thoughts.
 
Aidan Johansson
Ranch Hand
Posts: 32
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan van Hulst wrote:Hugh, don't use names like Base for generic type parameters. Use single capital letters, such as T.


Thank you kindly.
 
Junilu Lacar
Sheriff
Posts: 10884
158
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hugh Winn wrote:Hello,
I am supposed to compare the top two elements without changing the nature of the stack, i.e I am not supposed to use peek(), pop(), or push() as the way we implement those methods in class will change the date structures. We can define stack differently and it all depends on how we use it, so the method of implementation is different. This is what I think. Thank you for sharing your thoughts.

Feel free to ignore this comment if you're focused on just getting your homework done and submitting it for a grade.  This comment has to do with a learning goal that goes beyond what your current learning goal appears to be.

As I said before, a Stack is associated with a specific set of concepts and abstractions. To add a method like areTheyEquals() that looks at TWO elements of the stack breaks away from the normal concepts and abstractions of a Stack. The whole point of a Stack is that you can deal directly ONLY with the top item.  If you start looking at things beneath the top item, then you're not treating your data structure like a Stack anymore.  You are, in fact, misusing and corrupting the idea of a Stack. So, in my opinion, this exercise is flawed at a very deep conceptual level. It is not a good exercise to use to evaluate whether a student understands what a Stack is.
 
Aidan Johansson
Ranch Hand
Posts: 32
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think it is confusing when I made a class called stack but it is implemented as a singly linked list.
I attached a drawing.
IMG_3598.JPG
[Thumbnail for IMG_3598.JPG]
 
Stephan van Hulst
Saloon Keeper
Posts: 7190
118
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
A linked list in a fine way to implement a stack. As a matter of fact, if you take a look at Java's LinkedList class, you will see that it implements Deque, which is a queue and a stack rolled into one interface.

However, the entire point of queues and stacks is that you only ever consider one element at a time. If you want to consider more than one element, that's an operation that's not part of the data type.
 
Piet Souris
Rancher
Posts: 1828
61
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Junilu Lacar wrote:As I said before, a Stack is associated with a specific set of concepts and abstractions. To add a method like areTheyEquals() that looks at TWO elements of the stack breaks away from the normal concepts and abstractions of a Stack. The whole point of a Stack is that you can deal directly ONLY with the top item.  If you start looking at things beneath the top item, then you're not treating your data structure like a Stack anymore.  You are, in fact, misusing and corrupting the idea of a Stack. So, in my opinion, this exercise is flawed at a very deep conceptual level. It is not a good exercise to use to evaluate whether a student understands what a Stack is.

Hmmm. I think this is a harsh comment. Assuming OP has the obligate methods pop and push (he did not publish all of his code), then what is wrong by adding some utility methods, even if they make use of the internal structure? For instance:

But

is a lot easier in this case (assuming top.next != null, of course)
 
Stephan van Hulst
Saloon Keeper
Posts: 7190
118
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Piet Souris wrote:what is wrong by adding some utility methods, even if they make use of the internal structure?

Only if they make sense in terms of what the class represents.

If I was part of the Java design team, I could have added a utility method to the String class to check if a string doesn't consist of exactly 4 Chinese ideograms, but wouldn't that be completely weird?
 
Junilu Lacar
Sheriff
Posts: 10884
158
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan and I are on the same page, it seems. The issue is not so much in the internal implementation details but rather the semantics of providing a method that doesn't fit the concepts and abstractions related to a Stack. Let's take it to the extreme and say that you added a method that allowed access to the "bottom" element of the stack, that is, the very first element pushed onto it. If you did that, then what's the use of calling your data structure a Stack? The capabilities of a data structure that provides access to the elements at both ends of it reflect the semantics of a Queue or a Deque (a Double-Ended Queue), not a Stack, so it would be misleading to call the data structure a Stack when in fact, it behaves like a Queue/Deque.

I'm not trying be super critical or nitpicky here. If you're going to learn something, learn it right. What's the point of learning if you are not learning the right way and the right thing?
 
Junilu Lacar
Sheriff
Posts: 10884
158
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Andy Hunt's Rule #1 always applies: Always Consider Context.

Let me give you guys a context where having a stack that looks at the top two elements might make sense.

Now, assuming a BasicStack implements the normal operations of a Stack that we have already pointed out, and considering the Open-Closed design principle, and considering that you should be very careful/conservative when you design for inheritance, would it be appropriate for the implementation of the isTopAPair() method here to know about the implementation details of the superclass or should it just use the normal Stack semantics that are inherited?

I would argue that a better implementation of this class would just use the normal Stack semantics and not care about taking advantage of the underlying implementation details of the superclass.  If you really needed to make performance a priority factor in considering design alternatives, then you will likely have to compromise and give up on another consideration, like maybe not having duplication in your class hierarchy. 

That is, if you wanted to take advantage of your knowledge of internal implementation details, then you'd have to make some fields and methods protected in the superclass instead of private, so that subclasses can access them. Doing that already starts to break the encapsulation of the superclass. Breaking encapsulation can lead to further problems.  If you don't want to go that route and you still want to have an "efficient" implementation, then you may have to duplicate all the basic functionality in your subclass, keeping them private, just implement the Stack interface instead of inheriting from the superclass BasicStack, then add the specialization that a PairDetectingStack provides.

Design is never really clear, cut-and-dry, black-and-white set of choices. It's a series of compromises and which way the balance of compromise goes all depends on the context in which these decisions are made.
 
Piet Souris
Rancher
Posts: 1828
61
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
But my problem is the judgements made, without knowing the context of the exercise. If I were a teacher, I'd love to put in questions like that, just to test if the student not only knows the definition, but also knows what that means and/or how to apply it. And indeed, if that would involve asking about chinese letters, why not? But admitted: I'm not a teacher.
 
Junilu Lacar
Sheriff
Posts: 10884
158
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Admittedly, we base our judgements solely on the information supplied by OP and things we either assumed or inferred from those. If the OP gave us incomplete or misleading information, then our judgements will be made in error. However, we can spend all afternoon and a week trying to cover all bases trying to be fair and list out all the possible variations and interpretations that might invalidate our judgements. These posts should be read in that context as well. 

So, what do we do, leave everything up for interpretation? I say, we can make reasonable guesses as to the meanings and make some reasonable judgements based on those.  If our guesses turn out to be wrong, then we need to backtrack. However, I have seen enough of these kinds of requirements to be very cynical about the amount of attention that many instructors put into their requirements. I have a growing list of horrific assignments given out by instructors that I have culled from many posts in these forums. The issues with these bad homework requirements I have gathered range from putrid and incompetent to careless and outdated.  So, you'll have to excuse me if I tend to seem a bit more judgmental and unforgiving of instructors possible mistakes because frankly, I've had enough of the type of nonsense and confusion that they sow, whether or not it was innocently made in good faith or out of negligence or lack of caring.
 
Junilu Lacar
Sheriff
Posts: 10884
158
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This is what I like to remind developers on my team coming in for a code review with me. This is also what I said the other day at the workshop that I facilitated, with educators, students, and one other industry professional in the room:

Don't take criticism personally. When I make criticisms about the code and design, I'm not saying YOU are stupid. I'm saying that the code/design, as it has been written, is flawed, and yes, sometimes, it's pretty stupid. The only time the flaw or stupidity reflects on the author is when the author doesn't want to accept reasonable criticism and insists that they are correct.  That means they are not willing to learn. When you are unwilling to learn and improve, THAT is what makes YOU stupid.


All my team mates get this, at least the ones who get to stay on my teams. All the workshop participants appreciated this and said it made sense. It's what egoless programming is all about.
 
Junilu Lacar
Sheriff
Posts: 10884
158
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I might also add that this was the feedback I got from one of the professors who attended the workshop (the workshop was about aligning academia with industry needs) -- she said, "You have been very respectful of our students and haven't been cruel or crushed them with harsh criticism."  Dr. Paul West, a member of these forums said, "Some of the kids were actually afraid to come because they saw some of your posts on JavaRanch and thought you might be brutal on them here but those fears were pretty much unfounded" or something to that effect.

A number of students even hung around and wanted to ask more questions about what it was really like in the industry, to see if their current perceptions were correct or not. I thought I gave them some very useful insights and many of the things I say all the time in these forums was what they seemed to appreciate the most.
 
Aidan Johansson
Ranch Hand
Posts: 32
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I am sorry I have been working all day. I just saw the comments. Is everything alright? Are we cool?
Thanks for helping out me.
 
Junilu Lacar
Sheriff
Posts: 10884
158
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think we should be all cool. Sometimes I'll get on a soapbox about the things I wrote about in this thread. Sorry if it diverted attention from your main question but I just think it's also important to look beyond the details of what you've been asked to do and look at the bigger picture. For me, the original thing asked of you was like, "Hey, see if you can add a toaster-oven to this" and you're all like "ok, I can plug in to the electrical system, pull enough power from the 12V battery then route to a step-up transformer that provides power to a small heating element ... and then the toast pops out of the cassette player."  So, it turns out, you were asked to put a toaster-oven in your car dashboard.  That's what putting a method like areTheyEquals() into a Stack class is like. It doesn't fit the big picture of a Stack, just as a toaster-oven doesn't fit in the big picture of a car.
 
Aidan Johansson
Ranch Hand
Posts: 32
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think what you have said helps me a lot. Even though I may not fully understand what you are saying, I will keep in mind for future practice.
Thank you.
 
Liutauras Vilda
Marshal
Posts: 3961
214
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Aidan Johansson, have a cow, your topic has been chosen to publish in our April's journal
 
Aidan Johansson
Ranch Hand
Posts: 32
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It is my honor. Thank you for doing that.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!