스택(Stack) & 큐(Queue)

전 글에 이어서 스택과 큐를 이용한 문제를 통해 스택과 큐를 익혀보자.

LeetCode 225.Implement Stack using Queue

큐를 이용해 다음 연산을 지원하는 스택을 구현하라.

우선 스스로 이 문제를 풀어보았다.

class MyStack:

    def __init__(self):
        self.q = collections.deque()

    def push(self, x: int) -> None:
        self.q.append(x)

    def pop(self) -> int:
        return self.q.pop()

    def top(self) -> int:
        return self.q[-1]

    def empty(self) -> bool:
        return not self.q

스택의 구조보다는 스택의 연산이 구현되도록만 생각하고 작성하였다.

Solution 1 push() 할 때 큐를 이용해 재정렬

혼자 힘으로 풀었을 때에는 스택의 연산만을 생각하고 구현했다면 이번에는 스택의 구조까지 구현해볼 차례이다. 우선 문제의 의도에 맞게 큐의 선언을 deque로 해준다. 그리고 큐의 연산만을 사용해서 구현할 것이다. 큐는 FIFO에 해당하므로 popleft()만 가능하다. 그렇다면 popleft()로 스택 기준 가장 뒤의 수를 제거하려면 스택이 거꾸로된 형태로 저장되어야 한다. 그러므로 스택의 push() 연산에는 들어온 값을 가장 앞으로 보내는 연산까지 포함되어야 한다.

self.q.append(x)
for _ in range(len(self.q)-1):
    self.q.append(self.q.popleft())

이렇게 하면 popleft()로 스택의 pop()까지 구현할 수 있게 된다.

class MyStack:

    def __init__(self):
        self.q = collections.deque()

    def push(self, x: int) -> None:
        self.q.append(x)
        for _ in range(len(self.q)-1):
            self.q.append(self.q.popleft())

    def pop(self) -> int:
        return self.q.popleft()

    def top(self) -> int:
        return self.q[0]

    def empty(self) -> bool:
        return len(self.q)==0

LeetCode 232.Implement Queue using Stacks

스택을 이용해 다음 연산을 지원하는 큐를 구현하라.

이번에도 혼자서 풀어보았다. append()를 이용해서 input스택에 넣고 바로 output스택에 pop하여 옮겨 넣는 방식으로 구현하였다. 이 부분에서 생각이 짧아 틀렸다. input스택에 넣자마자 output스택에 옮기면 결국은 하나의 스택을 쓰는 것과 같아진다. 두개의 스택을 쓴다는 것까지는 잘 접근했지만 두 스택의 값을 옮기는 과정이 잘못되었었다. 두 스택의 값을 옮기는 함수를 따로 구현하고 pop과 peek전에 호출하도록 작성하였다.

class MyQueue:

    def __init__(self):
        self.input=[]
        self.output=[]
        
    def shift(self):
        if not self.output:
            while self.input:
                self.output.append(self.input.pop())

    def push(self, x: int) -> None:
        self.input.append(x)

    def pop(self) -> int:
        self.shift()
        return self.output.pop()

    def peek(self) -> int:
        self.shift()
        return self.output[-1]

    def empty(self) -> bool:
        return not self.input and not self.output

Solution 1 스택 2개 사용

힌트를 보고 혼자 풀어본 것과 거의 비슷하다. pop을 하기 전에 peek에 input스택에서 output스택으로 옮기는 연산을 넣고 peek를 먼저 호출하여 데이터를 거꾸로 옮겨놓고 pop한다.

class MyQueue:

    def __init__(self):
        self.input=[]
        self.output=[]

    def push(self, x: int) -> None:
        self.input.append(x)

    def pop(self) -> int:
        self.peek()
        return self.output.pop()

    def peek(self) -> int:
        if not self.output:
            while self.input:
                self.output.append(self.input.pop())
        return self.output[-1]

    def empty(self) -> bool:
        return self.input==[] and self.output==[]

LeetCode 622.Design Circular Queue

원형 큐를 디자인하라.

Solution 1 배열을 이용한 풀이

원형 큐는 큐와 같이 FIFO 구조를 가지지만 front와 rear가 연결된 링 구조를 띄고 있다. 기존의 큐는 공간이 꽉 차면 더 이상 요소를 추가할 수 없었다. 심지어 deQueue()로 인해 앞공간이 남는다고 하더라도 그 공간에 요소를 추가할 방법이 없다. 그러나 원형 큐는 위의 그림처럼 앞쪽에 공간이 남아있다면 동그랗게 연결해 앞쪽에 추가할 수 있도록 재활용 가능한 구조를 띈다.

동작하는 원리는 투 포인터와 비슷하다. 시작 위치와 끝 위치가 연결된 원형 구조를 만들고, front를 가리키는 포인터 하나와 rear를 가리키는 포인터 하나가 시작점과 끝점을 따라 움직인다. enQueue()를 하면 rear가 앞으로 이동하고, deQueue()를 하면 front가 뒤로 이동한다. enQueue()와 deQueue()가 계속 반복되면 front와 rear가 빙글빙글 돌게된다. 만약 rear가 front와 같은 위치에서 서로 만났을 때는 원형 큐에 남은 공간이 하나도 없다는 이야기가 되기 때문에 공간 부족 에러를 발생시킨다.

원형 큐를 초기화 할때에는 우선 원형 큐의 크기를 같이 받는다. 그리고 원형 큐를 받은 크기만큼 할당을 한다. 입력 받은 원형 큐의 크기를 최대 크기로 저장해주고 front와 rear를 의미하는 포인터 두개를 0으로 선언한다.

enQueue()의 경우 rear가 가리키고 있는 칸이 비어있을 때에 그 칸에 입력받은 수를 넣어주고 rear를 (rear+1)%maxlen으로 갱신해준다. 이는 다음 칸으로 이동하는 것을 구현한 것인데 %를 통해서 원형으로 돌게끔 한 것이다. 만약 rear가 가리키고 있는 칸이 차있다면 False를 반환한다.

deQueue()의 경우는 enQueue()와 반대로 front가 가리키고 있는 칸이 비어있다면 False를 반환한다. front가 가리키고 있는 칸이 채워져 있다면 이 칸을 None으로 갱신하고 front를 (front+1)%maxlen으로 갱신해준다. 원래의 원형 큐의 deQueue()는 지워지는 수를 반환해야 하는데 이 문제에서는 True와 False를 반환하도록 되어 있다. 만약 원래의 원형 큐를 구현해야 한다면 front가 가리키고 있는 칸의 수를 따로 저장한 뒤에 이 칸을 None으로 비우고 따로 저장한 수를 반환하면 될 것이다.

class MyCircularQueue:

    def __init__(self, k: int):
        self.q=[None]*k
        self.maxlen=k
        self.p1=0
        self.p2=0

    def enQueue(self, value: int) -> bool:
        if self.q[self.p2] is None:
            self.q[self.p2]=value
            self.p2=(self.p2+1)%self.maxlen
            return True
        else:
            return False

    def deQueue(self) -> bool:
        if self.q[self.p1] is None:
            return False
        else:
            self.q[self.p1]=None
            self.p1=(self.p1+1)%self.maxlen
            return True

    def Front(self) -> int:
        if self.q[self.p1] is None:
            return -1
        return self.q[self.p1]

    def Rear(self) -> int:
        if self.q[self.p2-1] is None:
            return -1
        return self.q[self.p2-1]

    def isEmpty(self) -> bool:
        return self.q[self.p1] is None and self.q[self.p2] is None

    def isFull(self) -> bool:
        return self.p1==self.p2 and self.q[self.p1] is not None