스택, 큐

자료 구조

스택(Stack), 큐(Queue)는 자료구조의 하나로, 데이터가 저장되는 방식을 말한다.

 

Stack

스택은 “쌓다”라는 뜻

스택은 가장 먼저 들어온 데이터가 가장 아래에 놓이고,
가장 나중에 들어온 데이터가 가장 위쪽에 놓인 후, 가장 위 쪽 데이터부터 처리하는 방식

 

후입선출(LIFO: Last In First Out)

 

Stack	스택
push(element)	스택의 최상단에 요소를 추가
pop()	스택에 최상단에서 요소를 제거하고 반환
size()	스택의 현재 요소 개수를 반환
top()	가장 마지막에 저장된 데이터의 인덱스
peek()	최근에 추가된(top) 데이터 조회
empty()	스택의 값이 비었는지 확인(비었으면 true, 아니면 false)

 

시간 복잡도(Time Complexity)

자료구조	가져오기	추가하기	삭제하기
Stack	O(n)	O(1)	O(1)

 

Queue

큐는 “기다리며 늘어선 줄”이라는 뜻

가장 먼저 들어온 데이터를 가장 먼저 처리하는 방식이다.

 

선입선출(FIFO : First In First Out)

Queue	큐
enqueue(element)	요소를 큐의 뒤에 추가
dequeue()	요소를 큐의 앞에서 제거하고 반환
size()	큐의 현재 요소 개수를 반환
front()	가장 먼저 들어온 데이터의 인덱스
rear()	가장 나중에 들어온 데이터의 인덱스
empty()	큐의 값이 비었는지 확인(비었으면 true, 아니면 false)

 

시간 복잡도(Time Complexity)

자료구조	가져오기	추가하기	삭제하기
Queue	O(n)	O(1)	O(1)