스택, Stack
스택이란 책을 쌓는 것처럼 차곡차곡 쌓아 올린 형태의 자료구조를 말합니다.
특징
스택은 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있고, top으로 정한 곳을 통해서만 접근할 수 있습니다. 덧붙여 top은 가장 최근에 들어온 자료를 가리키고 있습니다.
스택에서는 자료의 삽입(push)과 삭제(pop)가 모두 top을 통해서만 이루어집니다.
정리하자면 스택은 시간 순에 따라 자료가 쌓여 가장 마지막에 삽인된 자료가 가장 먼저 삭제된다는 구조적 특징을 가지며 이러한 구조를 후입선출(LIFO, Last In First Out) 구조라고 부릅니다.
활용
- 웹 브라우저의 뒤로가기
- 역순 문자열 만들기
- 실행 취소(undo)
- etc...
큐, Queue
큐는 사전적인 의미로 (무엇을 기다리는 사람, 자동차 등의) 줄, 혹은 줄을 서서 기다리는 것을 의미합니다.
한마디로 큐는 줄을 서는 것과 같은 형태의 자료구조를 말합니다.
특징
정해진 한 곳을 통해서만 삽입, 삭제가 이루어지는 스택과는 달리
큐는 한 쪽 끝에서는 삽입(offer) 작업이 다른 한 쪽 끝에서는 삭제(poll) 작업이 이루어집니다.
이때 삭제 연산만 수행되는 곳을 프론트(front)라고 부르며, 삽인 연산만 이루어지는 것을 리어(rear)로 정하여 맡은 연산만을 수행합니다.
리어에서 이루어지는 삽입 연산을 인큐,
프론트에서 이루어지는 삭제 연산을 디큐라고 부른다.
정리하자면 큐는 리어로 자료가 들어와 자료가 쌓이며, 쌓이게된 자료는 가장 먼저 쌓인 자료부터 차례대로 프론트로 나가게 되는 자료구조 형태인데, 이러한 구조를 선입선출(FIFO, First In First Out) 구조라고 부릅니다.
활용
- 우선 순위가 같은 작업 예약(프린터의 인쇄 대기열 등)
- 은행 업무
- 콜센터 고객 대기시간
- 너비 우선 탐색(BFS) 구현
- etc...
ArrayList
ArrayList는 중복을 허용하고 순서를 유지하며 인덱스로 원소들을 관리한다는 점에서 배열과 상당히 유사합니다. 다만, 일반 배열은 크기가 지정되며 고정되지만 ArrayList는 클래스이기 때문에 배열을 추가, 삭제할 수 있는 메서드들도 존재합니다.
하지만 추가했을 때 배열이 동적으로 늘어나는 것이 아니라 용량이 꽉 찼을 경우에는 더 큰 용량의 배열을 만들어 옮기는 작업을 하게 됩니다.
특징
- 연속된 메모리 공간에 순차적으로 저장한다.
- 배열의 크기는 고정되어 있다.
- 데이터를 검색하고 확인할 때 시간복잡도 O(1)의 속도로 작업이 가능하다.
- 임의적 접근(Random Access)이 가능하다.
임의적 접근이란 인덱스를 사용하여 바로 접근할 수 있는 것을 뜻한다.
연결 리스트, LinkedList
LinkedList는 내부적으로 양방향의 연결 리스트로 구성되어 있어서 참조하려는 원소에 따라 처음부터 순방향 또는 역방향으로 순회할 수 있다.
이러한 특징 때문에 ArrayList에 비해 비순차적인 데이터의 추가 또는 삭제에 용이합니다.
특징
- 연결 리스트의 각 노드(원소)들은 포인터를 기반으로 연결되어 리스트를 구성한다.
- 각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어진다.
- 반드시 연결된 노드를 통해서만 접근이 가능하다.
- 데이터의 삽입과 삭제에 용이한 반면, 검색 성능은 좋지 않다.
- 크기가 고정되어 있지 않아 크기 제한에서 자유로운 반면 포인터로 인한 저장 공간의 낭비가 발생한다.
Reference
[자료구조] 스택 (STACK), 큐(QUEUE) 개념/비교 /활용 예시
선형 자료구조 : 배열(Array), 연결리스트(linked list), 스택(Stack), 큐(Queue)
ArrayList와 LinkedList의 차이
[JAVA] ArrayList와 LinkedList의 차이
array(배열)과 arrayList(리스트)의 차이
