- 선형구조: 자료 간 관계가 1:1 ex)스택,큐, 연결리스트
- 비선형구조: 자료간의 관계가 1:N의 관계 ex)트리, 그래프
Stack
- LIFO(마지막에 삽입한 자료를 가장 먼저 꺼냄)
- 자료구조: 배열을 사용할 수 있음(저장소 자체를 스택이라고 부르기도 함)
- 스택은 구현이 용이하지만 크기를 변경하기가 어렵다
| 의미 | 연산 | 특징 |
|---|---|---|
| 마지막 원소위치 | top | |
| 삽입(저장소에 자료저장) | push | |
| 삭제 | pop | 실제로 삭제된건아니지만 덮어씌워지는 것 |
| 공백인지 아닌지 확인 | isEmpty | 비었으면 True |
| top에 있는 원소를 반환 | peek |
Queue
-
선입선출(FIFO)
-
아래쪽(head)에서 pop을 하고 위(tail)에서 append를 해줌
-
JCF에서 Queue 인터페이스의 경우에는 Collection 에서 상속 받은 메소드 (add, remove, element)가 실패 시에 익셉션을 발생시키므로, *Queue 활용 시, 일반적인 경우에는 offer, poll, peek 메소드를 사용
public interface Queue<E> extends Collection<E> {
boolean add(E e); //push (불가능시 익셉션 발생)
boolean offer(E e); //큐에 요소를 삽입 (불가능시 false 반환)
E remove(); // 앞부분을 반환 및 삭제, (비어있는 경우 익셉션 발생)
E poll(); // pop반환 후 제거 (비어있는 경우 null 반환)
E element(); //앞 부분 반환 (비어있는 경우 익셉션 발생)
E size(); // size반환
E peek(); // 앞부분 반환
(비어있는 경우 null 반환)Deque
- 양방향 queue
- 양 끝 엘리먼트의 append와 pop이 압도적으로 빠르다
- Deque 인터페이스의 경우에는 Queue 인터페이스에서 양쪽을 의미하는 First, Last 접미사를 사용해 어디서 요소를 제어할 것인가를 메소드에 추가 명시해뒀다. 그리고, Stack 형태로 활용이 가능하게끔 push, pop 메소드를 넣어두었다.
- Deque인터페이스에 push,pop메소드를 넣은 이유는 stack클래스를 자바에서 잘못구현했기 때문..
public interface Deque<E> extends Queue<E> {
void addFirst(E e);
void addLast(E e);
boolean offerFirst(E e);
boolean offerLast(E e);
E removeFirst();
E removeLast();
E pollFirst();
E pollLast();
E getFirst();
E getLast();
E peekFirst();
E peekLast();
void push(E e);
E pop();
//...