Stack과 Queue / Array와 Linked List
Stack과 Queue 자료구조와 차이점
스텍(Stack)
스텍(Stack) 쌓다, 라는 의미로 데이터를 차곡차곡 쌓아올린 형태의 자료 구조를 말한다.
데이터가 순서데로 쌓이며 가장 마지막의 순서로 데이터가 먼저 삽입/삭제되는 구조를 가지고 있다.
보드게임 "젠가"로 예를 들자면 블럭을 쌓으면 가장 위의 블록부터 뺄 수 있도록 룰이 있는것이다.
예시)
- 웹 브라우저 방문기록(뒤로가기)
- 실행 취소
- 역순 문자열 만들기
- 후위 표기법 계산
큐(Queue)
큐(Queue) 는 대기 행렬, 동사로 줄을 서서 기다리다 라는 말로 사용되곤 한다.
스텍(Stack) 와 반대로 가장 첫 번째의 순서로 데이터가 삽입/삭제되는 구조를 가지고 있다. FIFO(First In First Out) 구조라고도 한다.
스텍과 똑같이 보드게임 "젠가"로 예를 들자면 블럭을 쌓으면 가장 아래의 블록부터 뺄 수 있도록 룰이 있는것이다.
예시)
- 은행 업무
- 대기열 순서와 같은 우선순위의 작업 예약
- 서비스 센터의 데기시간
- 프로세스 관리
Array와 Linked List 자료구조와 차이점
Array(배열)
Array(배열) 는 입력된 데이터들이 연속적인 공간에 순서데로 데이터를 저장하는 자료 구조이다.
데이터 공간 사이즈가 정해져 있다. 1, 2, 3...100 이면 100까지 1000이면 1000까지 정해져있다.
주로 빠른 접근이 요구되고, 데이터의 삽입과 삭제가 적을 때 사용된다.
장점
- indexing을 통한 빠른 접근이 가능하다.
단점
- 데이터 삽입 삭제가 오래 걸린다.
- 배열 중간에 있는 데이터가 삭제되면, 공간 낭비가 발생한다.
Linked List(연결 리스트)
Linked List(연결 리스트) 는 입력된 데이터들이 비 연속적인 공간에서 순서데로 데이터를 저장하는 자료 구조이다.
그리고 그 데이터가 Linked(연결) 되어 있다. 다른 말로 여러 개의 노드들이 순차적으로 연결된 형태를 갖는 자료구조이다.
첫번째 노드를 헤드(Head), 마지막 노드를 테일(Tail) 이라고 한다.
주로 삽입과 삭제 연산이 잦고, 검색 빈도가 적을 때 사용된다.
장점
- 노드가 연결된 구조이기 때문에 데이터 삽입, 삭제에 용이하다.
단점
- Linked List는 데이터를 저장하는 공간 + 다음 데이터를 연결하기 위한 공간이 필요하기 때문에 array에 비해 공간을 더 많이 차지한다.
- array와 다르게 데이터를 접근할 때 0번째부터 순차적으로 접근해야 하니, 데이터를 접근할때는 array보다 느리다.
Array와 Linked List 의 공통점
순서가 있는 데이터 저장을 위한 자료구조이다.