큐, 스택

자료구조

• 대량의 데이터를 효율적으로 관리할 수 있는 데이터의 구조를 의미
• 어떤 데이터 구조를 사용하느냐에 따라, 코드 효율이 달라진다.
• 대표적인 자료구조 (배열, 스택, 큐, 링크드 리스트, 해쉬 테이블, 힙 등)

알고리즘

• 어떤 문제를 풀기 위한 절차 / 방법
• 어떤 문제에 대한 원하는 출력을 얻을 수 있도록 만드는 프로그래밍

어떤 자료구조와 알고리즘을 사용하느냐에 따라 성능이 천지차!

파이썬과 C언어의 배열 예제

#include <stdio.h>

int main(int args, char* argv[])){
    char country[3] = "US";
    printf("%c%c\n", country[0], country[1]);
    printf("%s\n", country);
    return 0;
}

country = 'US'
print(country)

country = country + 'A'
print(country)

파이썬과 배열

• 파이썬 리스트 활용

1차원 배열 - 리스트

data = [1,2,3,4,5]
print(data)

2차원 배열 - 리스트

data = [[1,2,3], [4,5,6], [7,8,9]]

예제

• dataset 리스트에서 M이 몇번 들어갔는지 계산

m_count = 0
for data in dataset:
    for index in range(len(data)):
        if data[index] == 'M':
            m_count += 1
print(m_count)

큐

• 줄을 서는 행위와 유사
• 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조 (FIFO)
• Enqueue: 큐에 데이터를 넣는 기능
• Dequeue: 큐에서 데이터를 꺼내는 기능
• 멀티 태스킹을 위한 프로세스 스케쥴링 방식을 구현하기 위해 많이 사용됨
  • 큐는 딱히 장단점으로 언급할 만한 것이 없다. 스케쥴링 방식 구현과 연관 되어있다 정도만 기억

라이브러리

• Queue(): 가장 일반적인 큐 자료 구조
• LifoQueue(): 나중에 입력된 데이터가 먼저 출력되는 구조 (스택 구조라고 보면 됨)
• PriorityQueue(): 데이터마다 우선순위를 넣어서, 우선순위가 높은 순으로 데이터 출력

Queue

import queue

data_queue = queue.Queue()  
data_queue.put("funcoding") # put : 데이터 삽입
data_queue.put(1)
data_queue.qsize()    # 큐의 데이터 개수 
data_queue.get()    # 큐의 데이터 출력 

큐는 데이터를 꺼내올 때 특정 값을 꺼내 오지 않고 처음 들어온 값을 꺼내기 때문에 별도의 인자는 없다.

LifoQueue

import queue
data_queue = queue.LifoQueue()

스택과 같은 형태로 LIFO 구조를 갖게 된다.

PriorityQueue

import queue

data_queue = queue.PriorityQueue()
data_queue.put((10, "korea"))
data_queue.put((5, 1))
data_queue.put((15, "china"))
data_queue.get()    # 가장 높은 우선순위를 가진 (5, 1) 출력

데이터를 넣을 때 우선순위를 같이 부여해서 꺼내올 순위를 지정한다.

Enqueue, Dequeue

queue_list = list()

def enqueue(data):
    queue_list.append(data)

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

for index in range(10):
    enqueue(index)

len(queue_list)

dequeue()

리스트 변수로 큐를 다룬다.

스택

• 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조
• 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조 (LIFO)

push : 데이터를 스택에 넣기

pop : 데이터를 스택에서 꺼내기

스택 구조는 프로세스 실행 구조의 가장 기본 - 함수 안에서 다른 함수가 동작하고 다른 함수가 먼저 종료

# 재귀 함수
def recursive(data):
    if data < 0:
        print("ended")
    else:
        print(data)
        recursive(data - 1)
        print("returned", data)

recursive(4)

• 4, 3, 2 , 1 , 0 , ended, return 0 , 1, 2 , 3 ,4 출력
• recursive(-1) 까지 호출이 돼야 한다.

스택 장단점

• 장점
  • 구조가 단순해서 구현이 쉽다.
  • 데이터 저장 / 읽기 속도가 빠르다.
• 단점 (일반적인 스택 구현시)
  • 데이터의 최대 갯수를 미리 정해야 한다.
    • 파이썬의 경우 재귀 함수는 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)
pop()

파이썬에선 기본적으로 pop() 을 제공하며 push 는 append로 사용한다.