[Data Structure] 배열(array) / 큐(queue) / 스택(stack)

1. 배열 (Array)

• 같은 종류의 데이터를 효율적으로 관리하기 위해 사용
• 같은 종류의 데이터를 순차적으로 저장
• 장점 : 빠른 접근 가능
• 단점 : 데이터의 추가/ 삭제의 어려움 <= 미리 최대 길이를 지정해야함

# 1차원 배열
data_list = [1, 2, 3, 4, 5]

# 2차원 배열
data_list = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

02. 큐 (Queue)

• 줄을 서는 행위와 유사
• 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조 => FIFO(First-In, First-Out)
• 활용 : 멀티 태스킹을 위한 프로세스 스케쥴링 방식 구현에 사용
• Enqueue : 큐에 데이터를 넣는 기능 /  Dequeue : 큐에서 데이터를 꺼내는 기능

• Queue() : 가장 일반적인 큐 /  FIFO

import queue

data = queue.Queue()
data = put("apple")
data = put(3)

data.qsize() #2
data.get()   #인덱스를 입력하지 않음(FIFO) => 'apple'
data.qsize() #3
data.get()   #1

• LifoQueue() : LIFO(Last-In, First-Out) /  스택 구조

import queue

data = queue.LifoQueue()
data = put("apple")
data = put(3)

data.qsize() #2
data.get()   #3

• PriorityQueue() : 우선순위대로 출력

import queue

data = queue.PriorityQueue()
data = put((10, "apple"))
data = put((5, 1))
data = put((15, "banana"))

data.qsize() #3
data.get()   #(5,1)
data.get()   #(10, 'apple')

 

03. 스택 (Stack)

• 데이터를 제한적으로 접근할 수 있는 구조 => 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조
• 가장 나중에 넣은 데이터를 가장 먼저 뺄 수 있는 데이터 구조 => LIFO(Last-In, First-Out)
• 활용 : 컴퓨터 내부 프로세스 구조의 함수 동작 방식
• push() / pop()
• 장점
  • 구조가 단순해서 구현이 쉽다
  • 데이터 저장/ 읽기 속도가 빠르다
• 단점
  • 데이터 최대 갯수를 미리 정해야한다(파이썬의 경우 재귀함수는 1000번까지만 호출 가능)
  • 저장 공간의 낭비가 발생할 수 있다(미리 최대 갯수만큼 저장공간 확보 필요)
  • => 스택은 단순하고 빠른 성능을 위해 사용되므로, 보통 배열 구조를 활용함

stack_list = list()

def push(data):
	stack_list.append(data)
    
def pop():
	data = stack_list[-1]
    del stack_list[-1]
    return data
    
for index in range(10):
	push(index)
    
"""
range(start,stop,step)

range(5) : 0,1,2,3,4
range(1,6) : 1,2,3,4,5
range(0,6,2) : 0,2,4,6  
"""
    
pop() #9