선형리스트1(Array Stack, Array Queue )

📚 Array Stack

💡배열이란?

연속적인 주소의 메모리에 원소들이 순차적으로 저장되어 있는 데이터 구조.

• 배열의 특징
  1. 배열 안에 있는 원소에 대해 상수 시간의 접근 가능하다.
  2. 동적이지 않다. 배열을 사용해서 만든 리스트 중간에 원소를 추가하거나 삭제할 때 많은 복사가 일어남.
  3. 확장되거나 축소될 수 없다. 원소의 수가 현재 할당된 배열의 크기보다 많아지면, 새로운 배열을 할당받아 기존 원소를 복사해야 한다.

💡살펴볼 ArrayStack

배열(a) 기반으로 List인터페이스를 구현한 것.

• List 인터페이스란?
  1. get, set, add, remove를 지원하는 인터페이스를 의미
  2. a[i]와 같이 i번째 원소에 접근 가능
  3. 실제로 담겨 있는 원소의 수를 n으로 나타냄
  4. a[0],...a[n-1]에 원소가 저장됨
  5. 항상 length(a) >= n

🗣️( 데이터 구조에 따라서 해당 배열에 원소들에 이동이 발생함에 따라, 효율적이지 않은 데이터 구조이다. )

• get, set, add, remove

initialize()
a <- new_array(1) # 새로운 배열을 생성하여 a변수에 저장
n <- 0 # 총 원소 
-> [] # 빈 배열

get(i)
#시간복잡도 O(1) 
	return a[i] 

set(i,x)
#시간복잡도 O(1)
	y <- a[i]
	a[i] <- x
	return y

add(i,x)
# n - i 개의 원소를 옮기기 때문에 시간복잡도 O(n - i)
# 배열이 원소로 꽉 차면 배열의 크기 조정
	if n = length(a) then resize()
# 마지막 원소부터 i번째 원소까지 한칸씩 오른쪽으로 이동
	a[i + 1, i + 2, ... ,n] <- a[i, i + 1, ..., n - 1]
	a[i] <- x
	n <- n + 1

remove(i)
# n - i - 1개의 원소를 옮기기 때문에 시간복잡도 O(n - i)
	x <- a[i]
# 마지막 원소부터 i + 1번째 원소까지 한칸씩 왼쪽으로 이동
	a[i, i + 1, i + 2, ... ,n - 2] <- a[i + 1, i + 2, ..., n - 1]
    n <- n - 1
# 배열의 길이가 총 원소 수의 3배보다 같거나 크면 배열의 크기 조정
	if length(a) >= 3 * n then resize()
    return x

resize()
# 시간복잡도 O(n)
# 원소의 개수 * 2 만큼의 공간을 새로운 배열로 할당
	b <- new_array(max(1, 2 * n))
# 새로운 배열로 기존 원소 복사
	b[0, 1, ..., n - 1] <- a[0, 1, ..., n - 1]
    a <- b # 기존 변수가 새로운 배열을 가리키도록 저장 

• 🗣️ 요약 :
  ArrayStack은 배열을 이용해 List인터페이스를 구현한다. 이때 resize() 호출에 드는 비욜을 무시하면, get(i)와 set(i,x)는 O(1)의 시간복잡도를 가지고 add(i,x)와 remove(i)는 O(n - i)의 시간복잡도를 가진다.

📚 Array Queue

💡Array Queue란?

• FIFO(First In First Out) 인터페이스를 구현하는 큐(Queue)
  1. FIFO(First In First Out) 인터페이스 : add, remove.
  2. remove 호출시 논리적인 순서의 처음(head) 부분의 원소가 삭제됨.
  3. add 호출시 논리적인 순ㄴ서의 끝(tail) 부분의 원소가 추가됨.

• Modular Arithmetic
  1. 배열로 큐를 구현하기 위해서, 배열의 크기가 무한하다고 가정하면 편리.
  2. 무한한 큐를 흉내내기 위해 mod(ular) 연산을 사용.
     • 15 mod 12
     • 15 % 12 = 3
  3. a[i mod length(a)]
     • 인덱스 i가 length(a)보다 클 경우, 배열의 처음부터 시작하게 되어 배열을 순환하는 구조처럼 사용 가능.

• get, set, add, remove

initialize()
a <- new_array(1) # 새로운 배열을 생성하여 a변수에 저장
n <- 0 # 논리적인 순서의 처음을 나타내는 인덱스(head)
n <- 0 # 총 원소 
-> [] # 빈 배열

add(x)
# 시간복잡도 O(1)
# 배열a가 꽉 차면 배열의 크기 조정
	if n + 1 > length(a) then resize()
# j(haed)로부터 n만큼 증가한 인덱스(=tail)에 mod 연산을 적용
	a[(j + n) mod length(a)] <- x # tail = (j + n)
	n <- n + 1
	return true

remove()
# 시간복잡도 O(1)
	x <- a[j]
# j를 1증가하여 head를 삭제 (이후 연산에서 j-1번째 원소를 무시하게 되므로)
	j <- (j + 1) mod length(a)
    n <- n - 1
# 배열의 길이가 총 원소 수의 3배보다 같거나 크면 배열의 크기 조정
	if length(a) >= 3 * n then resize()
    return x

resize()
# 2n 크기의 새로운 배열을 생성
	b <- new_array(max(1, 2 * n))
# j(head)로부터 k번째 원소를 새로운 배열의 k번째에 저장
for k in 0,1,2,...n,n - 1 do
	b[k] <- a[(j + k) mod length(a)]
a <- b # 새로운 배열을 기존 변수에 저장
j <- 0 # head reset

• 🗣️ 요약 :
  ArrayQueue는 FIFO인터페이스를 구현한다. 이때 resize() 호출에 드는 비욜을 무시하면, add(x)와 remove()는 O(1)의 시간복잡도를 가진다.