TIL | 배열 / 스택 / 큐

1. 배열(Array)

1.1 배열의 정의

• 같은 자료형을 갖는 여러 원소를 하나의 변수 이름으로 모아 놓은 데이터의 집합

1.2 배열의 특징

• 배열은 물리적인 개념과 추상화한 위치가 서로 같다.
• 배열의 순서는 메모리 공간에서 저장되는 원소 값의 물리적 순서이다.
• 배열의 형태는 다음과 같다.

index(abstract value), value(real value) => 1:1 mapping

• 예) <index, value> : <1, 24>
• A 라는 int 배열이 있다고 가정해보자.
• A[0] = 1 A[1] = 2 . . .
• 배열은 인덱스를 가지는 특성으로, 배열의 원소 값에 직접 접근할 수 있다.
• 인덱스와 주소값의 관계는 다음으로 설명할 수 있다.
• 물리적 주소 : 값 : 추상화된 주소 ooggti00 : 100 : 0 ooggti04 : 200 : 1 ooggti08 : 300 : 2 ooggti0c : 400 : 3
• 컴파일러, OS단의 시스템 소프트웨어는 메모리에 값을 할당할 때는 물리적 주소로 지정한 위치에 값을 할당하지만, 개발자는 추상화된 주소로 값의 위치를 파악할 수 있다. 이때 메모리에 할당된 값들은 프로그램이 시작될 때마다 바뀔 수 있으며 정해진 주소는 아니지만, 메모리에 추상화된 주소로 할당되어 있다는 것이 아님을 기억하는 게 중요하다.

1.3 배열의 추상자료형(Abstract Data Type Array)

• 추상 자료형 : 객체와 관련된 연산의 정의
• 예) C 에서의 printf, C#에서의 console.write 등
• 자료형 : 메모리 저장 할당을 위한 선언
• 예) int로 선언하면 메모리에 8bit를 할당할 것을 의미, float로 선언하면 메모리에 16bit를 할당하는 것을 의미.

그래서 배열의 추상자료형(ADT Array)이란 무엇이냐면,
: 배열의 추상자료형은 개념을 일반화로 표현한 형태. 달리 말하면 배열의 가이드 라인이라고도 할 수 있다.

The array is a basic abstract data type that holds an ordered collection of items accessible by an integer index. These items can be anything from primitive types such as integers to more complex types like instances of classes. Since it's an ADT, it doesn't specify an implementation, but is almost always implemented by an array (data structure) or dynamic array.
Array (ADT)

Array (ADT) | Brilliant Math & Science Wiki

• Array Object ; < i ∈ Index, e ∈ Element > 로 이루어진 집합.
  (i;순서를 나타내는 indext의 유한한 집합의 원소, e;타입이 같은 element의 원소)2) Element retrieve(a, i); 원소 검사(배열, 첨자) ::= if(i ∈ Index)
  then { return the i-th value 'e' in array }
  else { return error message }
• 3) Array 저장; Array store(a, i, e) ::= if (i ∈ Index)
  then { returns the array 'a' that store the value 'e' in the i-th }
  else { returns error message, if index is over the size of array }
• 1) Array 생성; Array create(n) ::= Create empty array of size n, and return array

1.4 2차원 배열, 행렬의 표현

• 행렬의 2차원 배열 표현에서 배열의 확장은 행이 우선인지 열이 우선인지 여부에 따라 좌표가 지정되는데,
  어떤 기준으로 할당할 것인지를 알아야만 반복문에서 변수 할당 고민을 적게 할 수 있다. (생각하자!)

A[4][5]

0,0  0,1  0,2  0,3  0,4 
1,0  1,1  1,2  1,3  1,4
2,0  2,1  2,2  2,3  2,4
3,0  3,1  3,2  3,3  3,4

• 행을 우선해서 할당하는 행렬의 경우

GGG
BBB

G
G
G
B
B
B

• 열을 우선해서 할당하는 행렬의 경우

RGB
RGB

R
R
G
G
B
B

1.5 희소 행렬(sparse matrix)

• 희소 행렬은 0으로 할당된 빈 공간의 값들을 제외하고 0이 아닌 값을 가지는 값만 할당한 배열의 형태
• 실제 위치는 할당된 위치와 물리적 위치가 다르다.
• 희소행렬 나무위키

희소행렬 - 위키백과, 우리 모두의 백과사전

 

2. 스택(Stack)

2.1 스택의 정의

• 스택이란 가장 먼저 입력된 자료가 가장 나중에 출력되는 관계를 표현한 자료구조

2.2 스택의 추상자료형

• 객체와 그 객체가 저장되는 순서를 기억하는 방법에 관한 추상 자료형
• 스택의 추상 자료형에서 정의된 연산은 시스템 개발자에 따라 다르게 정의 및 구현할 수 있고, 컴파일러 설계자에 따라 프로그래밍 언어에서
  다르게 제공될 수 있다.

2.3 스택의 특징

• 0개 이상의 원소를 갖는 유한 순서 리스트
• push(add), pop(delete) 연산이 한 곳에서 발생되는 자료구조
• 시스템 스택(system stack) ; 변수의 메모리 할당과 수집을 위해 운영체제가 관리하는 스택
• 시스템 스택, 서브루틴 호출, 수식의 계산에 활용됨

2.4 연산자 표기법(operator notation)

• 중위 표기법(infix notation) ; 피연산자 사이에 연산자를 표기하는 방법, 가장 많이 사용되는 표기방법(A+B)
• 전위 표기법(prefix notation) ; 피연산자 앞에 연산자를 표기하는 방법 (+AB)
• 후위 표기법(postfix notation) ; 피연산자 뒤에 연산자를 표기하는 방법 (AB+)

 

3. 큐(Queue)

3.1 큐의 정의

• 큐는 한쪽에서는 데이터의 삽입이, 다른 한 쪽에서는 데이터의 삭제가 발생하도록 정의된 자료구조
• 먼저 삽입된 원소가 먼저 삭제되어 First-In-First-Out; FIFO 또는 First-Come-First-Serve; FCFS의 알고리즘을 갖는 순서 리스트

3.2 큐의 추상자료형

• object를 순차적으로 보관하는 구조
• 큐의 앞(front/head) : 원소의 삭제연산이 이루어지는 위치
• 큐의 뒤(rear/tail) : 원소의 삽입연산이 이루어지는 위치

3.3 큐의 특징

• 큐는 원소의 순서에 따라 서비스가 공평하게 이루어지므로, 자원의 할당을 받는 작업들간의 순서를 관리하는 경우에 사용됨(CPU 할당)
• 큐의 삭제 연산 후에 빈 공간이 남겨지는데, 빈 공간 활용을 높이기 위해 원형 큐를 생성할 수 있음

3.4 큐를 활용한 스케줄링 기법

• FCFS 스케줄링 기법 or FIFO 스케줄링 기법 ; 작업이 준비된 큐에 도착한 순서대로 CPU 할당을 받도록하는 기법
• RR 스케줄링 기법 ; 작업이 도착한 순서대로 CPU가 할당되지만, CPU의 시간 할당량 or 시간 간격에 의해 제한을 받음. 일정한 크기의 시간 할당량을 모든 작업에게 주고 그 시간동안 작업이 완료되지 못하면 준비 큐의 맨 뒤에 다시 배치됨.

*본 내용은 방송대 자료구조 수업 내용을 요약하여 작성되었습니다.