자료구조가 스택 또는 큐로 구분되기 위한 규칙을 추상 자료형(ADT)라고 한다.
추상 자료형(ADT, Abstract Data Type)는 자료구조의 한 형태로, 해당 자료 구조가 어떤 동작을 수행할 수 있는지를 정의한 것이다.
자료구조의 방법이 코드로 정의된 것이 아니라 그 구조의 행동 양식만 정의된 것을 말한다.
스택(Stack)
스택(Stack: 쌓다)은 위로 쌓고 빼는 것만 가능하듯이 후입선출(LIFO) 구조로, 맨 위에 있는 항목만 접근 가능하다. 책을 쌓는 것과 비슷한 개념으로 맨 위에 있는 책만 꺼낼 수 있다.
- push(): 항목을 추가하는 것
- pop(): 항목을 제거하는 것
- peek(): 스택의 가장 위에 있는 항목을 반환
- isEmpty(): 스택이 비어 있을 때 true를 반환
스택의 장단점
장점
- 구조가 단순해서 구현이 쉽다.
- 데이터 저장/읽기 속도가 빠르다.
단점(배열 기반)
- 데이터 최대 개수를 미리 정해야 한다.
- 저장 공간 낭비가 발생할 수 있다.
스택은 언제 사용될까?
브라우저의 뒤로가기
웹 브라우저에 들어가면 스택에 해당 주소들을 저장해두었다가 뒤로가기를 누를 때 스택의 맨 위에 있는 한 페이지를 가져가는 것이다.
실행 취소(Ctrl + Z)
후위 표기법 계산
큐(Queue)
큐(Queue: 대기줄)는 선입선출(FIFO) 구조로, 먼저 들어온 데이터가 먼저 리턴되는 구조다. 줄을 서는 것과 비슷해서, 먼저 줄을 선 사람이 먼저 서비스를 받는 원리와 같다.
큐에서 항목을 추가하는 것을 인큐라고 하고, 항목을 제거하는 것은 디큐라고 한다.
- Enqueue : 큐에 데이터를 넣는 연산
- Dequeue : 큐에서 데이터를 꺼내는 연산
- peek : front에 위치한 데이터를 읽음. 다음 서비스를 받을 손님이 누구인지 확인
- front : 큐의 맨 앞
- rear : 큐의 맨 뒤
이러한 특성으로 작업 대기열, 네트워크 버퍼링에 사용된다.
큐는 언제 사용될까?
프로세스 관리
콜센터의 상담사
쇼핑몰에서 주문을 처리하는 방식
캐시
너비 우선 탐색
참고자료
나만의 무언가를 가진 프로그래머가 되자