[1. 자료구조 이론] 배열(List), Queue, Stack

1. 배열 

   : 데이터를 나열하고, 각 데이터를 인덱스에 대응하도록 구성한 데이터 구조

   : 파이썬은 별도의 Array타입이 존재하는 것이 아니라 list를 활용

   : 같은 종류의 데이터를 효율적으로 관리하기위해 사용

      ➡︎ 순차적으로 저장 (연속되고 연결된 공간에 저장)

      ➡︎ 인덱스를 통해 각각의 데이터에 접근 가능

    : 인덱스를 통한 빠른 접근 가능 : 첫번째 위치에서 상대적인 위치로 접근

    : 가변적 데이터 구조가 아님 (immutable) - 초기에 배열의 크기를 설정해야함

    : 데이터 추가 및 삭제가 어려움 : 기존 길이 초과시 데이터 추가 어려움, 중간 데이터 삭제시 데이터 재정렬 필요

   * 파이썬에서의 배열

      : list를 사용해서 구현하기 때문에 길이 지정 필요없음, 가변적이게 사용가능

      : 배열 생성

       1) python_list=[1,2,3] ⇨ 직접 대괄호 안에 작성

       2) python_list=list() ⇨ 빈 리스트 생성

      : 배열 요소 추가 ⇨ append(data)

      : 배열 요소 삭제 ⇨ del python_list[index]

# 배열 생성
# 방법1) list() 사용하여 빈 배열 선언
data_list = list()
print(data_list)  #[]
# 방법2) 간단히 대괄호에 데이터를 넣어 선언
data_list = [1,2,3,4]
print(data_list)  #[1,2,3,4]

# 배열값 추가
# list.append(data)
data_list.append(5)
print(data_list)  #[1,2,3,4,5]

# 배열값 삭제
# del list[index]
del data_list[0]
print(data_list)  #[2,3,4,5]

    

 

 

2. 큐(Queue)

   : FIFO(First in First Out) - 선입선출 구조

   : 특정 순서의 자료를 추출하는것이 아니라 무조건 순차적 처리

   : 매표소 앞에 줄을 서고 표를 구매하는 순서를 기억!

   : 프로세스 스케줄링 방식 구현시 주로 사용

     * 파이썬에서 큐 구현

      : 큐 라이브러리 사용 ➡︎ import queue

      : 다양한 구조의 큐를 지원

         1) Queue() : 일반적인 FIFO구조의 큐

         2) LifoQueue() : 스택과 같은 구조의 큐 - 나중에 입력된 데이터가 먼저 추출되는 구조

         3) PriorityQueue() : 데이터마다 우선순위를 지정하고 그 우선순위가 높은 순으로 데이터 추출 - 저장순서 무의미(낮을수록 높은것)

# 큐생성 위해 라이브러리 사용
import queue
# 1) FIFO Queue
data_queue=queue.Queue()
# 2) LIFO Queue
data_queue=queue.LifoQueue()
# 3) Priority Queue
data_queue=queue.PriorityQueue()

     : 큐 데이터 삽입 ⇨ Queue.put(data)

     : 큐 데이터 추출 ⇨ Queue.get()

import queue
data_queue=queue.Queue()
# FIFO,LIFO삽입시 : put
data_queue.put(100)
data_queue.put("korea")
print(data_queue) # [100, "Korea"]

# Priority 삽입시 튜플단위로! 즉, 괄호로 묶어서 (우선순위,값)으로 삽입
prior_queue=queue.PriorityQueue()
prior_queue.put((1,"Nate"))
prior_queue.put((15,"Peter"))
prior_queue.put((8,"Brad"))

# 데이터 추출시 : get()
data_queue.get()   #100
data_queue.get()   #Korea
prior_queue.get()  #Nate
prior_queue.get()  #Brad
prior_queue.get()  #Peter

     * 파이썬 queue 내장함수 사용하지 않고 list를 활용하여 큐 구현

queue_list = list()

def enqueue(data):
    queue_list.append(data)
    
def dequeue():
    data = queue_list[0]
    del queue_list[0]
    return data

 

 

3. 스택(Stack)

   : LIFO(Last in First Out) - 후입선출 구조

   : 특정 순서의 자료를 추출하는것이 아니라 무조건 순차적 처리

   : 접시를 차곡차곡 쌓고 가장 마지막에 쌓은 접시 먼저 활용하는 방식과 동일

   : 구조가 단순하여 구현이 쉽고, 데이터 저장 및 읽기 속도 우수

      ➡︎ 단, 데이터 저장 개수(재귀함수 호출 개수)를 미리 정해야하며 제한적임 : 공간 낭비 발생 우려

   : 컴퓨터 내부 프로세스 실행 구조의 기본 및 재귀함수시 데이터 관리 정책

     * 프로세스 실행구조 표현 with 재귀함수

def recursive(data):
    if data < 0:
        print ("the end")
    else:
        print(data)
        recursive(data-1)
        print("returned", data)  
        
recursive(4)
'''
4
3
2
1
0
ended
returned 0
returned 1
returned 2
returned 3
returned 4
'''

 

     * 파이썬에서 스택 구현

      : list를 이용하여 구현하며, 이미 list내장함수인 append(d)를 통해 put기능을 사용하고 pop()기능을 통해 pop기능을 사용

data_stack = list()
data_stack.append(1)
data_stack.append(2)
print(data_stack)  #[1,2]

data_stack.pop()   #2
print(data_stack)  #[1]

     * 파이썬 list 내장함수 사용하지 않고 스택 함수 구현

stack_list = list()

def push(data):
    stack_list.append(data)

def pop():
    #뒤에서 인덱스 세는 경우 -1부터 -1씩!
    data = stack_list[-1]
    del stack_list[-1]
    return data