Difference between revisions of "Stack Assignment"

From CSE231 Wiki
Jump to navigation Jump to search
 
(15 intermediate revisions by 2 users not shown)
Line 3: Line 3:
  
 
=Background=
 
=Background=
<youtube>wjI1WNcIntg</youtube>
+
{{CollapsibleYouTube|HackerRank: Stacks and Queues|<youtube>wjI1WNcIntg</youtube>}}
 
===interface Stack===
 
===interface Stack===
<nowiki>public interface Stack<E> {
+
<syntaxhighlight lang="java">public interface Stack<E> {
 
void push(E value);
 
void push(E value);
Optional<E> peek();
+
E peek();
Optional<E> pop();
+
E pop();
}</nowiki>
+
}</syntaxhighlight>
  
 
==Example==
 
==Example==
Line 17: Line 17:
 
[[File:Stack_empty.svg]]
 
[[File:Stack_empty.svg]]
  
In this state, <code>stack.peek()</code> will return <code>Optional.empty()</code> and <code>stack.pop()</code> will also return <code>Optional.empty()</code>.
+
In this state, <code>stack.peek()</code> will return <code>null()</code> and <code>stack.pop()</code> will also return <code>null</code>.
  
 
===push A, B, C, D, E===
 
===push A, B, C, D, E===
<nowiki>Stack<String> stack = new NotThreadSafeStack<>();
+
<syntaxhighlight lang="java">Stack<String> stack = new NotThreadSafeStack<>();
 
stack.push("A");
 
stack.push("A");
 
stack.push("B");
 
stack.push("B");
 
stack.push("C");
 
stack.push("C");
 
stack.push("D");
 
stack.push("D");
stack.push("E");</nowiki>
+
stack.push("E");
 +
</syntaxhighlight>
  
 
[[File:Stack_edcba.svg]]
 
[[File:Stack_edcba.svg]]
  
In this state, <code>stack.peek()</code> will return <code>Optional.of("E")</code>.
+
In this state, <code>stack.peek()</code> will return <code>"E"</code>.
  
 
===push A, B, C, D, E, pop===
 
===push A, B, C, D, E, pop===
<nowiki>Stack<String> stack = new NotThreadSafeStack<>();
+
<syntaxhighlight lang="java">Stack<String> stack = new NotThreadSafeStack<>();
 
stack.push("A");
 
stack.push("A");
 
stack.push("B");
 
stack.push("B");
Line 38: Line 39:
 
stack.push("D");
 
stack.push("D");
 
stack.push("E");
 
stack.push("E");
Optional<String> optOfE = stack.pop();</nowiki>
+
String e = stack.pop();
 +
</syntaxhighlight>
  
 
[[File:Stack_dcba.svg]]
 
[[File:Stack_dcba.svg]]
  
In this state, <code>optOfE</code> will hold <code>Optional.of("E")</code> and <code>stack.peek()</code> will return <code>Optional.of("D")</code>.
+
In this state, <code>e</code> will hold <code>"E"</code> and <code>stack.peek()</code> will return <code>"D"</code>.
  
 
=Code To Implement=
 
=Code To Implement=
Line 50: Line 52:
 
We will build an [https://www.javadoc.io/static/com.google.code.findbugs/jsr305/3.0.1/javax/annotation/concurrent/Immutable.html @Immutable] class Node.
 
We will build an [https://www.javadoc.io/static/com.google.code.findbugs/jsr305/3.0.1/javax/annotation/concurrent/Immutable.html @Immutable] class Node.
  
{{CodeToImplement|Node|value<br/>next|stack.node.exercise|main}}
+
{{CodeToImplement|Node|value<br/>next|stack.node.exercise|student-pre-aspect}}
 +
 
 +
{{Warning|class Node is found in the stack.node.exercise package in ***student-pre-aspect***}}
  
 
====constructor and instance variables====
 
====constructor and instance variables====
Line 56: Line 60:
 
The constructor
 
The constructor
  
  <nowiki>public Node(E value, Optional<Node<E>> next)</nowiki>
+
  <nowiki>public Node(E value, Node<E> next)</nowiki>
  
 
is passed a value and a next.  Hang on to this data in instance variables.  As instances of Node are to be immutable, the instance variables should be marked as <code>final</code> which prevents them from being re-assigned.
 
is passed a value and a next.  Hang on to this data in instance variables.  As instances of Node are to be immutable, the instance variables should be marked as <code>final</code> which prevents them from being re-assigned.
Line 69: Line 73:
  
 
==NotThreadSafeStack==
 
==NotThreadSafeStack==
<nowiki>public interface Stack<E> {
+
<syntaxhighlight lang="java">
void push(E value);
+
@NotThreadSafe
 
+
public class NotThreadSafeStack<E> implements Stack<E>
Optional<E> peek();
+
</syntaxhighlight>
 
 
Optional<E> pop();
 
}</nowiki>
 
  
 
{{NotThreadSafeLink}}
 
{{NotThreadSafeLink}}
  
 
{{CodeToImplement|NotThreadSafeStack|push<br/>peek<br/>pop|stack.notthreadsafe.exercise}}
 
{{CodeToImplement|NotThreadSafeStack|push<br/>peek<br/>pop|stack.notthreadsafe.exercise}}
 +
 +
'''Note:''' The constructor has been intentionally omitted. Simply initialize the instance variable you need when you declare it.
  
 
====instance variables====
 
====instance variables====
Line 101: Line 104:
  
 
=Pledge, Acknowledgments, Citations=
 
=Pledge, Acknowledgments, Citations=
{{Pledge|atomic-stack}}
+
{{Pledge|stack}}

Latest revision as of 14:27, 3 September 2024

Motivation

We will build an initial not-thread-safe implementation of a Stack. This exercise will allow us to gain experience building a data structure and see how it performs when used in a parallel for which it was not designed. Later in the semester we will build two thread-safe implementations: one concurrent and one atomic. Your work on this exercise will pay dividends on these later exercises.

Background

Video: HackerRank: Stacks and Queues  

interface Stack

public interface Stack<E> {
	void push(E value);
	E peek();
	E pop();
}

Example

empty

Stack<String> stack = new NotThreadSafeStack<>();

Stack empty.svg

In this state, stack.peek() will return null() and stack.pop() will also return null.

push A, B, C, D, E

Stack<String> stack = new NotThreadSafeStack<>();
stack.push("A");
stack.push("B");
stack.push("C");
stack.push("D");
stack.push("E");

Stack edcba.svg

In this state, stack.peek() will return "E".

push A, B, C, D, E, pop

Stack<String> stack = new NotThreadSafeStack<>();
stack.push("A");
stack.push("B");
stack.push("C");
stack.push("D");
stack.push("E");
String e = stack.pop();

Stack dcba.svg

In this state, e will hold "E" and stack.peek() will return "D".

Code To Implement

Node

The mighty cons cell goes back to the early days of computing. People have been building amazing systems with this data structure since the 1950s.

We will build an @Immutable class Node.

class: Node.java Java.png
methods: value
next
package: stack.node.exercise
source folder: student-pre-aspect/src/main/java
Attention niels epting.svg Warning:class Node is found in the stack.node.exercise package in ***student-pre-aspect***

constructor and instance variables

The constructor

public Node(E value, Node<E> next)

is passed a value and a next. Hang on to this data in instance variables. As instances of Node are to be immutable, the instance variables should be marked as final which prevents them from being re-assigned.

value

return the value.

next

return the next node.

NotThreadSafeStack

@NotThreadSafe
public class NotThreadSafeStack<E> implements Stack<E>

@NotThreadSafe

class: NotThreadSafeStack.java Java.png
methods: push
peek
pop
package: stack.notthreadsafe.exercise
source folder: student/src/main/java

Note: The constructor has been intentionally omitted. Simply initialize the instance variable you need when you declare it.

instance variables

What state do you need to keep track of to support a mutable non-thread-safe Stack?

push

peek

pop

Distasters To Investigate

NOTE: you only need to investigate these disaster clients. You need not fix them. Our NotThreadSafeStack is designed to be used in a single sequential thread. Not surprisingly, it fails when it is mutated in parallel.

ParallelPushStackDisasterClient

class: ParallelPushStackDisasterClient.java WHMIS Class D-1.svgBroken
methods: main
package: stack.notthreadsafe.disaster
source folder: src/main/java

ParallelPushAndPopStackDisasterClient

class: ParallelPushAndPopStackDisasterClient.java WHMIS Class D-1.svgBroken
methods: main
package: stack.notthreadsafe.disaster
source folder: src/main/java

Testing

class: _NotThreadSafeStackTestSuite.java Junit.png
package: stack.notthreadsafe.exercise
source folder: testing/src/test/java

Pledge, Acknowledgments, Citations

file: stack-pledge-acknowledgments-citations.txt

More info about the Honor Pledge