[자료구조/Java] 스택/큐

✔ 목차

1. 스택(stack)이란?
2. 큐(queue)란?
3. 시간복잡도
   
   

---

🔎 스택(stack)이란?

• 한 쪽 끝에서 삽입/삭제 연산이 이뤄지는 리스트
• top: 삽입/삭제 연산이 일어나는 끝
• push: 삽입 연산
• pop: 삭제 연산
• 후입선출, LIFO(Last-In First-Out)
• 사용 예시
  • 웹 브라우저 방문 기록
  • 후위 표기법 계산
  • 함수 호출 발생 시 복귀 주소 저장

java에서 stack 사용하기

---

🔎 큐(queue)란?

• 한 쪽 끝에서 삽입 연산이 일어나고 다른 쪽 끝에서만 삭제 연산이 일어나는 리스트
• rear: 삽입 연산이 일어나는 끝
• front: 삭제 연산이 일어나는 끝
• enqueue: 삽입 연산
• dequeue: 삭제 연산
• 선입선출, FIFO(First-In First-Out)
• 사용 예시
  • 운영체제 스케줄링
  • 우선순의 작업

java에서 Queue 사용하기

---

⏰ 시간복잡도

• 스택, 큐 모두 삽입, 삭제 하는 곳이 정해져 있어 O(1) 시간이 걸린다.
• 스택, 큐 모두 만약 특정 원소를 찾는다면 최악의 경우 원소의 개수 n개를 모두 꺼내야한다.

연산	시간복잡도
삽입	O(1)
삭제	O(1)
탐색	O(n)