[개인공부] Stack과 Queue

---

스택(Stack)

• LIFO 구조. 마지막에 저장된 것을 제일 먼저 꺼내게 된다.
  (Last In First Out)
• 밑이 막힌 상자라고 생각하자
• push / pop

↳ 저장할 땐 0 → 1 → 2 순으로 저장되고
추출할 땐 2 → 1 → 0 순으로 추출한다.
= 저장과 추출의 순서가 반대!

스택의 구현

• 배열과 링크드리스트 중 배열이 더 효과적이다.

---

큐(Queue)

• FIFO 구조. 제일 먼저 저장한 것을 제일 먼저 꺼내게 된다.
  (First In First Out)
• 밑이 뚫린 상자!
• 줄서기를 생각하자~ 제일 먼저 줄 선 사람이 제일 먼저 감~
• offer / poll
  ↳ 저장할 때 0 → 1 → 2 순으로 저장되고
  추출할 때도 0 → 1 → 2 순으로 추출한다.
  = 저장과 추출의 순서가 일치!

큐의 구현

• 배열과 링크드리스트 중 링크드리스트가 더 효과적이다.

---

---

스택과 큐(Stack & Queue)의 메서드

---

스택 메서드

• 스택은 클래스라 클래스처럼 사용하면 된다.

Stack st = new Stack();

▶︎ pop() : 삭제
▶︎ push() : 추가
▶︎ peek() : 맨 위에 있는 객체 반환
( 막혀있는 박스를 봤을 때 제일 위에있는 것만 보이듯!)
▶︎ search() 맨위에있는 객체부터 1,2,3...

---

큐 메서드

• 큐는 인터페이스로 정의되어 있다

Queue q = new Queue(); //인터페이스라 안됨!!!

Queue q = new LinkedList(); //OK! Queue를 구현한 클래스인 LinkedList 사용 or
LinkedList l = new LinkedList(); //OK! 더좋음 Queue가 큰 개념이라 참조변수 타입을 좁혀주는게 좋다.

따라서
1. Queue를 직접 구현해서 사용하거나
2. Queue를 구현한 클래스를 사용하면 된다. (더 편리하고 빠르니까!)
(Queue 인터페이스 설명에서 All Known Implementing Classes를 확인해보면 된다)

▶︎ offer(): 추가
▶︎ add(): 추가 → 예외 발생
▶︎ poll(): 삭제 → 예외발생 안하고 null 반환
▶︎ remove(): 삭제 → 예외발생(try-catch 필요)
▶︎ peek(): 꺼내지 않고 보기만 함 구경구경~

스택 & 큐 예제

—-

Stack과 Queue의 활용

• 스택의 활용 예)

  • 수식계산((3+2)*8)/2 같은, 수식괄호검사(괄호 갯수 맞는지?), 워드프로세서의 undo/redo, 웹브라우저의 뒤로/앞으로
    

• 큐의 활용 예)

  • 최근사용문서(목록), 인쇄작업 대기목록, 버퍼(buffer)
    
    
    

for문에서 list.size를 반복문을 도는 동안 계속 호출을 하는데 실무에서는 final로 SIZE값을 상수값으로 정해놓고 for문에 상수값을 넣어줘서 한다.
ListIterator it = list.listIterator();를 사용해도되는데, 현재는 사용을 잘 안한다.