[DataStructure] 스택, 큐, 연결 리스트

스택, 큐, 연결 리스트

---

1. 스택

2. 큐

3. 연결 리스트

 

자료구조 복습하며 작성했습니다.

---

1. 스택

LIFO(Last in First Out)의 후입선출 구조입니다.

D (제일 마지막에 들어온 요소)

C

B

A (제일 처음 들어온 요소)

 

A부터 차례대로 제일 처음 들어온 요소부터 B -> C -> D 순서대로 들어오게 됩니다.

출력될 때는 D부터 늦게 들어온 요소부터 C -> B -> A 순서대로 나가게 됩니다.

 

2. 큐

FIFO(First in First Out)의 선입선출 구조입니다.

A

B

C

D

 

들어올 때는 스택과 같이 A부터 차례대로 A -> B -> C -> D 순서대로 들어옵니다.

나갈 때는 A부터 차례대로 A -> B -> C -> D 순서대로 나가게 됩니다.

 

3. 연결 리스트

- 순차리스트

배열(Array)라고 불리며, 연속된 메모리 공간에 데이터를 저장하는 자료구조입니다.

 

- 연결 리스트

각 노드가 데이터와 다음 노드를 가리키는 포인터(주소)를 포함하는 자료구조입니다.

 

- 원형 연결 리스트

연결 리스트에서 마지막 노드가 첫 번째 노드를 가리키는 자료구조입니다.

마지막 노드가 첫 번째 노드를 가리키기 때문에 원형으로 이루어져있습니다.

 

- 이중 연결 리스트

각 노드가 앞쪽과 뒤쪽 두 포인터를 가지고 있는 연결 리스트입니다.

각 노드는 이전 노드와 다음 노드를 가리킵니다.

 

- 연결 리스트로 구현한 스택

연결 리스트로 스택을 구현할 수 있습니다.

 

- 연결 리스트로 구현한 큐

연결리스트로 큐를 구현할 수 있습니다.

 

빠른 삽입/삭제가 필요하면 연결 리스트가 좋고, 빠른 인덱스 접근이 필요하면 배열을 선택하는 것이 좋습니다.

---

참고 사이트

[자료구조] 리스트, 스택, 큐

 

문제가 있으면 댓글 남겨주세요 !

피드백은 언제나 환영입니다 <3