스택(Stack)

📌 스택(Stack)이란 무엇일까?

LIFO(Last In, First Out) 원칙에 따라 작동하는 데이터 구조로, 가장 마지막에 추가된 데이터가 가장 먼저 제거되는 특징을 가진다.

특징

• 후입선출(LIFO)
• 단방향 입출력 구조
• 깊이 우선 탐색(DFS)에 이용

사용 예시

• 웹 브라우저의 뒤로 가기
• 실행 취소 기능
• 함수 호출 관리
• 역순 문자열 만들기
• 후위 표기법 계산

기본 연산

• push: 스택의 맨 위에 새로운 객체를 추가
• pop: 스택의 맨 위에 있는 객체를 제거하고 반환
• peek: 스택의 맨 위에 있는 객체를 제거하지 않고 반환
• empty: 스택이 비어있는지 확인

시간 복잡도

• O(1)
  : 맨 앞이나 뒤의 객체를 다루기 때문에

큐(Queue)

📌 큐(Queue)란 무엇일까?

FIFO(First In, First Out) 원칙에 따라 작동하는 데이터 구조로, 가장 먼저 추가된 데이터가 가장 먼저 제거되는 특징을 가진다.

특징

• 선입선출(FIFO)
• 단방향 입출력 구조
• 너비 우선 탐색(BFS)에 이용
• 삭제 작업이 이루어지는 맨 앞을 front, 삽입이 이루어지는 맨 뒤를 rear/back라고 명명
• 배열에서 사용 시, 인덱스 변경하는 처리 속도가 상대적으로 느림
• 인덱스가 없기 때문에 LinkedList를 큐의 자료구조로 택하는 것이 좋다.

사용예시

• 은행 업무
• 대기열 같은 우선순위 작업 예약
• 프로세스 스케줄링
• 데이터 스트림

기본연산

• enqueue: 큐의 맨 뒤에 객체를 삽입
• dequeue: 큐의 맨 앞에 있는 객체를 제거하고 반환

시간 복잡도

• O(1)
  : 맨 앞이나 뒤의 객체를 다루기 때문에

데크(Deque)

📌 데크(Deque)란 무엇일까?

양 끝단에서 모두 입출력이 가능한 자료구조

특징

• 유연한 자료구조 : stack처럼 사용할 수도, queue처럼 사용할 수도 있음
• 양방향 탐색이 필요할 경우 사용
• 캐시 구현에 사용

기본연산

• addFirst: 데크의 맨 앞에 객체를 삽입
• addLast: 데크의 맨 뒤에 객체를 삽입
• removeFirst: 데크의 맨 앞에서 객체를 제거하고 반환
• removeLast: 데크의 맨 뒤에서 객체를 제거하고 반환
• peekFirst: 데크의 맨 앞 객체를 제거하지 않고 반환
• peekLast: 데크의 맨 뒤 객체를 제거하지 않고 반환

시간 복잡도

• O(1)
  : 맨 앞이나 뒤의 객체를 다루기 때문에