In this example, we will see how to implement the stack using array. Source from: https://www.youtube.com/watch?v=0XL1NBUv2NU&t=4965s
Person
public class Person {
private String name;
private String rollNo;
public Person(String name, String rollNo) {
super();
this.name = name;
this.rollNo = rollNo;
}
public String getName() {
return name;
}
@Override
public String toString() {
return "Person [name=" + name + ", rollNo=" + rollNo + "]";
}
}Stack
package com.example.hackerank;
public class IntStack {
private int[] stack;
private int top;
private int size;
public IntStack() {
this.stack = new int[50];
this.top = -1;
this.size = 50;
}
public IntStack(int size) {
this.stack = new int[size];
this.top = -1;
this.size = size;
}
// Add elements to stack
public boolean push(int item) {
if(!isFull()){
top++;
stack[top] = item;
return true;
}
return false;
}
//remove from stack
public int pop(){
return stack[top--];
}
public boolean isFull() {
return top == stack.length - 1;
}
public static void main(String[] args) {
IntStack intStack = new IntStack();
if(!intStack.isFull()){
intStack.push(2);
intStack.push(4);
intStack.push(6);
intStack.push(8);
intStack.push(9);
}
System.out.println(intStack.pop());
System.out.println(intStack.pop());
System.out.println(intStack.pop());
}
}Using Object
package com.example.hackerank;
public class PersonStack {
public static class Person {
private String name;
private String rollNo;
public Person(String name, String rollNo) {
this.name = name;
this.rollNo = rollNo;
}
@Override
public String toString() {
return "Name: " + this.name + ", Roll No: " + this.rollNo;
}
}
private Person[] stack;
private int top;
private int size;
public PersonStack() {
this.stack = new Person[50];
this.top = -1;
this.size = 50;
}
public PersonStack(int size) {
this.stack = new Person[size];
this.top = -1;
this.size = size;
}
public boolean push(Person item) {
if(!isFull()){
top++;
stack[top] = item;
return true;
}
return false;
}
public Person pop(){
return stack[top--];
}
public boolean isFull() {
return top == stack.length - 1;
}
public static void main(String[] args) {
Person person1 = new Person("Deepa", "Dekate");
Person person2 = new Person("Neha", "Parate");
Person person3 = new Person("Laxmi", "Ninawe");
PersonStack personStack = new PersonStack();
personStack.push(person1);
personStack.push(person2);
personStack.push(person3);
System.out.println(personStack.pop().toString());
System.out.println(personStack.pop().toString());
System.out.println(personStack);
}
}— — — — — — — — — — — — — — — — — — — —
Queue
public class IntQueue {
private int[] queue;
private int size;
private int total;
private int front;
private int rear;
public IntQueue() {
this.queue = new int[100];
this.size = 100;
this.total = 0;
this.front = 0;
this.rear = 0;
}
public IntQueue(int size) {
this.queue = new int[size];
this.size = 100;
this.total = 0;
this.front = 0;
this.rear = 0;
}
public boolean enqueue(int item) {
if (isFull()) {
return false;
} else {
total++;
queue[rear] = item;
rear = (rear + 1) % size;
return true;
}
}
public int dequeue() {
int item = queue[front];
total--;
front = (front + 1) % size;
return item;
}
public boolean isFull() {
if (size == total) {
return true;
} else {
return false;
}
}
public void showAll(){
int f = front;
if(total != 0){
for (int i = 0; i < total; i++) {
System.out.println(" "+queue[front]);
front = (front + 1) % size;
}
}
}
public static void main(String[] args) {
IntQueue intQueue = new IntQueue();
intQueue.enqueue(3);
intQueue.enqueue(4);
intQueue.enqueue(6);
intQueue.enqueue(8);
intQueue.showAll();
System.out.println(intQueue.dequeue());
}
}PersonQueue.java
public class PersonQueue {
private Person[] queue;
private int size;
private int total;
private int front;
private int rear;
public PersonQueue() {
this.queue = new Person[100];
this.size = 100;
this.total = 0;
this.front = 0;
this.rear = 0;
}
public PersonQueue(int size) {
this.queue = new Person[size];
this.size = 100;
this.total = 0;
this.front = 0;
this.rear = 0;
}
public boolean enqueue(Person item) {
if (isFull()) {
return false;
} else {
total++;
queue[rear] = item;
rear = (rear + 1) % size;
return true;
}
}
public Person dequeue() {
Person item = queue[front];
total--;
front = (front + 1) % size;
return item;
}
public boolean isFull() {
if (size == total) {
return true;
} else {
return false;
}
}
public void showAll(){
int f = front;
if(total != 0){
for (int i = 0; i < total; i++) {
System.out.println(" "+queue[front]);
front = (front + 1) % size;
}
}
}
public static void main(String[] args) {
PersonQueue personQueue = new PersonQueue();
personQueue.enqueue(new Person("Karan", "Nimje"));
personQueue.enqueue(new Person("Ankita", "Paunikar"));
personQueue.enqueue(new Person("Pallavi", "Mohadikat"));
personQueue.showAll();
}
}— — — — -
Single LinkedList
public class IntLinkedList {
private Node head;
public IntLinkedList(int item) {
head = new Node();
head.data = item;
head.link = null;
}
public boolean insertItem(int item) {
Node node = new Node();
node.data = item;
node.link = head;
head = node;
return true;
}
public void printList() {
Node z = head;
while (z != null) {
System.out.println(z.data);
z = z.link;
}
}
class Node {
private int data;
private Node link;
}
public boolean deleteItem(int item) {
if (head.data == item) {
head = head.link;
return true;
} else {
Node x = head;
Node y = head.link;
while (true) {
if (y == null || y.data == item) {
break;
} else {
x = y;
y = y.link;
}
}
if (y != null) {
x.link = y.link;
return true;
}else{
return false;
}
}
}
public static void main(String[] args) {
IntLinkedList list = new IntLinkedList(4);
list.insertItem(5);
list.insertItem(7);
list.insertItem(9);
list.insertItem(10);
list.printList();
list.deleteItem(5);
System.out.println("---- After Delete ----");
list.printList();
}
}Using
public class IntLinkedList {
private Node head;
public IntLinkedList() {
head = new Node();
head.value = 0;
head.link = null;
}
public boolean insertItem(int item) {
Node n = new Node();
Node new_node;
new_node = head;
while (new_node.link != null) {
new_node = new_node.link;
}
n.value = item;
n.link = null;
new_node.link = n;
return true;
}
public void printList() {
Node z = head;
while (z != null) {
System.out.println(z.value);
z = z.link;
}
}
class Node {
private int value;
private Node link;
}
public boolean deleteItem(int item) {
if (head.value == item) {
head = head.link;
return true;
} else {
Node x = head;
Node y = head.link;
while (true) {
if (y == null || y.value == item) {
break;
} else {
x = y;
y = y.link;
}
}
if (y != null) {
x.link = y.link;
return true;
}else{
return false;
}
}
}
public void sortList() {
int c = 0;
Node a = head.link;
while (a.link != null) {
Node b = head.link;
while (b.link != null) {
if(b.value < b.link.value) {
c = b.value;
b.value = b.link.value;
b.link.value = c;
}
b = b.link;
}
a = a.link;
}
}
public static void main(String[] args) {
IntLinkedList list = new IntLinkedList();
list.insertItem(7);
list.insertItem(5);
list.insertItem(9);
list.printList();
list.sortList();
System.out.println();
list.printList();
list.sortList();
}
}— — — — -
public class PersonLinkedList {
class Node {
private Person person;
private Node link;
}
private Node head;
public PersonLinkedList(Person person) {
head = new Node();
head.person = person;
head.link = null;
}
public boolean insertItem(Person person) {
Node n = new Node();
Node new_node = head;
while (new_node.link != null) {
new_node = new_node.link;
}
n.person = person;
n.link = null;
new_node.link = n;
return true;
}
public void printList() {
Node z = head;
while (z != null) {
System.out.println(z.person.toString());
z = z.link;
}
}
public boolean deleteItem(String name) {
if(name.equals(head.person.getName())) {
head = head.link;
return true;
}else {
Node x = head;
Node y = head.link;
while (y != null && !(y.person.getName().equals(name) )) {
x = y;
y = y.link;
}
if(y != null) {
x.link = y.link;
return true;
}else {
return false;
}
}
}
public void sortList() {
int c = 0;
// Node a = head.link;
// while (a.link != null) {
// Node b = head.link;
// while (b.link != null) {
// if(b.)
// }
// }
}
public static void main(String[] args) {
Person person1 = new Person("John", "11");
Person person2 = new Person("Jane", "12");
PersonLinkedList list = new PersonLinkedList(person1);
list.insertItem(person2);
list.printList();
}
}— — — — —
Doubly LinkedList
public class dList {
private Node head;
class Node {
private Node prev;
private int value;
private Node next;
}
public dList(int item) {
head = new Node();
head.value = item;
head.next = null;
head.prev = null;
}
public boolean insertItem(int item) {
Node n = new Node();
n.value = item;
n.prev = null;
head.prev = n;
n.next = head;
head = n;
return true;
}
public void printList() {
Node z = head.next;
while (z != null) {
System.out.println(z.value);
z = z.next;
}
}
public boolean deleteItem(int item) {
if (head.value == item) {
head = head.next;
return true;
} else {
Node x = head;
Node y = head.next;
while (true) {
if (y == null || y.value == item) {
break;
} else {
x = y;
y = y.next;
}
}
if (y != null) {
x.next = y.next;
return true;
} else {
return false;
}
}
}
public static void main(String[] args) {
dList list = new dList(2);
list.insertItem(3);
list.insertItem(6);
list.printList();
System.out.println();
list.deleteItem(3);
list.printList();
}
}— — — — — — — -
Binary Search Tree —
package com.bookstore.service;
public class BST {
class Node {
private Node lc;
private Person data;
private Node rc;
}
private Node root;
public BST() {
root = null;
}
public boolean insert(Person item) {
Node n = new Node();
n.data = item;
n.lc = null;
n.rc = null;
if (root == null) {
root = n;
return true;
}
Node p = root;
Node c = root;
while (c != null) {
p = c;
if (item.getName().compareTo(c.data.getName()) < 0) {
c = c.lc;
} else {
c = c.rc;
}
}
if (item.getName().compareTo(p.data.getName()) < 0) {
p.lc = n;
} else {
p.rc = n;
}
return true;
}
public Node findNode(String key) {
Node c = root;
while (c != null) {
if (key.compareTo(c.data.getName()) == 0) {
break;
} else if (key.compareTo(c.data.getName()) < 0) {
c = c.lc;
} else {
c = c.rc;
}
}
return c;
}
public Node findParent(String key) {
Node p = root;
Node c = root;
do {
if (key.compareTo(c.data.getName()) == 0) {
break;
}
p = c;
if (key.compareTo(c.data.getName()) < 0) {
c = c.lc;
} else {
c = c.rc;
}
} while (c != null);
System.out.println(">> " + p.data.getName());
if (c != null) {
return p;
} else {
return null;
}
}
public Person getData(Node n) {
return n.data;
}
public void showAll(Node n) {
Node p = n;
if (p != null) {
System.out.println(" " + p.data);
showAll(p.lc);
showAll(p.rc);
}
}
public static void main(String[] args) {
Person p1 = new Person("John", 20);
Person p2 = new Person("Neha", 21);
Person p3 = new Person("Jane", 22);
Person p4 = new Person("Adam", 23);
Person p5 = new Person("Matt", 24);
BST bst = new BST();
bst.insert(p1);
bst.insert(p2);
bst.insert(p3);
bst.insert(p4);
bst.insert(p5);
bst.showAll(bst.findNode("John"));
System.out.println("----------------------------------");
Person adam = bst.getData(bst.findParent("Jane"));
System.out.println(adam.toString());
}
}=============================
Find the missing element from the integer array.
package com.example;
public class FindMissingElement {
public static void main(String[] args) {
int[] a = {6, 4, 1, 3, 2};
System.out.println(findMissingNumbers(a));
}
private static int findMissingNumbers(int[] num) {
int length = num.length;
int sum = ((length + 1) * (length + 2)) / 2;
System.out.println("sum "+ sum);
for (int i = 0; i < length; i++) {
sum = sum - num[i];
System.out.println("new Sum : "+ sum);
}
return sum;
}
}Find Palindrome
package com.example;
public class Palindrome {
public static void main(String[] args) {
String value = "Nitin".toLowerCase();
int length = value.length();
boolean isPalindrome = true;
for (int i = 0; i < length / 2; i++) {
if (value.charAt(i) != value.charAt(length - 1 - i)) {
isPalindrome = false;
break;
}
}
if (isPalindrome)
System.out.println("Palindrome");
else
System.out.println("Not Palindrome");
}
}
