선형 구조에 대해 알아보기!! 👐🏻

💡 선형 구조에 대해 알아보자!!

• 선형 구조란 데이터를 연속적으로 연결한 자료구조를 의미한다.
• 대표적으로 리스트, 스택, 큐, 데크가 있다.

📍리스트(List)

종류	설명
선형 리스트 (Linear List)	• 배열과 같이 연속되는 기억 장소에 저장되는 리스트 • 선형 리스트의 대표적인 구조로는 배열 (Array) 등이 있음 • 가장 간편한 자료 구조이며, 접근 구조가 빠름 • 자료의 삽입, 삭제 시 기존 자료의 이동이 필요
연결 리스트 (Linked List)	• 노드의 포인터 부분으로 서로 연결시킨 리스트 • 연결하는 방식에 따라 단술 연결 리스트, 원형 연결 리스트, 이중 연결 리스트, 이중원형 연결 리스트로 구분 • 노드의 삽입, 삭제가 선형 리스트와 달리 편리 • 연결을 위한 포인터가 추가되어 저장 공간이 추가로 필요 • 포인터를 통해 찾는 시간이 추가되어 선형 리스트에 비해 느림

📌 단어 알고 가기!!

• 노드(Node) ➡️ 데이터 저장 부분과 포인터 부분으로 구성된 저장 공간이다.
• 포인터(Pointer) ➡️ 현 위치에서 다음 위치를 알려주는 요소이다.

 

선형 리스트 표현!!

 

연결 리스트 표현!!

 

📍 스택(Stack)

➡️ 스택은 한 방향으로만 자료를 넣고 꺼낼 수 있는 LIFO(Last-In First-Out) 형식의 자료 구조이다.

 

스택 구성도 한눈에 알아보기!!

• 한 방향으로만 PUSH와 POP을 이용하여 자료를 넣고 꺼낸다.
• TOP은 스택에서 가장 위에 있는 데이터로, 스택 포인터(Stack Pointer)라고도 불린다.

📌 스택 연산

연산	설명
PUSH	데이터를 차례대로 스택에 넣는 연산
POP	스택에서 가장 위에 있는 데이터를 하나씩 꺼내는 연산

 

📌 스택의 자료 삽입, 삭제

 

연산	코드	설명
삽입	If Top = n Then    Overflow Else {     Top = Top + 1     insert S(Top) }	• 스택에 데이터가 n개이면 • 삽입할 공간이 없으므로 오버플로 • 스택에 데이터가 n개가 아니면 • 스택 포인터 Top 값을 1 증가 • 스택 포인터 Top가 가르키는 곳에 데이터 삽입
삭제	If Top = 0 Then    Underflow Else {     remove S(Top)     Top = Top - 1 }	• 스택에 데이터가 0개이면 • 삭제할 데이터가 없으므로 언더플로 • 스택에 데이터가 0개가 아니면 • 스택 포인터 Top이 가리키는 곳에 데이터 삭제 • 스택 포인터 Top 값을 1 감소

 

📌 스택 응용 분야

 

분야	설명
인터럽트의 처리	현재 진행 중인 명령어 위치를 스택에 PUSH하고, 인터럽트 발생 상황을 처리한 후에 인터럽트 전에 진행 중이던 명령어 위치를 스택에서 POP을 통해 받아옴
함수 호출 (재귀 호출 포함)	함수를 호출 시 현재 진행 중인 명령어 주소를 스택에 저장
후위표현 연산	Postfix를 계산할 때 사용
깊이 우선 탐색 (DFS; Depth-First Search)	깊이 내려갈 때마다 스택에 값을 PUSH하고, 더 이상 깊이 갈 곳이 없을 경우 스택에서 POP한 노드와 인접한 노드를 찾음

 

📍 큐(Queue)

➡️ 큐는 한쪽 끝에서는 삽입 작업이 이뤄지고, 반대쪽 끝에서는 삭제 작업이 이루어지는 FIFO(First-In First-Out) 형식의 자료구조이다.

큐 구성도 한눈에 알아보기!!

• 한쪽에서는 ENQUEUE 연산을 이용하여 데이터를 넣고, 한쪽에서는 DEQUEUE 연산을 이용하여 데이터를 꺼낸다.
• 데이터가 꺼내는 쪽에서 가장 가까운 데이터를 Head(Front)라고 하고, 데이터를 넣는 쪽에서 가장 가까운 데이터를 Tail(Rear)라고 한다.

📌 큐 연산

 

연산	설명
ENQUEUE	데이터를 차례대로 넣는 연산
DEQUEUE	처음 저장된 데이터로부터 하나씩 꺼내는 연산

 

 

📍 데크(Deque; Double Ended Queue)

➡️ 데크는 큐의 양쪽 끝에서 삽입과 삭제를 할 수 있는 자료 구조이다.

데크 구성도 한눈에 알아보기!!

• 두 개의 포인터를 사용하여, 양쪽의 삭제/삽입이 가능하다.
• 데크를 이용한 스택과 큐의 구현이 가능하다.

📌 데크 연산

연산	설명
PUSH	데이터를 차례대로 데크에 넣는 연산
POP	데크에서 Front와 Rear에 있는 데이터를 하나씩 꺼내는 연산