🥕 스택(Stack)
후입선출 LIFO(Last In First Out) 구조로, 자료를 순서대로 쌓아 보관하고 사용한다.
top으로 정한 곳을 통해 접근해 한 방향으로만 삽입(push)과 삭제(pop)가 이루어진다. (top은 가장 최근에 들어온 자료를 가리킨다.)
-
시간 복잡도 : O(1)
-
문제점 : 제일 상위 원소에만 접근할 수 있다.
-
사용 예시 : 뒤로가기, 역순 문자열 만들기, 실행 취소, 후위 표기법 계산, 수식의 괄호 검사 등에 사용된다.
stack overflow : 정해진 크기를 초과해 흘러 넘친 경우
🍆 큐(Queue)
선입선출 FIFO(First In First Out) 구조로, 먼저 들어온 데이터가 먼저 처리된다. 정해진 곳(top)에서만 삽입, 삭제가 이루어지는 stack과 달리 프론트(front)에서 삭제, 리어(rear)에서만 삽입이 이루어진다.
디큐(dnQueue) : 프론트에서 이루어지는 삭제 연산
인큐(enQueue) : 리어에서 이루어지는 삽입 연산
접근은 가장 첫 원소와 끝 원소로만 가능한다.
-
시간 복잡도 : O(1)
-
문제점 : 큐에 빈 메모리가 남아 있어도 꽉 차있는것으로 판단할 수 있다. (rear가 배열의 끝에 도달했을 경우)
-
해결 방안 : 원형 큐(순환 큐, 환영 큐 라고도 한다)
배열을 직선으로 보는 게 아닌 원형으로 보는 방법이다.- 원형 큐의 문제점 : 메모리 공간은 잘 활용하나 배열로 구현되어 있기 때문에 큐의 크기가 제한된다.
- 해결 방안 : 링크드리스트로 큐가 나왔다. 이 큐는 크기 제한이 없고 삽입 삭제가 편리하다.
- 원형 큐의 문제점 : 메모리 공간은 잘 활용하나 배열로 구현되어 있기 때문에 큐의 크기가 제한된다.
-
사용 예시 : 프로세스 처리, CPU관리, 우선순위가 같은 작업 예약(프린터의 인쇄 대기열), 은행 업무, 너비 우선 탐색 구현, 캐시 구현
🌽 덱(Deque)
Deque(Double Ended Queue)는 queue와 비슷하지만 front와 rear에서 삭제와 삽입이 모두 가능하다. 선언 후에 크기를 변경할 수 있어 가변적이다.
스크롤(Scroll) : 입력 제한 덱 (입력이 한쪽에서만 발생, 출력은 양쪽에서)
셸프(Shelf) : 출력 제한 덱 (입력은 양쪽에서 일어나고, 출력이 한쪽에서)
