[ JAVA ] 스택과 큐

스택과 큐

• 스택 : 마지막에 저장한 데이터를 가장 먼저 꺼냄 - LIFO(Last In First Out)
• 큐 : 처음에 저장한 데이터를 먼저 꺼냄 - FIFO( First In First Out)
• 스택은 ArrayList로 구현
• 큐는 데이터를 꺼내면 맨처음 데이터를 삭제하기 때문에 LinkedList가 적합
• 배열을 사용하면 큐에서 데이터를 꺼낼 때마다 빈 공간을 채워주기 위해 배열을 복사해야 하기 때문에 부적합

메서드

스택

• boolean empty()
• Object peek() - 맨 위의 데이터를 반환, 데이터 삭제 X
• Object pop() - 맨 위의 데이터를 반환, 데이터 삭제
• Object push(Object item)
• int search(Object item) - 아이템의 위치를 반환, 못찾으면 -1 반환

큐

• boolean add(Object o) - 저장 공간이 부족하면 lllegalStateException 발생
• Object remove() - 큐에서 객체를 꺼내 반환, 없으면 NoSuchElementException 발생
• Object element() - 삭제 없이 데이터를 읽어옴, 없으면 NoSuchElementException 발생
• boolean offer(Object o) - 객체 저장, 성공하면 true, 실패하면 false
• Object poll() - 큐에서 객체 반환 , 없으면 null
• Object peek() - 큐에서 객체 읽기 , 없으면 null

Priority Queue, Dequeue

Priority Queue

• 저장한 순서와 관계 없이 우선 순위가 높은 것부터 꺼냄
• null은 저장 불가능
• 저장 공간으로 배열을 사용하며 각 요소를 힙이라는 자료구조 형태로 저장
• 힙 : 이진 트리의 한 종류로 가장 큰 값이나 작은 값을 빠르게 찾을 수 있음

Dequeue

• Double Ended Queue
• 덱 또는 디큐라 읽음
• 디큐는 양쪽 끝에 추가/삭제가 가능
• 스택과 큐를 합쳐놓음