Java Archives - copypasteearth

Merge Sort algorithm with Generics that implement Comparable interface

Sorting algorithms are used everyday to sort all types of information in computer programs so I decided to share a O(Nlog2N) sorting algorithm called Merge Sort with you today. This is written in Java Programming. I shared a post last year on Quick Sort algorithm and I just decided to do all of the Big-O (Nlog2N) sorting algorithms. Of course Java has many built in data structures and uses the best sorting algorithms already, but if you are learning about data structures and algorithms you might find this post handy.

First I will post the Circle class just like in the Quicksort example that can be found here by the way QuickSort sorting algorithm in java with Generics that implement Comparable

Circle.java

/**
 * author: copypasteearth
 * date: 7/17/2019
 */
public class Circle implements Comparable<Circle> {
    public int xValue;
    public int yValue;
    public int radius;

@Override
public int compareTo(Circle o) {
return (this.radius - o.radius);
}
@Override
public String toString() {
return "x: " + xValue + " ---y: " + yValue + " ---radius: " + radius;
}
}

Secondly you are going to need the MergeSort class which also has the main method inside it so it can run the program. The class has static methods called merge and mergeSort that do all of the work. They basically keep splitting and sorting the array untill everything is sorted and then merges it all back together.

MergeSort.java

import java.util.Arrays;
import java.util.Random;

/**
* author: copypasteearth
* date: 7/17/2019
*/
public class MergeSort<T extends Comparable<T>> {

public static <T extends Comparable<T>> void merge(int leftFirst, int leftLast, int rightFirst, int rightLast, T[] array){
T[] tempArray = Arrays.copyOf(array,array.length);
int index = leftFirst;
int saveFirst = leftFirst;

while((leftFirst <= leftLast) && (rightFirst <= rightLast)){
if(array[leftFirst].compareTo(array[rightFirst]) < 0){
tempArray[index] = array[leftFirst];
leftFirst++;
}else{
tempArray[index] = array[rightFirst];
rightFirst++;
}
index++;
}
while(leftFirst <= leftLast){
tempArray[index] = array[leftFirst];
leftFirst++;
index++;
}
while(rightFirst <= rightLast){
tempArray[index] = array[rightFirst];
rightFirst++;
index++;
}
for(index = saveFirst; index <= rightLast;index++){
array[index] = tempArray[index];
}
}
public static <T extends Comparable<T>> void mergeSort(int first, int last,T[] array){
if(first < last){
int middle = (first + last) / 2;
mergeSort(first,middle,array);
mergeSort(middle+1,last,array);
merge(first,middle,middle+1,last,array);
}
}

public static void main(String[] args){
Circle[] circlearray = new Circle[20];
Random rand = new Random();
for (int index = 0; index < 20; index++)
{
circlearray[index] = new Circle();
circlearray[index].xValue = Math.abs(rand.nextInt()) % 100;
circlearray[index].yValue = Math.abs(rand.nextInt()) % 100;
circlearray[index].radius = Math.abs(rand.nextInt()) % 100;
}
System.out.println("Circle Array Unsorted....");
for(int i = 0;i < 20;i++){

System.out.println(circlearray[i]);
}
MergeSort<Circle> mscircle = new MergeSort<Circle>();
mscircle.mergeSort( 0, circlearray.length-1,circlearray);
System.out.println("Circle Array Sorted");
for(Circle i: circlearray) {
System.out.println(i);
}
}
}

And that pretty much sums it up for MergeSort. Another one of your should be favorited sorting algorithms that run at a whopping O(Nlog2N) complexity. Thanks for your time and i hope you liked this article and got some use out of it. I am leaving the Link to this and QuickSort on github here it is https://github.com/copypasteearth/Sorting

Dell 65W USB-C Laptop Charger for XPS and Latitude 5000 - Power Cord Included

(1545)

$22.99 (as of November 19, 2024 02:53 GMT -05:00 - )

Amazon Fire HD 10 Kids Pro tablet (newest model) ages 6-12 | Bright 10.1" HD screen | Slim case for older kids, ad-free content, parental controls, 13-hr battery, 32 GB, Nebula

(3828)

$189.99 (as of November 19, 2024 02:53 GMT -05:00 - )

Amazon Fire HD 10 Kids Pro tablet (newest model) ages 6-12 | Bright 10.1" HD screen | Slim case for older kids, ad-free content, parental controls, 13-hr battery, 32 GB, Happy Day

(3828)

$189.99 (as of November 19, 2024 02:53 GMT -05:00 - )

Amazon eero 6+ mesh wifi router (newest model) - Say goodbye to wifi dead spots, Coverage up to 4,500 sq. ft., Connect 75+ devices, 3-pack

(8290)

$194.99 (as of November 19, 2024 02:53 GMT -05:00 - )

TP-Link Deco AX3000 WiFi 6 Mesh System(Deco X55) - Covers up to 6500 Sq.Ft. , Replaces Wireless Router and Extender, 3 Gigabit ports per unit, supports Ethernet Backhaul (3-pack)

(11558)

$189.99 (as of November 19, 2024 02:53 GMT -05:00 - )

QuickSort sorting algorithm in java with Generics that implement Comparable

In this article I’m going to touch on the sorting algorithm called Quicksort. Its worst case time complexity is O(n^2) and its best case time complexity is O(nlogn). Firstly the method we are going to make is going to take a generic array and those elements should implement the Comparable interface so they can be sorted. Take this Circle class for example. When you implement the Comparable interface you specify in the compareTomethod what makes a circle greater than, less than, or equal to another circle. In this example we return whether the radius of the circle is bigger or smaller than the circle it is being compared to.

Circle.java

/**
 * author: copypasteearth
 * date: 7/17/2019
 */
public class Circle implements Comparable<Circle> {
    public int xValue;
    public int yValue;
    public int radius;

Next we create the Quicksort class that has the method quicksort and a main method to test out the quicksort method. The quicksort method is a recursive method and the base case is if(a < b). The method goes through the generic array and sorts the elements based on what the compareTo method tells it. Here is the Quicksort class.

Quicksort.java

/**
 * author: copypasteearth
 * date: 7/17/2019
 */
import java.util.Random;
public class QuickSort<T extends Comparable<T>> {

public static <T extends Comparable<T>> void quicksort(T[] array, int a, int b) {
if (a < b) {
int i = a, j = b;
T x = array[(i + j) / 2];

do {
while (array[i].compareTo(x) < 0) i++;
while (x.compareTo(array[j]) < 0) j--;

if ( i <= j) {
T tmp = array[i];
array[i] = array[j];
array[j] = tmp;
i++;
j--;
}

} while (i <= j);

quicksort(array, a, j);
quicksort(array, i, b);
}
}

public static void main(String[] args) {
Integer[] integerarray = {50, 55, 11, 89, 90, 1, 20, 11};
QuickSort<Integer> qsinteger = new QuickSort<Integer>();
qsinteger.quicksort(integerarray, 0, integerarray.length-1);
for(Integer i: integerarray) {
System.out.println(i);
}
String[] stringarray = {"bird","moth","apple","zebra","banana","desert","pig"};
QuickSort<String> qsstring = new QuickSort<String>();
qsstring.quicksort(stringarray, 0, stringarray.length-1);
for(String i: stringarray) {
System.out.println(i);
}
Circle[] circlearray = new Circle[20];
Random rand = new Random();
for (int index = 0; index < 20; index++)
{
circlearray[index] = new Circle();
circlearray[index].xValue = Math.abs(rand.nextInt()) % 100;
circlearray[index].yValue = Math.abs(rand.nextInt()) % 100;
circlearray[index].radius = Math.abs(rand.nextInt()) % 100;

}
System.out.println("Circle Array Unsorted....");
for(int i = 0;i < 20;i++){

System.out.println(circlearray[i]);
}
QuickSort<Circle> qscircle = new QuickSort<Circle>();
qscircle.quicksort(circlearray, 0, circlearray.length-1);
System.out.println("Circle Array Sorted");
for(Circle i: circlearray) {
System.out.println(i);
}

}

If you run this code you will see the results from the main method. First it sorts an Integer array and then a String array. Then it makes a Circle array and prints them out unsorted then it sorts them and then prints them out again sorted. That pretty much does it for this example on quicksorting. In the future I will probably go through the rest of the sorting algorithms. Hope you enjoyed it.

Donate or Subscribe to support Copypasteearth!!!!!

Your Donation

USD 1
USD 5
USD 10
USD 15
USD 20
USD 25
Custom amount

Full Name Email Phone Number

copypasteearth@gmail.com">

Charger for Lenovo Laptop Computer 65W 45W Round Tip Power Supply AC Adapter for Lenovo IdeaPad 330-14, 330-15, 330-17, 510-15, 330s-14, 330s-15 Lenovo Flex 6-14 Laptop Charger

(7679)

$9.90 (as of November 19, 2024 02:53 GMT -05:00 - )

Dell 65W USB-C Laptop Charger for XPS and Latitude 5000 - Power Cord Included

(1545)

$22.99 (as of November 19, 2024 02:53 GMT -05:00 - )

Charger for HP Laptop Computer 65W 45W Smart Blue Tip Power Adapter

(2390)

$9.90 (as of November 19, 2024 02:53 GMT -05:00 - )

NSPENCM 85W Mac Book Pro Charger, Replacement AC 85w 2T-Tip Connector Power Adapter,Laptop Charger Compatible with MacBook pro & Mac Book Pro 13 inch-15 inch Retina After Mid 2012

(4417)

$18.99 (as of November 19, 2024 02:53 GMT -05:00 - )

Mac Book Pro Charger - 118W USB C Charger Fast Charger Compatible with USB C Port MacBook pro/Air, ipad Pro, Samsung Galaxy and All USB C Device, Include Charge Cable

(4331)

$35.99 (as of November 19, 2024 02:53 GMT -05:00 - )

How to make a mouse maze in Java

This is the code to make a mouse maze with recursion using a stack and a list with a GUI in Java.

First we will make a Mouse class

Mouse.java

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Mouse {
public int x,y;
public Stack<Coordinate> decisions;
public List<Coordinate> solution;

public Mouse(int x, int y){
this.x = x;
this.y = y;
decisions = new Stack<Coordinate>();
solution = new ArrayList<Coordinate>();
}
}

Then we will make the coordinate class

Coordinate.java

public class Coordinate {
public int x,y;

public Coordinate(int x,int y){
this.x = x;
this.y = y;
}

@Override
public boolean equals(Object obj) {

boolean sameSame = false;
if (obj != null && obj instanceof Coordinate)
{
if(this.x == ((Coordinate)obj).x && this.y == ((Coordinate)obj).y){
sameSame = true;
}

}
return sameSame;
}
}

Now its time for the decision class

Decision.java

public class Decision {

public boolean up,down,left,right;
public int x,y;
public Decision(int x, int y){
up = down = left = right = false;
this.x = x;
this.y = y;
}
public Decision(boolean up,boolean down,boolean right,boolean left){
this.up = up;
this.down = down;
this.right = right;
this.left = left;
}
public void setLeft(boolean left){
this.left = left;
}
public void setRight(boolean right){
this.right = right;
}
public void setUp(boolean up){
this.up = up;
}
public void setDown(boolean down){
this.down = down;
}
@Override
public String toString() {
// TODO Auto-generated method stub
return x + " x -- y " + y;
}

}

Now we have to make the maze class which does most of the hard work

Maze.java

import java.awt.Color;
import java.awt.Graphics;
import java.awt.Rectangle;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.Random;
import javax.swing.JComponent;

public class Maze extends JComponent{
public char[][] maze = null;
public Rectangle[][] rects = null;
public boolean mousebool = false;
public boolean backtrack = false;
public Mouse mouse;
public Random random = new Random();
public Coordinate startingPoint;
public boolean first = true;
public boolean solv = true;
public int lastx,lasty;
public String navigation = "working!!!";

@Override
protected void paintComponent(Graphics g) {
super.paintComponent(g);

if(maze != null){
for(int i = 0;i < maze.length;i++){
for(int j = 0;j < maze[0].length;j++){
if(maze[i][j] == '1'){
g.setColor(Color.BLACK);
g.fillRect(rects[i][j].x, rects[i][j].y, rects[i][j].width, rects[i][j].height);
g.setColor(Color.WHITE);
g.drawRect(rects[i][j].x, rects[i][j].y, rects[i][j].width, rects[i][j].height);
}else if(maze[i][j] == '0'){
g.setColor(Color.white);
g.fillRect(rects[i][j].x, rects[i][j].y, rects[i][j].width, rects[i][j].height);
g.setColor(Color.BLACK);
g.drawRect(rects[i][j].x, rects[i][j].y, rects[i][j].width, rects[i][j].height);
}
}
}
if(mousebool){
g.setColor(Color.PINK);

g.fillOval(rects[mouse.x][mouse.y].x, rects[mouse.x][mouse.y].y, rects[mouse.x][mouse.y].width, rects[mouse.x][mouse.y].height);
}
}

}
public void setMaze(char[][] maze){
mousebool = false;
this.maze = maze;
rects = new Rectangle[maze.length][maze[0].length];
for(int i = 0;i < rects.length;i++){
for(int j = 0;j < rects[0].length;j++){
rects[i][j] = new Rectangle(i * (getWidth()/rects.length),j * (getHeight()/rects[0].length)
,getWidth()/rects.length,getHeight()/rects[0].length);
}
}
repaint();
}
public void setMouse(int x,int y){
mousebool = true;
mouse = new Mouse(x,y);
startingPoint = new Coordinate(x,y);
mouse.solution.add(new Coordinate(x,y));
mouse.decisions.push(new Coordinate(x,y));
first = true;

repaint();
}
public void solve(){

if(mouse.x > 0 && mouse.x < maze.length - 1 && mouse.y > 0 && mouse.y < maze[0].length - 1 && mouse.decisions.size() > 0){

//System.out.println(wasHere(coord) + "now");
//north
System.out.println(wasHere(new Coordinate(mouse.x,mouse.y - 1)) + "north");
if (!(maze[mouse.x][mouse.y - 1] == '1') && !wasHere(new Coordinate(mouse.x,mouse.y - 1))) mouse.decisions.push(new Coordinate(mouse.x,mouse.y - 1));
//east
System.out.println(wasHere(new Coordinate(mouse.x + 1,mouse.y)) + "east");
if (!(maze[mouse.x + 1][mouse.y] == '1') && !wasHere(new Coordinate(mouse.x + 1,mouse.y))) mouse.decisions.push(new Coordinate(mouse.x + 1,mouse.y));
//west
if (!(maze[mouse.x - 1][mouse.y] == '1') && !wasHere(new Coordinate(mouse.x - 1,mouse.y))) mouse.decisions.push(new Coordinate(mouse.x - 1,mouse.y));
//south
if(!(maze[mouse.x][mouse.y + 1] == '1') && !wasHere(new Coordinate(mouse.x,mouse.y + 1))) mouse.decisions.push(new Coordinate(mouse.x,mouse.y + 1));

Coordinate coord = mouse.decisions.pop();

mouse.x = coord.x;
mouse.y = coord.y;

mouse.solution.add(coord);

ActionListener taskPerformer = new ActionListener() {

@Override
public void actionPerformed(ActionEvent arg0) {
solve();

}
};
javax.swing.Timer t = new javax.swing.Timer( 250, taskPerformer);
t.setRepeats(false);
t.start();
//solve();

repaint();
}else{
solv = false;
if(mouse.decisions.size() == 0){
mouse.solution.clear();
navigation = "there is no solution";
}else{
mouse.solution.clear();
findPath(startingPoint.x,startingPoint.y);
navigation = "maze complete";
}
}

//solve();
}
public boolean findPath(int x,int y){
if(x < 0 || y < 0 || x > maze.length - 1 || y > maze[0].length - 1)return false;

if(!(x > 0 && x < maze.length - 1 && y > 0 && y < maze[0].length - 1) && maze[x][y] == '0')
{
mouse.solution.add(new Coordinate(x,y));
return true;// && maze[x][y] == '0') return true;//&& maze[x][y] == '0') return true;
}
if(maze[x][y] == '1') return false;

mouse.solution.add(new Coordinate(x,y));
if(!mouse.solution.contains(new Coordinate(x,y - 1)))
if(findPath(x,y-1) == true) return true;
if(!mouse.solution.contains(new Coordinate(x+1,y)))
if(findPath(x + 1,y) == true) return true;
if(!mouse.solution.contains(new Coordinate(x,y+1)))
if(findPath(x,y + 1)== true) return true;
if(!mouse.solution.contains(new Coordinate(x-1,y)))
if(findPath(x - 1,y)== true) return true;
mouse.solution.remove(new Coordinate(x,y));
return false;
}

public boolean wasHere(Coordinate coord){
return mouse.solution.contains(coord);
}
public void TraverseMouse(int x){
if(x < mouse.solution.size()){
Coordinate coord = mouse.solution.get(x);
mouse.x = coord.x;
mouse.y = coord.y;
final int xt = x+=1;
ActionListener taskPerformer = new ActionListener() {

@Override
public void actionPerformed(ActionEvent arg0) {
TraverseMouse(xt);

}
};
javax.swing.Timer t = new javax.swing.Timer( 250, taskPerformer);
t.setRepeats(false);
t.start();
}
repaint();

}
public String Navigation(){
return navigation;
}
}

And finally the Main class to make the GUI

Main.java

import java.awt.BorderLayout;
import java.awt.Container;
import java.awt.Toolkit;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import javax.swing.JButton;
import javax.swing.JFileChooser;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JPanel;
import javax.swing.JTextField;
import javax.swing.SwingUtilities;
import javax.swing.UIManager;
import javax.swing.filechooser.FileNameExtensionFilter;

public class Main {
public static int width;
public static int height;
public static char[][] maze1;
public static void main(String[] args) {
try {
UIManager.setLookAndFeel(UIManager.getSystemLookAndFeelClassName());
}catch(Exception ex) {
ex.printStackTrace();
}

SwingUtilities.invokeLater(new Runnable() {
public void run() {
create();
}
});

}
public static void create(){
JFrame frame = new JFrame("Mouse Maze");
final Maze maze = new Maze();
frame.setSize(500, 500);
frame.setLocation((int)(Toolkit.getDefaultToolkit().getScreenSize().getWidth()/2)-264,
(int)(Toolkit.getDefaultToolkit().getScreenSize().getHeight()/2)-330);
maze.setSize(400, 400);
Container content = frame.getContentPane();
//Creates a new container
content.setLayout(new BorderLayout());

frame.add(maze,BorderLayout.CENTER);
//frame.add(maze);
JPanel panel = new JPanel(new BorderLayout());
JPanel panel1 = new JPanel(new BorderLayout());
JPanel panel2 = new JPanel(new BorderLayout());
JPanel finish = new JPanel(new BorderLayout());
final JLabel textFile = new JLabel(" ex: maze.txt ");
JButton pickFile = new JButton("Pick file");
pickFile.addActionListener(new ActionListener(){

@Override
public void actionPerformed(ActionEvent arg0) {
// TODO Auto-generated method stub
JFileChooser chooser = new JFileChooser();
FileNameExtensionFilter filter = new FileNameExtensionFilter(
".txt file", "txt");
chooser.setFileFilter(filter);

int returnVal = chooser.showOpenDialog(null);
if(returnVal == JFileChooser.APPROVE_OPTION) {
try {
BufferedReader read = new BufferedReader(new FileReader(chooser.getSelectedFile()));
String rea = read.readLine();
String[] split = rea.split(" ");
width = Integer.valueOf(split[0]);
height = Integer.valueOf(split[1]);

String readline;
int num = 0;
maze1 = new char[width][height];
while((readline = read.readLine()) != null){
char[] ch = readline.toCharArray();
for(int i = 0;i < ch.length;i++){
maze1[i][num] = ch[i];
}
num++;
}
maze.setMaze(maze1);
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
textFile.setText(chooser.getSelectedFile().getName());
}else{

}
}

});

panel.add(pickFile,BorderLayout.CENTER);
panel.add(textFile,BorderLayout.WEST);
JButton setMouse = new JButton("Set Mouse");
final JTextField mouseText = new JTextField("x,y",15);
JButton solve = new JButton("SOLVE");
JButton traverse = new JButton("TRAVERSE");
final JLabel error = new JLabel("ERROR MESSAGES!!!!");
panel2.add(solve,BorderLayout.NORTH);
panel2.add(traverse,BorderLayout.CENTER);
panel2.add(error,BorderLayout.SOUTH);
panel1.add(setMouse,BorderLayout.CENTER);
panel1.add(mouseText,BorderLayout.WEST);
finish.add(panel,BorderLayout.NORTH);
finish.add(panel1,BorderLayout.CENTER);
finish.add(panel2,BorderLayout.SOUTH);
//content.setLayout(new BorderLayout());
content.add(finish, BorderLayout.SOUTH);
traverse.addActionListener(new ActionListener(){

@Override
public void actionPerformed(ActionEvent e) {
// TODO Auto-generated method stub
maze.TraverseMouse(0);
}

});
solve.addActionListener(new ActionListener(){

@Override
public void actionPerformed(ActionEvent arg0) {
// TODO Auto-generated method stub

maze.solve();

error.setText(maze.navigation);

}

});
setMouse.addActionListener(new ActionListener(){

@Override
public void actionPerformed(ActionEvent arg0) {
String mousePosition = mouseText.getText();
String[] splitposition = mousePosition.split(",");
try{
int x = Integer.valueOf(splitposition[0]);
int y = Integer.valueOf(splitposition[1]);
if(x >= width || y >= height){
error.setText("those coordinates are not in range of your maze, try again, 0-"+ (width - 1)+",0-"+(height-1));
}else if(maze1[x][y] == '1'){
error.setText("you cannot place the mouse on a wall, try again");
}else{
maze.setMouse(x, y);
error.setText("coordinates set.");
}
}catch(NumberFormatException e){
error.setText("You Must enter the mouse position \"x,y\" example: 10,20");
}catch(ArrayIndexOutOfBoundsException e){
e.printStackTrace();
error.setText("You Must enter the mouse position \"x,y\" example: 10,20");
}

}

});

//frame.add(panel);

frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
//makes it so you can close
frame.setVisible(true);
//char[][] ch = new char[][]{{'1','1','1','1'},{'1','0','0','1'},{'1','0','0','1'},{'1','1','1','1'}};
//maze.setMaze(ch);
}

}

You will have to use a text file in this format where a 1 is a wall and a 0 is part of the path remember .txt file the first line means 10 width and 5 height for the maze

You can try it and alter it to your own code, thanks for reading.

Donate or Subscribe to support Copypasteearth!!!!!

Apple 2024 MacBook Pro Laptop with M4 chip with 10‑core CPU and 10‑core GPU: Built for Apple Intelligence, 14.2-inch Liquid Retina XDR Display, 16GB Unified Memory, 512GB SSD Storage; Space Black

(4)

$1,567.19 (as of November 19, 2024 02:53 GMT -05:00 - )

Mac Book Pro Charger - 118W USB C Charger Fast Charger Compatible with USB C Port MacBook pro/Air, ipad Pro, Samsung Galaxy and All USB C Device, Include Charge Cable

(4331)

$35.99 (as of November 19, 2024 02:53 GMT -05:00 - )

Amazon eero 6+ mesh wifi router (newest model) - Say goodbye to wifi dead spots, Coverage up to 4,500 sq. ft., Connect 75+ devices, 3-pack

(8290)

$194.99 (as of November 19, 2024 02:53 GMT -05:00 - )

65W USB C Laptop Charger Replacement for Lenovo Thinkpad/Yoga/Chromebook, ADLX65YDC2A Lenovo Laptop Charger

(1304)

$16.99 (as of November 19, 2024 02:53 GMT -05:00 - )

Amazon Fire HD 10 Kids Pro tablet (newest model) ages 6-12 | Bright 10.1" HD screen | Slim case for older kids, ad-free content, parental controls, 13-hr battery, 32 GB, Happy Day

(3828)

$189.99 (as of November 19, 2024 02:53 GMT -05:00 - )

How to Implement a Stack in Java

If you are a computer science major when you take Data Structures and Algorithms you are going to have to learn about a Stack. Java has a built in Stack class that you can use so you would probably never have to implement your own. In this example we will start with the Stack interface to formally define how our stack will be implemented.

Stack.java


/**
*
* @author Copypasteearth
*interface for the Stack implementation
* @param <T>
* generic parameter T
*/
public interface Stack<T>
{
/*
* push element onto the top of the stack
* @element
* the item to be pushed onto the top of the stack
*
*/
public void push(T element);
/**
* removes the top element from the stack and returns it
* @throws
* throws stackunderflowexception if the stack is empty
* @return
* returns T element
*/
public T pop();
/**
* lets you see the current top element of the stack without removing it
* @throws
* throws stackunderflowexception if the stack is empty
* @return
* returns T element (the top of the stack)
*/
public T top();
/**
* checks to see if the stack is empty
* @return
* returns true if the stack is empty, false otherwise
*/
public boolean isEmpty();
/**
* gets the size of the stack
* @return
* returns an integer representing how many items are on the stack
*/
public int getSize();

}

Next we will need a class that holds our information so we define the Node class to hold the data and a reference to the next Node in the stack.

Node.java


/**
*
* @author Copypasteearth
* Node class used to dynamically keep track of
* elements on the stack
*/
public class Node<T> {

/** holds the reference to Object of the node*/
public T data;
/** holds the reference to next node of the stack*/
public Node<T> next;
/**
*
* @param element
* element to be placed in data variable of Node
* @param next
* Node to be placed in next variable of Node
*/
public Node(T element,Node<T> next) {

this.data = element;
this.next = next;

}

}

Now we will define an Exception just incase someone trys to access the top of the stack and it is empty.

StackUnderflowException.java


/**
*
* @author Copypasteearth
* StackUnderflowException to be thrown when the
* stack tries to perform a getter method on an empty stack
*/
public class StackUnderflowException extends RuntimeException {

public StackUnderflowException() {
super();
// TODO Auto-generated constructor stub
}

public StackUnderflowException(String arg0) {
super(arg0);
// TODO Auto-generated constructor stub
}

public StackUnderflowException(Throwable arg0) {
super(arg0);
// TODO Auto-generated constructor stub
}

public StackUnderflowException(String arg0, Throwable arg1) {
super(arg0, arg1);
// TODO Auto-generated constructor stub
}

public StackUnderflowException(String arg0, Throwable arg1, boolean arg2,
boolean arg3) {
super(arg0, arg1, arg2, arg3);
// TODO Auto-generated constructor stub
}

}

And finally here is the implementation of the Stack interface, in a class called UnboundedStackImplementation.

UnboundedStackImplementation.java


/**
* @author Copypasteearth
*
* UnboundedStackImplementation is the version of a Stack
* created with the Stack interface dynamically creating
* instances of Node class to keep references to elements
* in the stack
*/
public class UnboundedStackImplementation<T> implements Stack<T> {

/** the count of how many elements are in the stack */
private int count;
/** the reference to the element on the top of the stack */
private Node<T> top;

/**
* constructor sets values of top and count and returns an
* instance of UnboundedStackImplementation
*/
public UnboundedStackImplementation()
{
this.count = 0;
this.top = null;
}

/*
* push element onto the top of the stack
* @element
* the item to be pushed onto the top of the stack
*
*/
@Override
public void push(T element) {

//create new node with element as data and top as next
Node<T> currentNode = new Node<T>(element,top);
//set top to the new node
top = currentNode;
//increment count
count++;


}

/**
* removes the top element from the stack and returns it
* @throws
* throws stackunderflowexception if the stack is empty
* @return
* returns T element
*/
@Override
public T pop() {
//get T with top method, may throw StackUnderflowException
T result = top();
//set top data to null
top.data = null;
//set top to the top next node
top = top.next;
//decrement count
count--;
return result;

}

/**
* lets you see the current top element of the stack without removing it
* @throws
* throws stackunderflowexception if the stack is empty
* @return
* returns T element (the top of the stack)
*/
@Override
public T top() {

//prepare result T to be returned by top
T result = null;
// if stack is not empty
if(!isEmpty()){
//set result to top variable data
result = top.data;
}else{
// if stack is empty there is no data to be returned
throw new StackUnderflowException("StackUnderflowException -- The Stack is empty!!!");
}

return result;
}

/**
* checks to see if the stack is empty
* @return
* returns true if the stack is empty, false otherwise
*/
@Override
public boolean isEmpty() {
if(top == null)
return true;
else
return false;
}

/**
* gets the size of the stack
* @return
* returns an integer representing how many items are on the stack
*/
@Override
public int getSize() {

return count;
}

}

And that’s it, I hope you appreciate this little demonstration about the data structure that is very commonly used in practice. There are a ton of different data structures to choose from and some are better in certain situations than others.

Tag: Java

Merge Sort algorithm with Generics that implement Comparable interface

Dell 65W USB-C Laptop Charger for XPS and Latitude 5000 - Power Cord Included

Amazon Fire HD 10 Kids Pro tablet (newest model) ages 6-12 | Bright 10.1" HD screen | Slim case for older kids, ad-free content, parental controls, 13-hr battery, 32 GB, Nebula

Amazon Fire HD 10 Kids Pro tablet (newest model) ages 6-12 | Bright 10.1" HD screen | Slim case for older kids, ad-free content, parental controls, 13-hr battery, 32 GB, Happy Day

Amazon eero 6+ mesh wifi router (newest model) - Say goodbye to wifi dead spots, Coverage up to 4,500 sq. ft., Connect 75+ devices, 3-pack

TP-Link Deco AX3000 WiFi 6 Mesh System(Deco X55) - Covers up to 6500 Sq.Ft. , Replaces Wireless Router and Extender, 3 Gigabit ports per unit, supports Ethernet Backhaul (3-pack)

Like this:

QuickSort sorting algorithm in java with Generics that implement Comparable

Charger for Lenovo Laptop Computer 65W 45W Round Tip Power Supply AC Adapter for Lenovo IdeaPad 330-14, 330-15, 330-17, 510-15, 330s-14, 330s-15 Lenovo Flex 6-14 Laptop Charger

Dell 65W USB-C Laptop Charger for XPS and Latitude 5000 - Power Cord Included

Charger for HP Laptop Computer 65W 45W Smart Blue Tip Power Adapter

NSPENCM 85W Mac Book Pro Charger, Replacement AC 85w 2T-Tip Connector Power Adapter,Laptop Charger Compatible with MacBook pro & Mac Book Pro 13 inch-15 inch Retina After Mid 2012

Mac Book Pro Charger - 118W USB C Charger Fast Charger Compatible with USB C Port MacBook pro/Air, ipad Pro, Samsung Galaxy and All USB C Device, Include Charge Cable

Like this:

How to make a mouse maze in Java

Apple 2024 MacBook Pro Laptop with M4 chip with 10‑core CPU and 10‑core GPU: Built for Apple Intelligence, 14.2-inch Liquid Retina XDR Display, 16GB Unified Memory, 512GB SSD Storage; Space Black

Mac Book Pro Charger - 118W USB C Charger Fast Charger Compatible with USB C Port MacBook pro/Air, ipad Pro, Samsung Galaxy and All USB C Device, Include Charge Cable

Amazon eero 6+ mesh wifi router (newest model) - Say goodbye to wifi dead spots, Coverage up to 4,500 sq. ft., Connect 75+ devices, 3-pack

65W USB C Laptop Charger Replacement for Lenovo Thinkpad/Yoga/Chromebook, ADLX65YDC2A Lenovo Laptop Charger

Amazon Fire HD 10 Kids Pro tablet (newest model) ages 6-12 | Bright 10.1" HD screen | Slim case for older kids, ad-free content, parental controls, 13-hr battery, 32 GB, Happy Day

Like this:

How to Implement a Stack in Java

Like this:

Share this:

Like this:

Share this:

Like this:

Share this:

Like this:

Share this:

Like this: