[CS][자료구조] 선형구조

선형 구조란?

• 데이터를 연속적으로 연결한 자료 구조
• 선형 구조의 종류 : 리스트, 스택, 큐, 데크

리스트(List)

• 데이터를 연속적으로 연결한 자료 구조(선형 구조)의 종류

선형 리스트(Linear List)

• 연속되는 기억 장소에 저장되는 리스트
• 장점 : 가장 간편한 자료 구조, 접근 구조가 빠름
• 자료의 삽입, 삭제 시 기존 자료의 이동이 필요

연결 리스트(Linked List)

• 노드 = 데이터 + 포인터(링크) : 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 자료구조
• 데이터를 담고 있는 노드들이 연결되어 있고, 노드의 포인터가 이전 노드와 다음 노드와 연결
• 장점 : 중간에 데이터를 변경하더라도 전체의 인덱스가 밀리거나 당겨지는 일이 없어 데이터의 추가/삭제가 편리
• 단점 : 인덱스가 없어 특정 데이터를 탐색하기 위해서는 순차 탐색이 필요하므로 탐색 속도가 저하

선형 리스트와 연결 리스트

• 선형 리스트 : 배열 -> 탐색/정렬
• 연결리스트 -> 데이터의 추가/삭제

Stack (스택)

• 한 방향으로만 자료를 넣고 꺼낼 수 있는 LIFO(Last-In Firtst-Out, 후입선출) 형식의 자료 구조

  

• 한 방향으로만 PUSH 와 POP 을 통해 자료를 넣고 꺼냄
• Top : 스택에서 가장 위에 있는 데이터

스택 연산

• PUSH : 데이터를 차례대로 스택에 삽입
• 스택의 자료 삽입

  If Top=n Then // 스택에 데이터가 n개면
    Overflow // 삽입 공간이 없으므로 오버플로우
  Else { // 스택에 데이터가 n개가 아니면
    Top = Top + 1 // 스택 포인터 Top 값을 1 증가
    insert S(Top) // 스택포인터가 Top이 가리키는 곳에 데이터 삽입
  }
  

• POP : 스택에서 가장 위에 있는 데이터를 하나씩 삭제
• 스택의 자료 삭제

  If Top=0 Then // 스택에 데이터가 0개면
    Underflow // 삭제할 데이터가 없으므로 언더플로우
  Else { // 스택에 데이터가 0개가 아니면
    remove S(Top) // 스택 포인터 Top이 가리키는 곳에 데이터 삭제
    Top = Top -1 // 스택 포인터 Top 값을 1 감소
  }
  

스택 응용 분야

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

Queue (큐)

• 한쪽 끝에서는 삽입이, 반대쪽 끝에서는 삭제 작업이 이루어지는 FIFO(First-In First-Out ; 선입선출) 형식의 자료 구조

• Front(Head) : 데이터를 꺼내는 쪽에서 가장 가까운 데이터
• Back(Tail, Rear) : 데이터를 넣는 쪽에서 가장 가까운 데이터

큐 연산

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

Deque (데크)

• 큐의 양쪽 끝에서 삽입과 삭제를 모두 할 수 있는 자료 구조

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

데크 연산

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