스택으로 큐, 큐로 스택 메모

https://bellog.tistory.com/143 

[리트코드(LeetCode)] 큐로 스택 구현하기, 스택으로 큐 구현하기 - Python

자주 받는 질문인데, 자주까먹어서 찾아본 자료.

 

 

 

1. 스택으로 큐를 구현할때

- 스택 두개를 준비한다

- 큐의 성질은 뺄때 먼저 넣은게 먼저 나온다는 것(FIFO)

- 스택a에는 일단 밀어 넣고, 스택 b는 꺼낼때 이용한다. 

- 스택 b에서 원소를 꺼낼때 비어있으면 a가 빌때까지 원소를 모두 b로 옮긴다. 이때 스택이기때문에 옮겨지면 b스택 가장 위에는 a스택에 가장 먼저 들어갔던것이 있게 된다. 

- b가 빌때까지 계속 b에서 deque때 원소를 빼간다. 

 

2. 큐로 스택을 구현

- 이건 방법이 여러개가 있는 것 같은데, 내가 이해한 방법은 아래와 같다. 

- 일단 큐를 하나 준비한다. 

- 스택의 성질은 나중에 넣은게 먼저 나오도록 해줘야한다(LIFO)

- 큐에 일단 밀어 넣되, 넣기전에 있었던 갯수만큼 큐에서 꺼낸다음 현재 넣은것 뒤로 순서대로 넣어준다. (원소를 넣기 전에 큐의 길이가 len이었다면 len번 큐에서 deque를 하고 enque를 해준다)

- 큐에서 꺼낼때는 앞에 있는게 가장 마지막에 넣었던 것이 된다.