파이썬 알고리즘 - 스택(Stack)으로 큐(Queue)를 구현하기

개발자 면접 트레이딩 - 파이썬 알고리즘 문제(13)

 

(1). 개발자 면접 트레이닝 - 스택(Stack)을 Set(리스트)으로 구현하기

① 큐(Queue : 선입선출) 구조 이해하는 것이 중요

② Enqueue, Dequeue 개념 파악 후 아래 코드 실습

③ 스택 공간에 데이터가 가득 찰 경우 스택 자체를 리스트로 구성

④ 예를들어 스택 사이즈가 3, 2, 1 순서로 Enqueue 후 Dequeue 결과는 1, 2, 3 순서로 출력

 

 

(2). 소스 코드

PYTHON

#two_stack_make_queue.py
import unittest

class Stack:
    def __init__(self):
        self.items = []
        self.max = 3

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def print_stack(self):
        print(self.items)

    def peek(self):
        return self.items[len(self.items) - 1]

    def is_empty(self):
        return self.items == []

    def size(self):
        return len(self.items)

class myQueue:
    def __init__(self):
        self.st1 = Stack()
        self.st2 = Stack()

    def enqueue(self, item):
        self.st1.push(item)

    def dequeue(self):
        if self.st2.is_empty():
            while self.st1.is_empty() is False:
                self.st2.push(self.st1.pop())

        return self.st2.pop()

class test(unittest.TestCase):
    def test(self):
        myq = myQueue()
        myq.enqueue(1)
        myq.enqueue(2)
        #FIFO(선입선출) 확인 가능
        self.assertEqual(1, myq.dequeue())
        myq.enqueue(3)
        self.assertEqual(2, myq.dequeue())

unittest.main()

 

(3). 소스 코드 분석

① 7 라인 : 스택 클래스(Class) 선언

② 26 라인 : 스택이 비어있는지 확인하는 is_empty 메소드 선언

③ 33 라인 : 큐(Queue) 클래스(Class) 선언

④ 39 라인 : 스택을 이용해서 큐에 데이터를 삽입하는 enqueue 메소드 선언

⑤ 43 라인 : 2개의 스택을 이용해서 큐에서 데이터를 추출하는 dequeue 메소드 선언

⑥ 51 ~ 끝 : 스택에 데이터 삽입 후 assertEqula 단위 테스트 함수를 사용하여 큐(queue)의 FIFO 확인 및 데이터 비교

 

자료구조의 Queue(큐) 는 정말 중요한 개념이며, 응용 분야는 관련 검색을 통해 자세히 알아보자.

현재 예제는 2개의 스택(Stack)으로 큐(Queue)를 구성해보았다.

(4). 실행결과1 - 단위테스트 정상 출력(큐(Queue)의 선입선출(FIFO) 확인 성공)

 

 

(5). 실행결과2 - 단위테스트 에러 출력(큐(Queue)의 선입선출(FIFO) 확인 실패)