queue
: 일반적으로 가장 많이 사용되는 구조. 통신쪽에서 많이 사용한다.
-
java에서 에러 메시지를 담아놓는 구조는 큐이다.
(어디서부터 에러가 났는지 순서대로 출력해줘야하기 때문이다.) -
Queue는 나한테 제어권이 없는 구조이다. (선입선출이므로)
poll할 때 먼저들어온 것부터 끄집어낼 수 있다. -
큐 인터페이스를 받으면 큐에 정의된 메소드만 써야하므로 Linkedlist에 있는 다른 메소드들을 제약하는 것이다.
-
Linked list는 Queue 인터페이스를 상속받는다.
package com.bit.day10;
import java.util.LinkedList;
import java.util.Queue;
public class Ex05 {
public static void main(String[] args) {
Queue list=new LinkedList();
list.offer("첫번째");
list.offer("두번째");
list.offer("세번째");
list.offer("네번째");
//집어넣은 순서대로 끄집어내진다.
// System.out.println(list.peek());
// System.out.println(list.poll()); //한번보고 끄집어낸다
// System.out.println(list.peek());
// System.out.println(list.poll()); //두번째를 끄집어낸다
// System.out.println(list.peek());
// System.out.println(list.poll());
// System.out.println(list.peek());
while(list.peek()!=null){ //null이 아니면 반복접으로 끄집어내기
System.out.println(list.poll());
}
}
}Stack
- 스택을 사용하는 경우
ex) 페이지이동 (뒤로가기)
package com.bit.day10;
import java.util.Stack;
public class Ex07 {
public static void main(String[] args) {
Stack list=new Stack(); //Lifo
list.push("a");
list.push("b");
list.push("c");
list.push("d");
while(!list.empty()){ //비어있으면 true -- 반복문 탈출
System.out.println(list.pop());
}
}
}Deque
package com.bit.day10;
import java.util.Deque;
import java.util.LinkedList;
public class Ex08 {
public static void main(String[] args) {
Deque que=new LinkedList();
que.offerFirst("첫번째");
que.offerFirst("두번째");
que.offerFirst("세번째");
que.offerFirst("네번째");
while(que.peek()!=null){
System.out.println(que.pollLast()); //첫번째부터 출력
// System.out.println(que.pollFirst()); //네번째부터 출력(앞에서부터 출력)
}
System.out.println("-----------------------");
que.offerLast("첫번째");
que.offerLast("두번째");
que.offerLast("세번째");
que.offerLast("네번째");
while(que.peek()!=null){
System.out.println(que.pollLast());
// System.out.println(que.pollFirst());
}
}
}Vector
package com.bit.day10;
import java.util.Vector;
public class Ex09 {
public static void main(String[] args) {
Vector list=new Vector();
System.out.println(list.capacity()); //default 버퍼량:10
for(int i=0; i<22; i++) list.add(i); //2배로 늘린다.(10의 단위로)
System.out.println(list.capacity()); Vector list=new Vector(5,2); //5:공간, 2:증가량까지 내가 직접 줄 수 있다.package com.bit.day10;
import java.util.Enumeration;
import java.util.Vector;
public class Ex09 {
public static void main(String[] args) {
Vector list=new Vector(5,2);
// System.out.println(list.capacity()); //default 버퍼량:10
//
// for(int i=0; i<22; i++) list.add(i); //2배로 늘린다.(10의 단위로)
// System.out.println(list.capacity());
list.addElement("첫번째");
list.addElement("두번째");
list.addElement("세번째");
list.addElement("네번째");
//순서가 있는 list. idx가 있다는 것은 순서가 있다는 것.
// for(int i=0; i<list.size(); i++){
// System.out.println(list.elementAt(i));
// }
System.out.println("-----------------------------");
//set : 이 당시의 vector는 set의 흉내. 버퍼가 있다=배열. 그래서 100% 순서가 없을 순 없다.
//완벽하게 구현되지 못한 set이었다. 중복처리도 되지 않았다. 개념적인 존재였다.
Enumeration em=list.elements();
while(em.hasMoreElements()){ //있으면 true
System.out.println(em.nextElement());
}
}
}프로그램상에서는 순서가 없을 수가 없다. 메모리주소도있고..
즉, 내부적으로는 순서가있다. 순서가 있어야 비교가 가능하기 때문이다.
그래서 다르면 집어넣고 같으면 못집어넣는다.
- 순서가 없다는 것은 중복되지 않는다는 것이다.
그래서 중복되지 않은 값을 넣어줘야한다?? --> 값을 넣기 전에 중복인지 아닌지 검사해야한다. - 값이 들어갈때마다 정리를 해놓으면 중복인지 아닌지 쉽게 검사할 수 있다.
- 어떤 정리방식을 선택할 것인가는 클래스마다 다르다.
- 개념상으로는 순서가없으므로 인덱스로 값을 끄집어낼수없다.
Set
-Hashset : 객체의 hash값이 기준. (같은 객체인지 다른객체인지 비교할때 기준)
hash값을 사용하는데 완벽한 중복검출이 안될 수도 있다.(희박한 확률)
package com.bit.day10;
import java.util.HashSet;
import java.util.Iterator;
public class Ex10 {
public static void main(String[] args) {
//interface set
java.util.Set set=new HashSet(); //문제를 잘 일으키지 않는 set
set.add(1111);
set.add(2222);
set.add(3333);
set.add(4444);
set.add(2222); //중복됐을땐 들어가지 않는다.
Iterator ite=set.iterator(); //iterator를 반환한다. (iterable interface의 메소드)
while(ite.hasNext()){
System.out.println(ite.next());
}
//순서와 상관없이 출력되는것같지만 여러번 해보면 똑같은 순서만 나온다.
//즉, 순서가 있지만 순서가 없는것처럼 동작하는것.
}
}treeset
: value값을 기준으로 정렬한다..
package com.bit.day10;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;
public class Ex10 {
public static void main(String[] args) {
//interface set
java.util.Set set=new TreeSet();
set.add(1111);
set.add(2222);
set.add(3333);
set.add(4444);
set.add(2222);
set.add(11);
Iterator ite=set.iterator();
while(ite.hasNext()){
System.out.println(ite.next());
}
//개념상으로 set은 순서가 없는 것인데, 이진트리의 구조상 자동으로 정렬되기 때문에 순서가 있는것처럼된다.
}
}Hash로는 문제없음
public class Ex10 {
public static void main(String[] args) {
//interface set
java.util.Set set=new HashSet();
set.add(new Ex10());
set.add(new Ex10());
set.add(new Ex10());
set.add(new Ex10());tree로는 실행 안됨(에러) -- 값을 비교해야하는데 객체가 들어오면 비교할 기준이 없으니까.ClassCastException 에러가 뜨게 된다.
객체일지라도 문자열은 문자의 집합이므로 비교가 가능하다.(compareTo)
comparable 인터페이스를 상속하고 compareTo메소드를 오버라이딩 하여 정렬 기준을 정해주었다.
package com.bit.day10;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;
public class Ex10 implements Comparable{
int val;
public Ex10(int su){ //생성자
val=su;
}
public static void main(String[] args) {
//interface set
java.util.Set set=new TreeSet();
Ex10 me=new Ex10(1);
set.add(me);
set.add(me);
set.add(new Ex10(2));
set.add(new Ex10(3));
set.add(new Ex10(4));
Iterator ite=set.iterator();
while(ite.hasNext()){
System.out.println(ite.next()); //me는 중복 -- 하나만 저장했으므로 하나 출력.
}
}
public int compareTo(Object obj){ //정렬기준을 val 값으로 정하였다.
return val-((Ex10)obj).val; //이렇게 하면 객체의 값을 val로 받아들이고 출력가능
}
}객체를 비교하려면 2를 기준으로 compareto를 호출해서 2를 인자로받아서 리턴.
그 일을 시켜야함. 그런데 내가 만든 이 Ex10 클래스를 어떻게 알고 호출하느냐
실제 객체는 integer인데 어떻게 캐스팅햐냐~interface로 캐스팅하면 가능
자료구조는 꼭꼭 다시 공부해야 할 부분!
