TIL | 1.25.수 [CS 기초지식 | Stack / Queue / Array / Linked List]

[이전 관련 글]

 

2023.01.05 - [woncoding/TIL] - TIL | 1.3.화 [CS 기초지식 | 스택 / 큐]

TIL | 1.3.화 [CS 기초지식 | 스택 / 큐]

2023.01.05 - [woncoding/TIL] - TIL | 1.4.수 [CS 기초지식 | 배열 / 링크드리스트]

TIL | 1.4.수 [CS 기초지식 | 배열 / 링크드리스트]

 

---

 

- Stack / Queue

Stack : 차곡차곡 쌓아 올린 형태의 자료구조 즉, 시간 순서에 따라 자료가 쌓여서 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다는 구조적 특징으로 후입선출(LIFO, Last-In-First-Out) 구조를 갖고 있다.

 

[특징]

• 데이터를 집어넣을 수 있는 선형(Linear) 자료형
• 사용되는 Property(특성, 속성) 또는 메소드는 push(넣기), pop(빼기), peek(가장 마지막 집어넣은 데이터 확인)

 

 

 

Queue : 사전적 의미처럼 줄을 서서 기다리는 형태의 자료구조 즉, 선입선출(FIFO, First in first out) 방식의 자료구조 이다. → 한쪽 끝에서 삽입 작업이, 다른 쪽 끝에서 삭제 작업이 양쪽으로 이루어짐

 

[특징]

• 데이터를 집어넣을 수 있는 선형(Linear) 자료형
• 사용되는 Property 또는 메소드는 Enqueue, dequeue (shift)

 

👉 스택과 큐 모두 1차원 형태의 자료구조이다.

 

 

---

 

- Array / Linked List

Array : 배열은 특정 크기만큼 연속된 메모리 공간에 데이터를 저장하는 자료구조이다. 다만, 데이터를 빈번하게 추가하거나, 삭제할땐 효울적이지 못하다.

 

[특징]

• 삽입 순서대로 저장됩니다.(즉 새로 삽입되는요소는 array의 새로운 꼬리)
• 이미 생성된 리스트도 수정이 가능합니다.(mutable)
• 동일한 값도 여러번 삽입이 가능합니다.
• 다중차원 배열(Array의 요소가 array가 될 수 있습니다.)

[배열을 쓰는 경우]

• 순차열적인 데이터를 저장할 때
• 다차원 데이터를 다룰 때
• 어떠한 특정 요소를 빠르게 읽어야 할 때 (index로 바로 접근)
• 데이터의 사이즈가 자주 변하지 않을 때
• 요소가 자주 추가, 삭제가 되지 않을 때

 

Linked List : 배열과 달리 연속된 메모리 공간에 저장되어 있지 않다. 각각의 데이터가 메모리 공간 상에 고유한 노드로 존재한다. 그리고 이 노드는 자신의 앞에 있는 데이터와 뒤에 있는 데이터에 대한 주소를 기억하고 있다. → 따라서 데이터를 추가 하거나 삭제할때 복잡도가 현저히 줄어든다. 왜? 각 노드들이 가리키는 주소만 변경해주면 되기 때문에

 

[특징]

• head (첫 번째 데이터 참조)가 기본적으로 존재해야 한다.

 

 

- Array vs Linked List | 차이점