스택 두개로 큐 구현하기

스택 2개로 큐를 구현하기

스택 2개로 큐를 구현하다구? 뭔 개소리야... 라고 생각한다면.. 이 문제를 처음접했었던 저의 반응과 같아요  ^~^ 아래를 참고합시다.

http://creatordev.tistory.com/83

http://www.geeksforgeeks.org/queue-using-stacks/

즉 큐를 구현하고싶은데 스택두개를 쓴다는 거구요, 스택 한개는 큐에 푸쉬 전용으로 (enqueue) 다른 스택은 dequeue 전용으로 쓴다는 겁니다.

1 개요

아래는 구조체와 메인함수, 구현 내용입니다.

2 queue init

3 enqueue 

enqueue 는 기본적으로 stack 푸쉬해줍니다. 저는 s1에 푸쉬를 해주었습니다.

4 dequeue

dequeue는 기본적으로 stack에서 팝하는것입니다. 저는 s2에서 팝합니다. 단 dequeue 가 처음 수행될 때는 s2는 반드시 top이 0이기때문에 s1에서 팝해온뒤 s2로 푸쉬하는 동작이 필요합니다. 그 외의 경우에는 s2에서 팝해서 리턴값으로 받습니다. 

수고하셨습니다. 굉장히 쉬웠습니다만, 스택으로 큐를 구현한다는 문제가 있다는 것을 모른다면 당황하고 이해 못해서 못푸는 문제일 수 있겠습니다. 절대 제가 당시에 못 풀어서 이런 당부드리는건 아닙니다 ㅡ.ㅡ..... 뻘쭘

전체코드보기

https://github.com/ingyeoking13/algorithm/blob/master/swtest/sk/p5.c