[파이썬 알고리즘]큐를 이용한 스택 구현

문제:

- push(x) : 요소 x를 큐 마지막에삽입한다.

- pop() : 스택 처음에 있는 요소를 삭제한다.

- top() : 스택 처음에 있는 요소를 가져온다.

- empty() : 스택이 비어 있는지 여부를 리턴한다.

 

MyQueue queue = new MyQueue();

 

queue.push(1);

queue.push(2);

queue.push();  // 1리턴

queue.pop();  // 1리턴

queue.empty(0; // false 리턴

 

- 큐를 이용해서 스택을 만들어라

 

 

1) 생각한 것

- 큐랑 스택의 가장 큰 차이점을 생각해보면 push할 때 스택은 FIFO이고, 큐는 LIFO니까 이 부분을 수정하면 되겠구나.

- 값을 push 할때 큐의 값을 역순으로 출력하게 하면 되겠다.

 

2) 알아낸 것

- deque를 쓰면 앞에서도 뺄 수있고, 뒤에서도 뺄 수 있으니 큐 사용할때 좋을 것 같다.

from nltk import collections


class Mystack:
    def __int__(self):
        self.q = collections.deque()

    def push(self, x):
        self.q.append(x)
        # x 값을 추가해주고 스택은 FIFO니까 들어간 값이 맨 뒤에 가도록 정렬
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())


def pop(self):
    return self.q.popleft()


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


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