Δομές δεδομένων σε Java |  Οδηγός για αρχάριους |2023

Δομές δεδομένων σε Java | Οδηγός για αρχάριους |2023

November 21, 2022 0 Von admin

Οι δομές δεδομένων είναι θεμελιώδεις για οποιαδήποτε γλώσσα προγραμματισμού. Η επιλογή μιας συγκεκριμένης δομής δεδομένων έχει σημαντικό αντίκτυπο στη λειτουργικότητα και την απόδοση των εφαρμογών Java, επομένως αξίζει τον κόπο να κυριαρχήσετε τις δομές δεδομένων σε Java.

Αυτός ο οδηγός θα βοηθήσει τους αρχάριους να κατανοήσουν τι είναι δομές δεδομένων, τι είναι δομές δεδομένων στην Java, τους τύπους δομών δεδομένων σε Java και πολλά άλλα.

Τι είναι η Java;

Ο προγραμματισμός Java είναι μια γλώσσα προγραμματισμού υψηλού επιπέδου που δημιουργήθηκε από μικροσυστήματα Sun. Αυτή η γλώσσα προγραμματισμού είναι αξιόπιστη, αντικειμενοστραφής και ασφαλής. Η Java ακολουθεί την αρχή WORA, η οποία σημαίνει „Γράψτε μια φορά να τρέξετε οπουδήποτε“. Μπορείτε να εκτελέσετε ένα πρόγραμμα java όσες φορές θέλετε σε μια πλατφόρμα που υποστηρίζει java μετά τη μεταγλώττιση του.

Τι είναι οι Δομές Δεδομένων;

Μια δομή δεδομένων ορίζεται ως μια μορφή για τακτοποίηση, επεξεργασία, πρόσβαση και αποθήκευση δεδομένων. Οι δομές δεδομένων είναι ο συνδυασμός απλών και πολύπλοκων μορφών, οι οποίες είναι φτιαγμένες για την οργάνωση δεδομένων για μια συγκεκριμένη χρήση. Οι χρήστες βρίσκουν απλό την πρόσβαση στα δεδομένα που χρειάζονται και τα χρησιμοποιούν κατάλληλα χάρη στις δομές δεδομένων.

Για να καταλάβετε με απλούστερους όρους, δείτε το παρακάτω παράδειγμα

If you want to store data in

One on the other - Stacks
Linear fashion - Array/ Linked List
Hierarchical Fashion - Trees
Connect Nodes - Graph

Τι είναι οι δομές δεδομένων στην Java;

Η δομή δεδομένων στη java ορίζεται ως η συλλογή τεμαχίων δεδομένων που προσφέρει ένα αποτελεσματικό μέσο αποθήκευσης και οργάνωσης δεδομένων σε έναν υπολογιστή. Η συνδεδεμένη λίστα, η στοίβα, η ουρά και οι πίνακες είναι μερικά παραδείγματα δομών δεδομένων java.

Τύποι Δομών Δεδομένων σε Java

Ακολουθεί η λίστα μερικών από τους κοινούς τύπους δομών δεδομένων στην Java:

  • Πίνακας
  • Συνδεδεμένη λίστα
  • Σωρός
  • Ουρά
  • Δυαδικό δέντρο
  • Δυαδικό δέντρο αναζήτησης
  • Σωρός
  • Κατακερματισμός
  • Γραφική παράσταση

Εδώ είναι η εικονογραφική αναπαράσταση τύπων δομών δεδομένων java

Δομές δεδομένων σε Java
To learn more about Java Programming, you can take up a free online course offered by Great Learning Academy and upskill today. If you are already well-versed with the basics, go ahead and enrol yourself in the Data Structure & Algorithms in Java for Intermediate Level.

Περαιτέρω ταξινόμηση τύπων Δομών Δεδομένων

Υπάρχουν δύο τύποι Δομών Δεδομένων:

  1. Πρωτόγονες Δομές Δεδομένων
  2. Μη πρωτόγονες Δομές Δεδομένων

Πρωτόγονες Δομές Δεδομένων ονομάζονται επίσης Πρωτόγονοι τύποι δεδομένων. byte, short, int, float, char, boolean, long και double είναι πρωτόγονοι τύποι δεδομένων.

Μη πρωτόγονες δομές δεδομένων – Οι μη πρωτόγονες δομές δεδομένων είναι δύο τύπων:

  1. Γραμμικές Δομές Δεδομένων
  2. Μη γραμμικές Δομές Δεδομένων
Μη πρωτόγονες δομές δεδομένων σε java

Γραμμικές Δομές Δεδομένων – Τα στοιχεία που είναι διατεταγμένα με γραμμικό τρόπο ονομάζονται Γραμμικές Δομές Δεδομένων. Εδώ, κάθε στοιχείο συνδέεται μόνο με ένα άλλο στοιχείο. Οι γραμμικές δομές δεδομένων είναι οι εξής:

  • Πίνακες
    • Μονοδιάστατος πίνακας
    • Πολυδιάστατος πίνακας
  • Συνδεδεμένη λίστα
    • Λίστα μεμονωμένα
    • Λίστα διπλά συνδεδεμένη
    • Κυκλική συνδεδεμένη λίστα

Μη Γραμμικές Δομές Δεδομένων – Τα στοιχεία που είναι διατεταγμένα με μη γραμμικό τρόπο ονομάζονται Μη Γραμμικές Δομές Δεδομένων. Εδώ, κάθε στοιχείο συνδέεται με n-άλλα στοιχεία. Οι μη γραμμικές δομές δεδομένων είναι οι εξής:

  • Δέντρα
    • Δυαδικό δέντρο
    • Δυαδικό δέντρο αναζήτησης
    • Δέντρο AVL
    • Κόκκινο-Μαύρο Δέντρο

Πλεονεκτήματα των Δομών Δεδομένων στη Java

  • Αποδοτικότητα
  • Επαναχρησιμοποίηση
  • Ταχύτητα Επεξεργασίας
  • Αφαίρεση
  • Αναζήτηση δεδομένων

Ταξινόμηση Δομών Δεδομένων

Οι δομές δεδομένων μπορούν να ταξινομηθούν ως:

  • Στατικές Δομές Δεδομένων είναι οι δομές δεδομένων των οποίων το μέγεθος δηλώνεται και καθορίζεται την ώρα μεταγλώττισης και δεν μπορεί να αλλάξει αργότερα ονομάζονται δομές στατικών δεδομένων.
  • Παράδειγμα – Πίνακες
  • Δυναμικές Δομές Δεδομένων Είναι οι Δομές Δεδομένων των οποίων το μέγεθος δεν καθορίζεται κατά το χρόνο μεταγλώττισης και μπορούν να αποφασιστούν κατά το χρόνο εκτέλεσης ανάλογα με τις απαιτήσεις ονομάζονται δομές δυναμικών δεδομένων.
  • Παράδειγμα – Δυαδικό δέντρο αναζήτησης
Array declaration
datatype varname []=new datatype[size];  
datatype[] varname=new datatype[size];  

Πίνακας

Τι είναι ένας πίνακας;

Ένας πίνακας είναι η απλούστερη δομή δεδομένων όπου λαμβάνει χώρα μια συλλογή παρόμοιων στοιχείων δεδομένων και κάθε στοιχείο δεδομένων μπορεί να προσπελαστεί απευθείας χρησιμοποιώντας μόνο τον αριθμό ευρετηρίου του.

Πλεονεκτήματα συστοιχίας

  • Τυχαία πρόσβαση
  • Εύκολη ταξινόμηση και επανάληψη
  • Αντικατάσταση πολλαπλών μεταβλητών

Μειονεκτήματα συστοιχίας

  • Το μέγεθος είναι σταθερό
  • Δύσκολη εισαγωγή και διαγραφή
  • Εάν η χωρητικότητα είναι μεγαλύτερη και η πληρότητα λιγότερη, το μεγαλύτερο μέρος της συστοιχίας χάνεται
  • Χρειάζεται συνεχόμενη μνήμη για να εκχωρηθεί

Εφαρμογές Πίνακα

  • Για αποθήκευση πληροφοριών με γραμμικό τρόπο
  • Κατάλληλο για εφαρμογές που απαιτούν συχνή αναζήτηση

Πρόγραμμα Java με χρήση Array

import java.util.*;

class JavaDemo {
	public static void main (String[] args) {
	    int[] priceOfPen= new int[5];
	    Scanner in=new Scanner(System.in);
	    for(int i=0;i<priceOfPen.length;i++)
	        priceOfPen[i]=in.nextInt();

	    for(int i=0;i<priceOfPen.length;i++)
		    System.out.print(priceOfPen[i]+" ");
	}
}


Input:
23 13 56 78 10

Output:
23 13 56 78 10 

Συνδεδεμένη λίστα

Τι είναι η Συνδεδεμένη Λίστα;

Η δομή δεδομένων συνδεδεμένης λίστας βοηθά τα απαιτούμενα αντικείμενα να ταξινομηθούν σε γραμμική σειρά.

Πλεονεκτήματα συνδεδεμένης λίστας

  • Δυναμικό σε μέγεθος
  • Καμία σπατάλη καθώς η χωρητικότητα και το μέγεθος είναι πάντα ίσα
  • Εύκολη εισαγωγή και διαγραφή καθώς απαιτείται χειρισμός 1 συνδέσμου
  • Αποτελεσματική κατανομή μνήμης

Συνδεδεμένη λίστα Μειονεκτήματα

  • Εάν χαθεί ο κύριος κόμβος, χάνεται η συνδεδεμένη λίστα
  • Δεν είναι δυνατή η τυχαία πρόσβαση

Συνδεδεμένη λίστα Εφαρμογές

  • Κατάλληλο όπου η μνήμη είναι περιορισμένη
  • Κατάλληλο για εφαρμογές που απαιτούν συχνή εισαγωγή και διαγραφή

Πρόγραμμα Java στη συνδεδεμένη λίστα


import java.util.*;

class LLNode{

	int data;
	LLNode next;
	
	LLNode(int data)
	{
		this.data=data;
		this.next=null;
		
	}
}


class Demo{
	
	LLNode head;
	
	
	LLNode insertInBeg(int key,LLNode head)
	{
		LLNode ttmp=new LLNode(key);
		
		if(head==null)
			head=ttmp;
		
		else
			{
				ttmp.next=head;
				head=ttmp;
			}
		return head;
	}
	
	
	LLNode insertInEnd(int key,LLNode head)
	{
		LLNode ttmp=new LLNode(key);
		LLNode ttmp1=head;
		
		if(ttmp1==null)
			head=ttmp;
		else
		{
			while(ttmp1.next!=null)
					ttmp1=ttmp1.next;
			ttmp1.next=ttmp;
			
		}
		
		return head;
			
	}


	LLNode insertAtPos(int key,int pos,LLNode head)
	{
		LLNode ttmp=new LLNode(key);
		
		if(pos==1)
		{
			ttmp.next=head;
			head=ttmp;
		}
		else
		{
			LLNode ttmp1=head;
			for(int i=1;ttmp1!=null && i<pos;i++)
				ttmp1=ttmp1.next;
			ttmp.next=ttmp1.next;
			ttmp1.next=ttmp;
		}
		
		return head;
	}
	
	
	LLNode delete(int pos,LLNode head)
	{
		LLNode ttmp=head;
		if(pos==1)
			head=ttmp.next;
		else
		{
			for(int i=1;ttmp!=null && i<pos-1;i++)
				ttmp=ttmp.next;
			ttmp.next=ttmp.next.next;
		}
		return head;
	}
	
	int length(LLNode head)
	{
		LLNode ttmp=head;
		int c=0;
		if(ttmp==null)
			return 0;
		else
		{
		 while(ttmp!=null)
			{	ttmp=ttmp.next;
				c++;
			}
		}
		return c;
	}
	
	
	LLNode reverse(LLNode head)
	{
		LLNode prevLNode=null,curLNode=head,nextLNode=null;
		while(curLNode!=null)
		{
			nextLNode=curLNode.next;
			curLNode.next=prevLNode;
			
			prevLNode=curLNode;
			curLNode=nextLNode;
		}
		
		head=prevLNode;
		return head;
	}
	
	
	void display(LLNode head)
	{
		LLNode ttmp=head;
		while(ttmp!=null)
			{System.out.print(ttmp.data+" ");
			 ttmp=ttmp.next;
			}
	}
	
	public static void main(String[] args)
	{
		LinkedListDemo l=new LinkedListDemo();
		l.head=null;
		Scanner in=new Scanner(System.in);
		 do
	{
 System.out.println("\n********* MENU *********");
	 System.out.println("\n1.Insert In End");
	 System.out.println("\n2.Insert In Beg");
	 System.out.println("\n3.Insert At A  Particular Pos");
	 System.out.println("\n4.Delete At a Pos");
	 System.out.println("\n5.Length");
	 System.out.println("\n6.Reverse");
	 System.out.println("\n7.Display");
	 System.out.println("\n8.EXIT");
	 System.out.println("\nenter ur choice : ");
	 int n=in.nextInt();
	 switch(n)
		{case 1: System.out.println("\nenter the value ");
			  l.head=l.insertInEnd(in.nextInt(),l.head);
			 break;
		 case 2: System.out.println("\nenter the value");
			 l.head=l.insertInBeg(in.nextInt(),l.head);
			 break;
		 case 3: System.out.println("\nenter the value");
			 l.head=l.insertAtPos(in.nextInt(),in.nextInt(),l.head);
			 break;
		 case 4: 
			 l.head=l.delete(in.nextInt(),l.head);
			 break;
		 case 5: 
			System.out.println(l.length(l.head));
			 break;
		 case 6: 
			 l.head=l.reverse(l.head);
			 break;
		 case 7: 
			l.display(l.head);
		 		 break;
		 case 8: System.exit(0);
		 		 break;
		 default: System.out.println("\n Wrong Choice!");
		 		  break;
		}
	 System.out.println("\n do u want to cont... ");
	}while(in.nextInt()==1);

 }
}





Output:

********* MENU *********

1.Insert In End

2.Insert In Beg

3.Insert At A  Particular Pos

4.Delete At a Pos

5.Length

6.Reverse

7.Display

8.EXIT

enter ur choice :
1

enter the value
23

 do u want to cont...
1

********* MENU *********

1.Insert In End

2.Insert In Beg

3.Insert At A  Particular Pos

4.Delete At a Pos

5.Length

6.Reverse

7.Display

8.EXIT

enter ur choice :
1

enter the value
56

 do u want to cont...
1

********* MENU *********

1.Insert In End

2.Insert In Beg

3.Insert At A  Particular Pos

4.Delete At a Pos

5.Length

6.Reverse

7.Display

8.EXIT

enter ur choice :
2

enter the value
10

 do u want to cont...
1

********* MENU *********

1.Insert In End

2.Insert In Beg

3.Insert At A  Particular Pos

4.Delete At a Pos

5.Length

6.Reverse

7.Display

8.EXIT

enter ur choice :
7
10 23 56
 do u want to cont...
1

********* MENU *********

1.Insert In End

2.Insert In Beg

3.Insert At A  Particular Pos

4.Delete At a Pos

5.Length

6.Reverse

7.Display

8.EXIT

enter ur choice :
3

enter the value
67
2

 do u want to cont...
1

********* MENU *********

1.Insert In End

2.Insert In Beg

3.Insert At A  Particular Pos

4.Delete At a Pos

5.Length

6.Reverse

7.Display

8.EXIT

enter ur choice :
7
10 23 67 56
 do u want to cont...
1

********* MENU *********

1.Insert In End

2.Insert In Beg

3.Insert At A  Particular Pos

4.Delete At a Pos

5.Length

6.Reverse

7.Display

8.EXIT

enter ur choice :
4
2

 do u want to cont...
1

********* MENU *********

1.Insert In End

2.Insert In Beg

3.Insert At A  Particular Pos

4.Delete At a Pos

5.Length

6.Reverse

7.Display

8.EXIT

enter ur choice :
7
10 67 56
 do u want to cont...
1

********* MENU *********

1.Insert In End

2.Insert In Beg

3.Insert At A  Particular Pos

4.Delete At a Pos

5.Length

6.Reverse

7.Display

8.EXIT

enter ur choice :
6

 do u want to cont...
1

********* MENU *********

1.Insert In End

2.Insert In Beg

3.Insert At A  Particular Pos

4.Delete At a Pos

5.Length

6.Reverse

7.Display

8.EXIT

enter ur choice :
7
56 67 10
 do u want to cont...




Σωρός

Τι είναι μια στοίβα;

Μια στοίβα είναι μια αναπαράσταση κόμβων. Υπάρχουν δύο στοιχεία σε κάθε κόμβο: δεδομένα και επόμενο (αποθήκευση διεύθυνσης επόμενου κόμβου). Το τμήμα δεδομένων κάθε κόμβου περιέχει την εκχωρημένη τιμή και ο επόμενος δείκτης του κατευθύνει τον χρήστη στον κόμβο που έχει το επόμενο στοιχείο της στοίβας. Ο υψηλότερος κόμβος στη στοίβα αναφέρεται ως κορυφή.

Χαρακτηριστικά του Stack

  • Γραμμικές δομές δεδομένων με χρήση Java
  • Ακολουθεί το LIFO: Last In First Out
  • Μόνο τα κορυφαία στοιχεία είναι διαθέσιμα για πρόσβαση
  • Η εισαγωγή και η διαγραφή πραγματοποιείται από την κορυφή
  • Π.χ.: μια στοίβα από πιάτα, καρέκλες κ.λπ
  • 4 σημαντικές λειτουργίες:
    • push(ele) – χρησιμοποιείται για την εισαγωγή στοιχείου στην κορυφή
    • pop() – αφαιρεί το επάνω στοιχείο από τη στοίβα
    • isEmpty() – επιστρέφει true ότι η στοίβα είναι άδεια
    • peek() – για να λάβετε το επάνω στοιχείο της στοίβας
  • Όλες οι λειτουργίες λειτουργούν σε σταθερό χρόνο, π.χ., O(1)

Πλεονεκτήματα στοίβας

  • Διατηρεί δεδομένα με τρόπο LIFO
  • Το τελευταίο στοιχείο είναι άμεσα διαθέσιμο για χρήση
  • Όλες οι λειτουργίες είναι πολυπλοκότητας O(1).

Μειονεκτήματα στοίβας

  • Ο χειρισμός περιορίζεται στην κορυφή της στοίβας
  • Όχι πολύ ευέλικτο

Στοίβα εφαρμογών

  • Αναδρομή
  • Τεχνολογία
  • Πρόγραμμα περιήγησης
  • Συντάκτες

Πρόγραμμα Java με χρήση στοίβας

import java.util.*;

class Stack
{
   int[] a;
   int top;
   Stack()
   {	
	a=new int[100];
	top=-1;
   }
  
  void push(int x)
  {	
	if(top==a.length-1)
	  System.out.println("overflow");
	else
	 a[++top]=x;
   }
   
   int pop()
   {
     if(top==-1)
		{System.out.println("underflow");
	     return -1;
		}
	 else
	   return(a[top--]);
	}
	
	void display()
	{
		for(int i=0;i<=top;i++)
			System.out.print(a[i]+" ");
		System.out.println();	
	}
	
	boolean isEmpty()
	{
		if(top==-1)
			return true;
		else 
			return false;
	}
	
	int peek()
	{
		if(top==-1)
			return -1;
		return (a[top]);
	}
	
	
}

public class Demo
{
	public static void main(String args[])
	{
		
		Stack s=new Stack();
		Scanner in= new Scanner(System.in);
		
		 do
			{System.out.println("\n******** MENU *******");
			 System.out.println("\n1.PUSH");
			 System.out.println("\n2.POP");
			 System.out.println("\n3.PEEK");
			 System.out.println("\n4 IS EMPTY");
			 System.out.println("\n5.EXIT");
			 System.out.println("\n enter ur choice : ");
			 switch(in.nextInt())
				{
				 case 1: 
					 System.out.println("\nenter the value ");
					 s.push(in.nextInt());
					 break;
				 case 2: 
					System.out.println("\n popped element : "+ s.pop());
					 break;
				 
				case 3: 
					System.out.println("\n top element : "+ s.peek());
					 break;
				 case 4: System.out.println("\n is empty : "+ s.isEmpty());
						 break;
				 case 5: System.exit(0);
						 break;
				 default: System.out.println("\n Wrong Choice!");
						  break;
				}
			 System.out.println("\n do u want to cont... ");
			}while(in.nextInt()==1);

	}
}






Output:

******** MENU *******

1.PUSH

2.POP

3.PEEK

4 IS EMPTY

5.EXIT

 enter ur choice :
1

enter the value
12

 do u want to cont...
1

******** MENU *******

1.PUSH

2.POP

3.PEEK

4 IS EMPTY

5.EXIT

 enter ur choice :
1

enter the value
56

 do u want to cont...
1

******** MENU *******

1.PUSH

2.POP

3.PEEK

4 IS EMPTY

5.EXIT

 enter ur choice :
2

 popped element : 56

 do u want to cont...
1

******** MENU *******

1.PUSH

2.POP

3.PEEK

4 IS EMPTY

5.EXIT

 enter ur choice :
4

 is empty : false

 do u want to cont...
1

******** MENU *******

1.PUSH

2.POP

3.PEEK

4 IS EMPTY

5.EXIT

 enter ur choice :
2

 popped element : 12

 do u want to cont...

Πρόγραμμα δομής δεδομένων Java του Stack – χρησιμοποιώντας LinkedList

import java.util.*;

class LNode
{
	 int data;
	 LNode next;
	 LNode(int d)
	 {
		data=d;
	 }
	 
}

 class Stack
{
	 LNode push(int d,LNode head){  
		
				LNode tmp1 = new LNode(d);
				
				if(head==null)
				   
					head=tmp1;
				
				else
				{
					tmp1.next=head;
					
					head=tmp1;
				}
				return head;
			 }
			 
			 
	 LNode pop(LNode head){
		   
		    if(head==null)
		        System.out.println("underflow");
		   else
				head=head.next;
			return head;
		 }
	

	void display(LNode head){
		
				System.out.println("\n list is : ");
				if(head==null){
					
					System.out.println("no LNodes");
			
					return;
					}
				 
				LNode tmp=head;

				while(tmp!=null){
						
				System.out.print(tmp.data+" ");
					 
				tmp=tmp.next;
					 
					
				}
	       }

    boolean isEmpty(LNode head)
	{
		if(head==null)
			return true;
		else
			return false;
	}
	
	int peek(LNode head)
	{
		if(head==null)
			return -1;
		return head.data;
	}
	
}


public class Demo{
		
		public static void main(String[] args)
		{
		Stack s=new Stack();
		LNode head=null;
		Scanner in=new Scanner(System.in);
		
		 do
			{System.out.println("\n******** MENU *******");
			 System.out.println("\n1.PUSH");
			 System.out.println("\n2.POP");
			 System.out.println("\n3.PEEK");
			 System.out.println("\n4 IS EMPTY"); 
			 System.out.println("\n5 DISPLAY");
			 System.out.println("\n6.EXIT");
			 System.out.println("\n enter ur choice : ");
			 switch(in.nextInt())
				{
				 case 1: 
					 System.out.println("\nenter the value ");
					 head=s.push(in.nextInt(),head);
					 break;
				 case 2: 
					 head=s.pop(head);
					 break;
				 
				case 3: 
				System.out.println("\n top element : "+ s.peek(head));
					 break;
				 case 4: 
System.out.println("\n is empty : "+ s.isEmpty(head));
						 break;
				 case 5: s.display(head); 
						 break;
				 case 6: System.exit(0);
						 break;
				 default: System.out.println("\n Wrong Choice!");
						  break;
				}
			 System.out.println("\n do u want to cont... ");
			}while(in.nextInt()==1);

	}
}





Output
******** MENU *******

1.PUSH

2.POP

3.PEEK

4 IS EMPTY

5 DISPLAY

6.EXIT

 enter ur choice :
1

enter the value
12

 do u want to cont...
1

******** MENU *******

1.PUSH

2.POP

3.PEEK

4 IS EMPTY

5 DISPLAY

6.EXIT

 enter ur choice :
1

enter the value
56

 do u want to cont...
1

******** MENU *******

1.PUSH

2.POP

3.PEEK

4 IS EMPTY

5 DISPLAY

6.EXIT

 enter ur choice :
5

 list is :
56 12
 do u want to cont...
1

******** MENU *******

1.PUSH

2.POP

3.PEEK

4 IS EMPTY

5 DISPLAY

6.EXIT

 enter ur choice :
3

 top element : 56

 do u want to cont...
1

******** MENU *******

1.PUSH

2.POP

3.PEEK

4 IS EMPTY

5 DISPLAY

6.EXIT

 enter ur choice :
4

 is empty : false

 do u want to cont...
1

Ουρά

Τι είναι η ουρά;

Η ουρά ονομάζεται αφηρημένη δομή δεδομένων. Τα δεδομένα προστίθενται πάντα στο ένα άκρο (σε ουρά) και αφαιρούνται από το άλλο (dequeue). Η ουρά χρησιμοποιεί την προσέγγιση First-In-First-Out και το στοιχείο δεδομένων που αποθηκεύτηκε αρχικά θα προσπελαστεί πρώτα σε μια ουρά.

Χαρακτηριστικά του Queue

  • Γραμμική Δομή Δεδομένων
  • Ακολουθεί το FIFO: First In First Out
  • Η εισαγωγή μπορεί να γίνει από το πίσω άκρο.
  • Η διαγραφή μπορεί να γίνει από το μπροστινό μέρος.
  • Π.χ.: ουρά σε γκισέ εισιτηρίων, σταθμό λεωφορείων
  • 4 σημαντικές λειτουργίες:
    • enqueue(ele) – χρησιμοποιείται για την εισαγωγή στοιχείου στην κορυφή
    • dequeue() – αφαιρεί το επάνω στοιχείο από την ουρά
    • peekfirst() – για να λάβετε το πρώτο στοιχείο της ουράς
    • peeklast() – για να λάβετε το τελευταίο στοιχείο της ουράς
  • Όλες οι λειτουργίες λειτουργούν σε σταθερό χρόνο, π.χ., O(1)

Πλεονεκτήματα ουράς

  • Διατηρεί τα δεδομένα με τρόπο FIFO
  • Η εισαγωγή από την αρχή και η διαγραφή από το τέλος χρειάζονται χρόνο O(1).

Εφαρμογές ουράς

  • Χρονοδρομολόγηση
  • Διατήρηση λίστας αναπαραγωγής
  • Διακοπή χειρισμού

Παραλλαγές στην ουρά: Δύο δημοφιλείς παραλλαγές των ουρών είναι Κυκλικές ουρές και Ουρές.

πρόγραμμα Java του Queue- χρησιμοποιώντας Array


import java.util.*;

class Queue{

 int front;
 int rear;
 int[] arr;
 
 Queue()
 {
   front=rear=-1;
   arr=new int[10];
  }
  
  void enqueue(int a)
  {
    if(rear==arr.length-1)
		System.out.println("overflow");
	else
		arr[++rear]=a;
	
	if(front==-1)
		front++;
   }
   
   int dequeue()
   {
     int x=-1;
	 if(front==-1)
		System.out.println("underflow");
	 else
		x=arr[front++];
	 if(rear==0)
	     rear--;
	 return x;
    }
	
	void display()
	{
	  for(int i=front;i<=rear;i++)
		System.out.print(arr[i]+" ");

	 System.out.println();


	}
}

public class QueueDemo{

	public static void main(String[] args)
	{
	  Queue ob=new Queue();
	  ob.enqueue(1);
	  ob.enqueue(2);
	  ob.enqueue(3);
	  ob.enqueue(4);
	  ob.enqueue(5);
	  ob.display();
	  ob.dequeue();
	  ob.display();
	 }
}
	  




Output:


1 2 3 4 5 
2 3 4 5 

Επίδειξη ουράς- με χρήση LinkedList

class LNode{
	
	int data;
	LNode next;

	LNode(int d)
	{
		data=d;
	}
}


class Queue{

	LNode enqueue(LNode head,int a)
	{
		LNode tmp=new LNode(a);
		if(head==null)
			head=tmp;
		else
		 { 
			LNode tmp1=head;
			while(tmp1.next!=null)
				tmp1=tmp1.next;
			
			tmp1.next=tmp;
		}
		return head;
	}
	
	
	LNode dequeue(LNode head)
	{
		if(head==null)
		        System.out.println("underflow");
		   else
				head=head.next;
			return head;
	}
	
	void display(LNode head)
	{
		
				System.out.println("\n list is : ");
				if(head==null){
					
					System.out.println("no LNodes");
			
					return;
					}
				 
				LNode tmp=head;

				while(tmp!=null){
						
				System.out.print(tmp.data+" ");
					 
				tmp=tmp.next;
					 
					
				}
	}
	
	}
	
	public class QueueDemoLL{
		
		public static void main(String[] args)
		{
			Queue ob=new Queue();
			LNode head=null;
			
			head=ob.enqueue(head,1);
			head=ob.enqueue(head,2);
			head=ob.enqueue(head,3);
			head=ob.enqueue(head,4);
			head=ob.enqueue(head,5);
			ob.display(head);
			head=ob.dequeue(head);
			ob.display(head);
		}
	}




Output

list is : 
1 2 3 4 5 
list is : 
2 3 4 5 

Δυαδικό δέντρο

Τι είναι ένα Δυαδικό Δέντρο;

Σε ένα δυαδικό δέντρο, τα κλαδιά του δέντρου αποτελούνται από έως και δύο θυγατρικούς κόμβους για κάθε κόμβο. Ο αριστερός και ο δεξιός κόμβος είναι τα κοινά ονόματα για τους δύο νέους. Οι θυγατρικοί κόμβοι κάνουν αναφορές στους γονείς τους, ενώ οι γονικοί κόμβοι είναι κόμβοι με παιδιά.

Χαρακτηριστικά του Binary Tree

  • Ιεραρχική Δομή Δεδομένων
  • Το κορυφαίο στοιχείο είναι γνωστό ως η ρίζα του δέντρου
  • Κάθε Κόμβος μπορεί να έχει το πολύ 2 παιδιά στο δυαδικό δέντρο
  • Μπορεί να έχει πρόσβαση σε στοιχεία τυχαία χρησιμοποιώντας ευρετήριο
  • Π.χ.: Ιεραρχία συστήματος αρχείων
  • Κοινές μέθοδοι διέλευσης:
    • preorder(root) : print-αριστερά-δεξιά
    • postorder(root) : αριστερά-δεξιά-εκτύπωση
    • inorder(root) : αριστερά-εκτύπωση-δεξιά

Πλεονεκτήματα δυαδικού δέντρου

  • Μπορεί να αναπαραστήσει δεδομένα με κάποια σχέση
  • Η εισαγωγή και η αναζήτηση είναι πολύ πιο αποτελεσματικές

Μειονεκτήματα Binary Tree

  • Η ταξινόμηση είναι δύσκολη
  • Όχι πολύ ευέλικτο

Εφαρμογές Δυαδικών Δέντρων

  • Ιεραρχία συστήματος αρχείων
  • Οι πολλαπλές παραλλαγές του δυαδικού δέντρου έχουν μεγάλη ποικιλία εφαρμογών

Επίδειξη δυαδικού δέντρου

class TLNode
{
 int data;
 TLNode left,right;
 
 TLNode(int d)
 {
   data=d;
  }
 }
 
 
public class BinaryTree
{
   static void preorder(TLNode r)
   {
		if(r==null)
		    return;
		
		System.out.print(r.data+" ");
		
		preorder(r.left);
		preorder(r.right);
		
   }
   static void inorder(TLNode r)
   {
		if(r==null)
		    return;
		
		
		inorder(r.left);
		System.out.print(r.data+" ");
		inorder(r.right);
		
   }
   static void postorder(TLNode r)
   {
		if(r==null)
		    return;
		
		
		postorder(r.left);
		postorder(r.right);
		System.out.print(r.data+" ");

   }
     
    public static void main(String[] args)
	{
		TLNode root=new TLNode(1);
		
		root.left=new TLNode(2);
		root.right=new TLNode(3);
		
		root.left.left=new TLNode(4);
		root.left.right=new TLNode(5);
		
		root.right.left=new TLNode(6);
		root.right.right=new TLNode(7);
		preorder(root);
		System.out.println();
		
		inorder(root);
		System.out.println();
		
		postorder(root);
		System.out.println();
		
		
	}
}



	 
Output
	
1 2 4 5 3 6 7 
4 2 5 1 6 3 7 
4 5 2 6 7 3 1 

Δυαδικό δέντρο αναζήτησης

Τι είναι ένα Δυαδικό Δέντρο Αναζήτησης;

Το δυαδικό δέντρο αναζήτησης είναι ένας προηγμένος αλγόριθμος που χρησιμοποιείται για την ανάλυση των κόμβων, των κλάδων και πολλών άλλων. Το BST αναπτύχθηκε χρησιμοποιώντας την αρχιτεκτονική ενός βασικού δυαδικού αλγόριθμου αναζήτησης, επιτρέποντας ταχύτερες αναζητήσεις κόμβων, εισαγωγές και αφαιρέσεις.

Χαρακτηριστικά του Δυαδικού Δέντρου Αναζήτησης

  • Ένα δυαδικό δέντρο με τον πρόσθετο περιορισμό
  • Περιορισμός:
    • Το αριστερό παιδί πρέπει πάντα να είναι μικρότερο από τον ριζικό κόμβο
    • Το σωστό παιδί πρέπει να είναι πάντα μεγαλύτερο από τον ριζικό κόμβο
  • Η εισαγωγή, η διαγραφή, η αναζήτηση είναι πολύ πιο αποτελεσματική από ένα δυαδικό δέντρο

Δυαδικό δέντρο αναζήτησης Πλεονεκτήματα

  • Διατηρεί την τάξη στα στοιχεία
  • Μπορεί εύκολα να βρει τους min και max κόμβους στο δέντρο
  • Με τη σειρά, η διέλευση δίνει ταξινομημένα στοιχεία

Δυαδικό δέντρο αναζήτησης Μειονεκτήματα

  • Δεν είναι δυνατή η τυχαία πρόσβαση
  • Η παραγγελία προσθέτει πολυπλοκότητα

Δυαδικό δέντρο αναζήτησης Εφαρμογές

  • Κατάλληλο για ταξινομημένα ιεραρχικά δεδομένα

Επίδειξη δυαδικού δέντρου αναζήτησης

class TLNode{

	int data;
	TLNode left,right;
	
	TLNode(int d)
	{
		data=d;
	}
 }
 
 public class BST{
 
	TLNode root;
	
	TLNode insert(int d,TLNode root)
	{
	  if(root==null)
	    root=new TLNode(d);
	  
      else if(d<=root.data)
		root.left=insert(d,root.left);
	
	  else
		root.right=insert(d,root.right);
	
	  return root;
	}
	
	TLNode search(int d,TLNode root)
	{
		if(root.data==d)
			return root;
		else if(d<root.data)
			return search(d,root.left);
	    else
			return search(d,root.right);
	}
	
	
	
	void inorder(TLNode r)
   {
		if(r==null)
		    return;
		
		
		inorder(r.left);
		System.out.println(r.data);
		inorder(r.right);
		
   }
   

TLNode delete(TLNode root, int data) 
    { 
        
        if (root == null)  return root; 
 
        if (data < root.data) 
            root.left = delete(root.left, data); 
        else if (data > root.data) 
            root.right = delete(root.right, data); 
  
        else
        { 
            
            if (root.left == null) 
                return root.right; 
            else if (root.right == null) 
                return root.left; 
  
            
            root.data = minValue(root.right); 
  
            root.right = delete(root.right, root.data); 
        } 
  
        return root; 
    } 	
   int minValue(TLNode root) 
    { 
        int minv = root.data; 
        while (root.left != null) 
        { 
            minv = root.left.data; 
            root = root.left; 
        } 
        return minv; 
    } 

   
   public static void main(String[] args)
   {
		BST ob=new BST();
		ob.root=ob.insert(50,ob.root); 
                ob.root=ob.insert(30,ob.root); 
                ob.root=ob.insert(20,ob.root); 
                ob.root=ob.insert(20,ob.root); 
                ob.root=ob.insert(70,ob.root); 
                ob.root=ob.insert(60,ob.root); 
                ob.root=ob.insert(80,ob.root);    
		ob.root=ob.delete(ob.root,50);
		System.out.println("******" +ob.root.data);
		ob.inorder(ob.root);
		
		TLNode find=ob.search(30,ob.root);
		if(find==null)
			System.out.println("not found");
		else
			System.out.println("found : "+find.data);
		
		
	}
}

  Output:
  
******60
20
20
30
60
70
80
found : 30

Σωρός

  • Το Binary Heap μπορεί να οπτικοποιηθεί ο πίνακας ως ένα πλήρες δυαδικό δέντρο
  • Arr[0] το στοιχείο θα αντιμετωπίζεται ως root
  • μήκος(Α) – μέγεθος πίνακα
  • heapSize(A) – μέγεθος σωρού
  • Γενικά χρησιμοποιείται όταν έχουμε να κάνουμε με ελάχιστα και μέγιστα στοιχεία
  • Για τον κόμβο
(i-1)/2 Μητρική εταιρεία
(2*i)+1 Αριστερό παιδί
(2*i)+2 Σωστό παιδί

Σωρός Πλεονεκτήματα

  • Μπορεί να είναι 2 τύπων: ελάχιστο σωρό και μέγιστο σωρό
  • Ο ελάχιστος σωρός διατηρεί το μικρότερο στοιχείο και το επάνω και το μέγιστο διατηρούν το μεγαλύτερο
  • O(1) για την αντιμετώπιση ελάχιστων ή μέγιστων στοιχείων

Σωρός Μειονεκτήματα

  • Δεν είναι δυνατή η τυχαία πρόσβαση
  • Μόνο το ελάχιστο ή μέγιστο στοιχείο είναι διαθέσιμο για προσβασιμότητα

Σωρός Εφαρμογές

  • Κατάλληλο για εφαρμογές που αφορούν προτεραιότητα
  • Αλγόριθμος προγραμματισμού
  • προσωρινή αποθήκευση

Το πρόγραμμα του Max Heap

import java.util.*;


class Heap{

	int heapSize;
	
	void build_max_heap(int[] a)
	{
		heapSize=a.length;
		for(int i=(heapSize/2);i>=0;i--)
			max_heapify(a,i);
		
	}
	
	void max_heapify(int[] a,int i)
	{
		int l=2*i+1;
		int r=2*i+2;
		int largest=i;
		if(l<heapSize &&a[l]>a[largest])
			largest=l;
		if(r<heapSize &&a[r]>a[largest])
			largest=r;
		if(largest!=i)
		{
			int t=a[i];
			a[i]=a[largest];
			a[largest]=t;
		    max_heapify(a,largest);
		}
		
	}
	
	//to delete the max element
	
	int extract_max(int[] a)
	{
		if(heapSize<0)
			System.out.println("underflow");
		int max=a[0];
		a[0]=a[heapSize-1];
		heapSize--;
		max_heapify(a,0);
		return max;
	}
	
	void increase_key(int[] a,int i,int key)
	{
		if(key<a[i])
			System.out.println("error");
		a[i]=key;
		while(i>=0 && a[(i-1)/2]<a[i])
		{
			int t=a[(i-1)/2];
			a[(i-1)/2]=a[i];
			a[i]=t;
			
			i=(i-1)/2;
		}
	}
	
	void print_heap(int a[])
	{
		for(int i=0;i<heapSize;i++)
		    System.out.println(a[i]+" ");
	}
}
	
public class HeapDemo{
	
	public static void main(String[] args)
	{
		Scanner in=new Scanner(System.in);
		int n=in.nextInt();
		int a[]=new int[n];
		
		System.out.println("enter the elements of array");
		
		for(int i=0;i<n;i++)
		  a[i]=in.nextInt();
	         Heap ob=new Heap();
		
		ob.build_max_heap(a);
		ob.print_heap(a);
		
		
		System.out.println("maximum element is : "+ob.extract_max(a));
		ob.print_heap(a);
		System.out.println("maximum element is : "+ob.extract_max(a));
		ob.increase_key(a,6,800);
		ob.print_heap(a);
		   
	}

}

Output
7
enter the elements of array
50 100 10 1 3 20 5
100
50
20
1
3
10
5
maximum element is : 100
50
5
20
1
3
10
maximum element is : 50
800
5
20
1
3

Κατακερματισμός

  • Χρησιμοποιεί ειδική λειτουργία Hash
  • Μια συνάρτηση κατακερματισμού αντιστοιχίζει ένα στοιχείο σε μια διεύθυνση για αποθήκευση
  • Αυτό παρέχει πρόσβαση σε σταθερό χρόνο
  • Οι τεχνικές επίλυσης σύγκρουσης χειρίζονται τη σύγκρουση
  • Τεχνική επίλυσης σύγκρουσης

Κατακερματισμός Πλεονεκτήματα

  • Η συνάρτηση κατακερματισμού βοηθά στην ανάκτηση στοιχείων σε σταθερό χρόνο
  • Ένας αποτελεσματικός τρόπος αποθήκευσης στοιχείων

Κατακερματισμός Μειονεκτήματα

  • Η ανάλυση σύγκρουσης αυξάνει την πολυπλοκότητα

Κατακερματισμός Εφαρμογές

  • Κατάλληλο για την εφαρμογή χρειάζεται συνεχή λήψη χρόνου

Επίδειξη του HashSet – η εύρεση συμβολοσειράς έχει μοναδικούς χαρακτήρες

import java.util.*;

class HashSetDemo1{

	static boolean isUnique(String s)
	{
		HashSet<Character> set =new HashSet<Character>();
		
		for(int i=0;i<s.length();i++)
		    {
				char c=s.charAt(i);
				if(c==' ')
					continue;
				if(set.add(c)==false)
					return false;
					
			}
			
		return true;
	}
	
	
	public static void main(String[] args)
	{
		String s="helo wqty ";
		boolean ans=isUnique(s);
		if(ans)
			System.out.println("string has unique characters");
		else
			System.out.println("string does not have unique characters");

		
		
	}
}

Output:
string has unique characters

Επίδειξη του HashMap – μετρήστε τους χαρακτήρες σε μια συμβολοσειρά

import java.util.*;

class HashMapDemo
{

	static void check(String s)
	{
		HashMap<Character,Integer> map=new HashMap<Character,Integer>();
		for(int i=0;i<s.length();i++)
			{char c=s.charAt(i);
			 if(!map.containsKey(c))
				map.put(c,1);
			 else
				map.put(c,map.get(c)+1);
			}
			
		
		
		Iterator<Character> itr = map.keySet().iterator();
		while (itr.hasNext()) {
			Object x=itr.next();
			System.out.println("count of "+x+" : "+map.get(x));
		}
	}
	
	public static void main(String[] args)
	{
		String s="hello";
		check(s);
	}
}

Output
count of e : 1
count of h : 1
count of l : 2
count of o : 1

Επίδειξη HashTable – η εύρεση συμβολοσειρών έχει μοναδικούς χαρακτήρες

import java.util.*; 
class hashTabledemo { 
	public static void main(String[] arg) 
	{ 
		// creating a hash table 
		Hashtable<Integer, String> h = 
					new Hashtable<Integer, String>(); 

		Hashtable<Integer, String> h1 = 
					new Hashtable<Integer, String>(); 

		h.put(3, "Geeks"); 
		h.put(2, "forGeeks"); 
		h.put(1, "isBest"); 

		// create a clone or shallow copy of hash table h 
		h1 = (Hashtable<Integer, String>)h.clone(); 

		// checking clone h1 
		System.out.println("values in clone: " + h1); 

		// clear hash table h 
		h.clear(); 

		// checking hash table h 
		System.out.println("after clearing: " + h); 
				System.out.println("values in clone: " + h1); 


	} 
} 

Output
values in clone: {3=Geeks, 2=forGeeks, 1=isBest}
after clearing: {}
values in clone: {3=Geeks, 2=forGeeks, 1=isBest}

Γραφική παράσταση

  • Βασικά είναι μια ομάδα ακμών και κορυφών
  • Αναπαράσταση γραφήματος
    • G(V, E); όπου το V(G) αντιπροσωπεύει ένα σύνολο κορυφών και το E(G) ένα σύνολο ακμών
  • Το γράφημα μπορεί να είναι κατευθυνόμενο ή μη
  • Το γράφημα μπορεί να συνδεθεί ή να αποσυνδεθεί

Γραφική παράσταση Πλεονεκτήματα

  • εύρεση συνδεσιμότητας
  • Το συντομότερο μονοπάτι
  • ελάχιστο κόστος για να φτάσετε από 1 pt σε άλλο
  • Ελάχιστο εκτεινόμενο δέντρο

Μειονεκτήματα γραφήματος

  • Η αποθήκευση γραφήματος (λίστα γειτνίασης και πίνακας γειτνίασης) μπορεί να οδηγήσει σε πολυπλοκότητα

Εφαρμογές γραφήματος

  • Κατάλληλο για δίκτυο κυκλώματος
  • Κατάλληλο για εφαρμογές όπως Facebook, LinkedIn κ.λπ
  • Ιατρική επιστήμη

Επίδειξη γραφήματος

import java.util.*;

class Graph
{
	int v;
	LinkedList<Integer> adj[];

	Graph(int v)
	{
		this.v=v;
		adj=new LinkedList[v];
		for(int i=0;i<v;i++)
			adj[i]=new LinkedList<Integer>();
	}


	void addEdge(int u,int v)
	{
		adj[u].add(v);
	}
	
	void BFS(int s)
	{
		boolean[] visited=new boolean[v];
		LinkedList<Integer> q=new LinkedList<Integer>();
		q.add(s);
		visited[s]=true;

		while(!q.isEmpty())
		{
			int x=q.poll();
			System.out.print(x+" ");

			Iterator<Integer> itr=adj[x].listIterator();
			while(itr.hasNext())
			{
			  int p=itr.next();
			  if(visited[p]==false)
				{
					visited[p]=true;
					q.add(p);
				}
			}
		}
	}
	
	
	void DFSUtil(int s,boolean[] visited)
	{
		visited[s]=true;
		System.out.println(s);

		Iterator<Integer> itr=adj[s].listIterator();
		while(itr.hasNext())
		{
			int x=itr.next();
			if(visited[x]==false)
			{                                                        
				//visited[x]=true;

				DFSUtil(x,visited);
			} 
		}
	}
	
	
	void DFS(int s){
		boolean visited[]=new boolean[v];
		DFSUtil(s,visited);
	}

	public static void main(String[] args)
		{
			Graph g=new Graph(4);
			g.addEdge(0,1);
			g.addEdge(0,2);
			g.addEdge(1,2);
			g.addEdge(2,0);
			g.addEdge(2,3);
			g.addEdge(3,3);
			
			g.BFS(2);
			g.DFS(2);

		}
}

Output:
2 0 3 1 2
0
1
3

Δομές δεδομένων σε Συχνές ερωτήσεις Java

Μπορώ να χρησιμοποιήσω Java για δομές δεδομένων;

Ναι, μπορείτε να χρησιμοποιήσετε java για δομές δεδομένων, Εδώ η java είναι απλώς μια γλώσσα προγραμματισμού και οι δομές δεδομένων βοηθούν στην αποθήκευση και οργάνωση των δεδομένων στην απαιτούμενη μορφή.

Ποιες είναι οι δομές δεδομένων της Java;

Μερικές από τις δομές δεδομένων της java είναι
Συνδεδεμένες λίστες.
Πίνακες.
Σωρός.
Ουρά.
Γραφική παράσταση.
Σειρά.

Ποια δομή δεδομένων είναι καλύτερη για Java;

Δεν υπάρχει τέτοια καλύτερη δομή δεδομένων για java. Αλλά οι προγραμματιστές θα χρησιμοποιήσουν πίνακα καθώς είναι μια από τις απλούστερες και πιο ευρέως χρησιμοποιούμενες δομές δεδομένων.

Ποια είναι η ταχύτερη δομή δεδομένων στην Java;

Για διαφορετικά προβλήματα, οι διαφορετικές δομές δεδομένων είναι οι πιο γρήγορες. Αλλά γενικά, οι πίνακες είναι οι πιο γρήγορες δομές δεδομένων στη java καθώς είναι απλές δομές δεδομένων.

Πρέπει να μάθω δομές δεδομένων σε Java;

Ναι, η εκμάθηση δομών δεδομένων σε java σας βοηθά να βελτιώσετε τις γνώσεις προγραμματισμού σας. Λέγεται ότι Δομές δεδομένων + Αλγόριθμοι = Προγράμματα, επομένως η εκμάθηση δομών δεδομένων είναι σημαντική.

Ποια γλώσσα είναι η καλύτερη για DSA;

Η γλώσσα είναι απλώς ένα μέσο, ​​αλλά στην τρέχουσα τάση, η java ή η python είναι η καλύτερη γλώσσα για DSA.

Πόσες δομές δεδομένων υπάρχουν στην Java;

Υπάρχουν 2 δομές δεδομένων στη java. Είναι γραμμικές και μη γραμμικές (ιεραρχικές) δομές δεδομένων.