1. 자료구조 - 배열, 큐, 스택

[Python으로 진행하는 자료구조 공부]

단순히 혼자 기억을 상기시키는 목적의 글입니다

틀린 부분이 있을 수도 있으니, 발견 시 댓글로 남겨주시면 감사하겠습니다 :)

 

1. 배열

 

   : 동일한 타입의 데이터를 순차적으로 저장하는 구조

   : 각 데이터에 접근하기 위해서 인덱스를 활용함

   - 장점 : 인덱스를 활용하므로 데이터 요소에 접근이 쉬움

   - 단점 : 최대 배열 크기를 초기에 설정해 둬야 함. 따라서 데이터의 삭제와 삽입이 어려울 수 있음

                잔여 공간 크기보다 큰 데이터를 추가할 경우 추가가 불가능하며,

                정해진 크기의 배열에서 데이터 일부를 삭제하는 경우 저장 공간의 낭비가 발생함

 

   * 파이썬은 배열 기능을 리스트 타입이 제공함

 

   - 1차원 배열 : 인덱스는 0부터 시작.

   - 2차원 배열 : 배열이 2차원이므로 인덱스도 2차원으로 존재함

 

ar = [[0,1,2],[3,4,5],[6,7,8]]
print(ar[0])
>>> [0,1,2]
print(ar[1][2])
>>> 5

 

   - String이 나열되어 있는 리스트에서 특정 문자(A) 의 개수 세기

 

arr = ["Arr1", "Arr2", "Arr3", "Arr4", "Arr5"]
count = 0

for data in arr:
	for i in range(len(data)):
    		if data[i] == A:
    			count+=1
print(count)

>>> 5

 

 

2. 큐

   

   : FIFO ( First In First Out) -> 먼저 입력된 데이터가 먼저 출력되는 구조

   : 프로세스 스케줄링 과 유사한 구조

   - Enqueue = 큐에 데이터를 넣음

   - Dequeue = 큐에서 데이터를 꺼냄

 

   - 파이썬의 queue 라이브러리

•  . put : enqueue의 기능
•  .get : dequeue의 기능
•  .qsize : queue의 크기

     1) Queue : 가장 기본 구조의 큐 - FIFO 정책

 

import queue

data = queue.Queue()  #Create New Queue

data.put(2)
data.put(3)
data.qsize()
>>> 2
data.get()
>>> 2
data.get()
>>> 3
data.qsize()
>>> 0

     

     2) LifoQueue : 스택과 유사. 나중에 입력된 데이터가 가장 먼저 출력

 

import queue

data = queue.LifoQueue()

data.put(2)
data.put(3)
data.get()
>>>3
data.get()
>>>2

# 일반적인 Queue와는 다른 출력 순서임을 확인할 수 있음

   

      3) PriorityQueue : 우선순위를 설정하고, 우선순위를 높은 순으로 데이터를 출력함

                            : 작은 숫자일수록 우선순위가 높은 것

 

import queue

data = queue.PriorityQueue()

# 앞에 저장하는 수가 우선 순위를 의미함
# 이 수가 작을 수록, 우선 순위는 높은 것
data.put((10,"apple"))
data.put((4,120))
data.put((13,12))

data.get()    # 가장 우선 순위가 높은 데이터부터 출력되는 것을 볼 수 있음
>>> (4,120)
data.get()
>>> (10,'apple')

 

3. 스택

 

   : LIFO ( Last In First Out) -> 마지막에 넣은 데이터를 가장 먼저 출력하는 구조

   : 프로세스 구조의 함수 동작 방식, 재귀함수 사용 방식

• . push : 스택에 데이터를 넣는 기능
• . pop : 스택에서 데이터를 꺼내는 기능

    * 파이썬에서는 push의 기능을 list의 append로 구현할 수 있음

   

   - 원래 정의된 함수 사용

 

data_list = []

data_list.append(2)
data_list.append(5)

data_list
>>> [2,5]

data_list.pop()
>>>5
data_list.pop()
>>> 2

   

 

 

   * 재귀 함수

      : 실행 과정이 스택과 유사

      : 함수 정의에 함수 자신을 다시 호출해서 반복 실행되게 하는 것

      : 함수의 호출 반복이 끝날 때까지, 호출하는 부분 뒤의 실행문은 실행되지 않음

 

def RecursiveFunc (num):
	if num ==0:    # Stop condition이 필요하다
    		print("End")
   	else:
   		print(num, end = '')
        	RecursiveFunc(num-1)    #재귀 함수 호출
        	print("Closed " + (num-1))

RecursiveFunc(8)
>>> 8 7 6 5 4 3 2 1 End 
# 재귀 함수 호출 뒤의 문장이 실행됨
>>> Closed 0  		     #RecursiveFunc(1) 내에서, RecursiveFunc(0)이 종료된 후 print문의 실행 결과
>>> Closed 1
>>> Closed 2
>>> Closed 3
>>> Closed 4
>>> Closed 5
>>> Closed 6
>>> Closed 7