큐와 스택

Algorithm 2022. 1. 27. 17:25

Queue

큐는 스택과 같이 데이터를 임시 저장하는 자료구조이다(배열을 사용하여 구현 가능).

가장 먼저 넢은 데이터를 가장 먼저 꺼내는 선입선출(FIFO) 구조이다.

컴퓨터에서 데이터를 주고받을 때 각 주변장치들 사이에 존재하는 속도의 차이나 시간차이를 극복하기 위한 임시 기억 장치로 큐가 사용되는데, 이것을 buffer라고 한다.

큐에 데이터를 추가하는 작업을 인큐(enqueue), 데이터를 꺼내는 작업을 디큐(dequeue). 데이터를 꺼내는 쪽을 front, 넣는 쪽을 rear라고 한다.

위의 배열은 원소 24를 인큐하고 19를 디큐하는 작업이다. 인큐는 맨 뒤의 인덱스에 추가하면 그만이기 때문에 복잡도는 O(1)으로 적은 cost로 구현 가능하다. 하지만 디큐는 맨 앞의 원소를 꺼낸 후 모든 원소를 앞쪽으로 옮겨야 한다. 이때의 처리 복잡도는 O(n)이다. 데이터가 늘어난다면 효율성을 기대할 수 없다.

링 버퍼로 큐 구현

Ring buffer 자료구조는 디큐할 때 배열 안의 원소를 옮기지 않는다. 배열 맨 끝의 원소 뒤에 맨 앞의 원소가 연결되는 자료구조이다. 원소의 맨 앞과 끝은 front와 rear 변수로 구분한다.

인큐와 디큐를 수행하면 front와 rear의 값은 변한다. (front와 rear는 논리적인 데이터 순서일 뿐 물리적 원소의 순서가 아니다.)

원소를 옮길 필요 없이 front와 rear의 값을 업데이트하는 것만으로 인큐와 디큐를 수행할 수 있다. 모든 처리의 복잡도는 O(1)이다.

링버퍼 큐

<code>

# -- fixed_queue.py

class FixedQueue:
    class Empty(Exception):
        pass
    
    class Full(Exception):
        pass
    
    
    def __init__(self, capacity):
        self.no = 0   # 현재 데이터의 개수
        self.front = 0   # 맨 앞 원소 커서
        self.rear = 0     # 맨 뒤 원소 커서
        self.capacity = capacity # 큐의 크기
        self.que = [None] * capacity # 큐의 본체
        
    def __len__(self):
        return self.no
    
    def is_empty(self):
        return self.no <= 0
    
    def is_full(self):
        return self.no > self.capacity
    
    def enque(self, x):
        '''데이터 x를 인풋'''
        if self.is_full:
            raise FixedQueue.Full # 큐가 가득 차 있는 경우 예외 처리 발생
        self.que[self.rear] = x
        self.rear += 1
        self.no += 1
        if self.rear == self.capacity: # ring 모양의 자료구조이기 때문에
            self.rear = 0
            
    
    def deque(self):
        if self.is_empty:
            raise FixedQueue.Empty
        x = self.que[self.front]
        self.front += 1
        self.no -= 1
        if self.front == self.capacity:
            self.front = 0
        return x
    
    def peek(self):
        '''큐에서 데이터를 피크(맨 앞 데이터를 들여다 봄)'''
        if self.is_empty:
            raise FixedQueue.Empty
        return self.que[self.front]
    
    def find(self, value):
        '''큐에서 value를 찾아 인덱스 반환 (없으면 -1 반환)'''
        for i in range(len(self.capacity)): # 큐를 선형 검색
            idx = (i + self.front) # % self.capacity
            if self.que[idx] == value:
                return idx
            else:
                return -1
            
    def count(self, value):
        c = 0
        for i in range(self.no):
            idx = (i + self.front) % self.capacity
            if self.que[idx] == value:
                c += 1
        return c
    
    def __contains__(self, value):
        return self.count(value)
    
    def clear(self):
        self.no = self.front = self.rear = 0
        
    def dump(self):
        '''모든 데이터를 맨 앞부터 끝 순으로 출력'''
        if self.is_empty:
            print('큐가 비었습니다.')
        else:
            for i in range(self.no):
                print(self.que[(i + self.front) % self.capacity], end='')
            print()

from enum import Enum
from fixed_queue import FixedQueue

Menu = Enum('Menu', ['enque', 'deque', 'peek', 'search', 'dump', 'off'])

def select_menu():
    '''메뉴 선택'''
    s = [f'({m.value}){m.name}' for m in Menu]
    while True:
        print(*s, sep=' ', end='')
        n = int(input(': '))
        if 1 <= n <= len(Menu):
            return Menu(n)
        
q = FixedQueue(64)

while True:
    print(f'현재 데이터 개수 :  {len(q)} / {q.capacity}')
    menu = select_menu()
    
    if menu == Menu.enque:
        x = int(input('데이터를 입력하세요 : '))
        try:
            q.enque(x)
        except FixedQueue.Full:
            print('큐가 가득 차 있습니다.')
        
    elif menu == Menu.deque:
        try:
            x = q.deque()
            print(f'deque한 데이터는 {x}입니다.')
        except FixedQueue.Empty:
            print('큐가 비어 있습니다.')
            
    elif menu == Menu.peek:
        try:
            x = q.peek()
            print(f'피크한 데이터는 {x}입니다.')
        except FixedQueue.Empty:
            print('큐가 비어 있습니다.')
            
    elif menu == Menu.search:
        x = int(input('검색할 값을 입력하세요 : '))
        if x in q:
            print(f'{q.count(x)}개 포함되고, 맨 앞의 위치는 {q.find(x)}입니다.')
        else:
            print('검색값을 찾을 수 없습니다.')
            
    elif menu == Menu.dump:
        q.dump()
        
    else:
        break

우선순위 큐

인큐할 때는 데이터에 우선순위를 부여하여 추가하고, 디큐할 때 우선순위가 가장 높은 데이터를 꺼내는 방식이다. 파이썬에서 우선순위를 부여하는 큐는 heapq 모듈에서 제공한다. heap에서 data의 인큐는 heapq.heappush(heap, data)로 수행하고, 디큐는 heapq.heappop(heap)으로 수행한다.

Stack

스택은 데이터를 임시 저장할 때 사용하는 자료구조로, 데이터의 입력과 출력 순서는 후입선출LIFO 방식이다.

스택에 데이터를 넣는 작업은 push, 꺼내는 작업은 pop이라고 한다. 겹쳐 쌓은 접시처럼 데이터를 넣고 꺼내는 작업을 맨 위부터 수행한다. push하고 pop하는 윗부분을 top이라 하고, 아랫부분을 bottom이라고 한다.

크기가 결정된 고정 길이 스택 구현

<code>

# -- fixed_stack.py
class FixedStack:
    '''고정 길이 스택'''
    
    class Empty(Exception):
        '''비어 있는 FixedStack에 팝 또는 피크할 때 내보내는 예외 처리'''
        pass
    
    class Full(Exception):
        '''가득 찬 FixedStack에 푸시할 때 내보내는 예외 처리'''
        pass
    
    def __init__(self, capacity: int = 256):
        self.stk = [None] * capacity
        self.capacity = capacity 
        self.ptr = 0
        
    def __len__(self):
        return self.ptr
    
    def is_empty(self):
        '''스택이 비어있는지 판단'''
        return self.ptr <= 0
    
    def is_full(self):
        '''스택이 가득 차있는지 판단'''
        return self.ptr >= self.capacity
    
    def push(self, value):
        if self.is_full():
            raise FixedStack.Full #스택이 가득 차 있는 경우 예외 처리 발생
        self.stk[self.ptr] = value
        self.ptr += 1
        
    def pop(self):
        if self.is_empty():
            raise FixedStack.Empty
        self.ptr -= 1
        return self.stk[self.ptr]
    
    def peek(self):
        '''스택에서 데이터를 피크(꼭대기 데이터를 들여다봄)'''
        if self.is_empty():
            raise FixedStack.Empty
        return self.stk[self.ptr]
    
    def clear(self):
        '''스택의 데이터 모두 삭제'''
        self.ptr = 0
        
    def find(self, value):
        '''스택에서 value를 찾아 인덱스 반환 (없으면 -1 반환) '''
        for i in range(self.ptr - 1, -1, -1):    # 꼭대기 쪽부터 선형 검색
            if self.stk[i] == value:
                return i    # 검색 성공
        return -1    # 검색 실패
    
    def count(self, value):
        '''스택에 있는 value의 개수 반환'''
        c = 0
        for i in range(self.ptr):
            if self.stk[i] == value:
                c += 1
        return c 

    def __contains__(self, value):
        '''스택에 value가 있는지 판단'''
        return self.count(value)
    
    def dump(self):
        '''덤프(스택 안의 모든 데이터를 바닥부터 꼭대기 순으로 출력)'''
        if self.is_empty():
            print('스택이 비어 있습니다.')
        else:
            print(self.stk[:self.ptr])

from enum import Enum
from os import sep
from itsdangerous import exc

from sqlalchemy import true
from fixed_stack import FixedStack

Menu = Enum('Menu', ['push', 'pop', 'peek', 'search', 'dump', 'off'])

def select_menu():
    '''메뉴 선택'''
    s = [f'({m.value}){m.name}' for m in Menu]
    while True:
        print(*s, sep=' ', end='')
        n = int(input(': '))
        if 1 <= n <= len(Menu):
            return Menu(n)
        
s = FixedStack(64)

while True:
    print(f'현재 데이터 개수 :  {len(s)} / {s.capacity}')
    menu = select_menu()
    
    if menu == Menu.push:
        x = int(input('데이터를 입력하세요 : '))
        try:
            s.push(x)
        except FixedStack.Full:
            print('스택이 가득 차 있습니다.')
        
    elif menu == Menu.pop:
        try:
            x = s.pop()
            print(f'pop한 데이터는 {x}입니다.')
        except FixedStack.Empty:
            print('스택이 비어 있습니다.')
            
    elif menu == Menu.peek:
        try:
            x = s.peek()
            print(f'피크한 데이터는 {x}입니다.')
        except FixedStack.Empty:
            print('스택이 비어 있습니다.')
            
    elif menu == Menu.search:
        x = int(input('검색할 값을 입력하세요 : '))
        if x in s:
            print(f'{s.count(x)}개 포함되고, 맨 앞의 위치는 {s.find(x)}입니다.')
        else:
            print('검색값을 찾을 수 없습니다.')
            
    elif menu == Menu.dump:
        s.dump()
        
    else:
        break

deque를 사용한 Stack

큐(queue)는 선입선출(FIFO) 방식이며, 데큐(deque)는 양방향 큐 방식이다. 즉, 앞, 뒤 양쪽 방향에서 element를 추가하거나 제거할 수 있다.

container의 양끝 element에 접근하여 삽입 또는 제거를 할 경우, 일반적인 리스트의 연산에서는 O(n)이 소요되는 데 반해, 데크는 O(1)로 접근 가능하다.

<code>

from collections import deque

from itsdangerous import exc

class Stack:
    
    def __init__(self, maxlen):
        self.capacity = maxlen
        self.__stk = deque([], maxlen)
        
    def __len__(self):
        '''스택에 쌓여 있는 데이터 개수 반환'''
        return len(self.__stk)
    
    def is_empty(self):
        '''스택이 비어 있는지 판단'''
        return not self.__stk
    
    def is_full(self):
        '''스택이 가득 차 있는지 판단'''
        return len(self.__stk) == self.__stk.maxlen
    
    def push(self, value):
        self.__stk.append(value)
        
    def pop(self):
        return self.__stk.pop()
    
    def peek(self):
        return self.__stk[-1]
    
    def clear(self):
        self.__stk.clear()
        
    def find(self, value):
        try:
            return self.__stk.index(value)
        except ValueError:
            return -1
        
    def count(self, value):
        return self.__stk.count(value)
    
    def __contains__(self, value):
        return self.count(value)
    
    def dump(self):
        print(list(self.__stk))

'Algorithm' 카테고리의 다른 글

버블 정렬 (0)	2022.01.29
재귀 알고리즘 분석 (0)	2022.01.28
검색 알고리즘 - 해시법 (0)	2022.01.20
검색 알고리즘 - 이진검색 (0)	2022.01.20
검색 알고리즘 - 선형 검색 (0)	2022.01.20

ABOUT ME

Alex-Moon Alex-Moon

Queue

링 버퍼로 큐 구현

우선순위 큐

Stack

크기가 결정된 고정 길이 스택 구현

deque를 사용한 Stack

'Algorithm' 카테고리의 다른 글

티스토리툴바

ABOUT ME

Queue

링 버퍼로 큐 구현

우선순위 큐

Stack

크기가 결정된 고정 길이 스택 구현

deque를 사용한 Stack

'Algorithm' 카테고리의 다른 글

관련글 관련글 더보기

티스토리툴바