자료 구조 중에 stack과 queue를 배웠다.
둘 다 개념 자체는 별 거 아닌데, 이걸 응용해서 문제풀기가.. 어렵지.
보면 항상 그래. 개념 자체는 별 거 아니야. 문제 해결이 문제지.
아니다, 내가 문젠가ㅋㅋㅋㅋㅋ
자료 구조 : 데이터를 효율적으로 다룰 수 있는 방법들
각 자료 구조는 특정한 상황에 특화되어있다
내가 해결할 문제에 어떤 자료구조를 채택하여 문제를 해결할 것인가! 를 위해 자료구조를 공부하는 것
Stack : 데이터를 순서대로 "쌓는다"
Last In First Out
push() : 데이터 넣기
pop() : 마지막에 넣은 데이터를 리턴하고 스택에서 삭제
peek() : 마지막에 넣은 데이터 리턴
empty() : boolean 리턴
search(o) : o가 스택에 없다면 -1리턴, 있다면 얼마나 멀리 있는지 int로 리턴
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4); //{1, 2, 3, 4}
System.out.println(stack.pop());//4
System.out.println(stack.search(1));
//3, 현재 스택은 {1, 2, 3}, 1을 꺼내려면 pop을 3번 해야한다, 이렇게 이해하면 되나?
System.out.println(stack.pop());//3
System.out.println(stack.pop());//2
System.out.println(stack.empty());//false
System.out.println(stack.pop());//1
System.out.println(stack.empty());//trueStack의 장점
-데이터를 삽입, 삭제할 때 모든 데이터를 순회할 필요가 없기 때문에 데이터를 가져오는 속도가 빠르다
-자바에서 스택을 기본 자료 구조로 제고아기 때문에 별도의 라이브러리나 모듈을 설치할 필요가 없다
자바에서 Stack의 단점
-크기 제한이 없다. 이를 피하려면 스택의 크기를 미리 정하거나 동적으로 조절해야 한다.
-Vector 클래스를 상속받아 구현되어 있다. >처음에 지정된 크기만큼만 할당되고, 크기가 초과되면 새로 할당하고 기존 데이터를 복사한다. >크기가 자주 변하는 스택은 다른 구조를 쓰는게 효율적
-Vector를 상속받아 구현되어 있어 vector의 모든 메서드를 사용할 수 있다 > 중간 삽입, 삭제 등 의도된 동작을 방해할 수 있어 주의를 요한다.
LIFO 깊이 들어가려면 Deque 인터페이스 보라고 공식문서가 학습방향도 알려주네... 좀있다가 봐야지
Queue는 First In First Out
게임할 때 큐 생각하면 될듯
queue의 요소 추가는 add(), offer()이 있다.
offer()는 넣을 자리가 없으면 false를 리턴하고 add()는 예외를 발생시킨다. 즉, offer()는 예외처리 안해도 된다
나머지 메서드들도 마찬가지
| Throws exception | Return special value | |
|---|---|---|
| insert | add | offer |
| remove | remove | poll |
| examine | element | peek |
Queue 의 장점
-처리해야 할 작업이 여러 개 있을 경우, 차례대로, 효율적인 처리가 가능하다.
-삽입, 삭제가 빠르다
-자바에서 기본 자료구조로 제공한다
자바에서 Queue의 단점
-중간 삽입, 삭제, 조회에는 적합하지 않다
-크기 제한이 없어서 메모리 낭비가 발생할 수 있다.
-iterator()가 지원되지 않는다
-큐가 중복 객체를 허용할 경우, remove(o)의 동작이 불명확하다.
+원형 큐 공부하란다..... deque랑 같이 봐야겠다....
