두 개의 Stack으로 Queue 자료구조를 구현해봅시다

'두 개의 Stack으로 Queue 자료구조를 구현해주세요' 라는 질문 어디서 많이 보지 않았나요?

그래서 직접 해보았습니다

 

사실 처음의 아이디어는 이것이엇습니다 👇

 

Enqueue 연산: 스택을 두 개로 나누어서 Enqueue 시 Stack 1에 Push한다

👉 일반 스택의 Push연산과 동일하므로 Time Complexity: O(1)

Dequeue 연산:

1️⃣ Stack 1의 모든 Element들을 Stack 2로 이동한다 (하나씩 Pop하면서, Pop된 Value를 동시에 Stack 2로 Push한다). - O(N)

2️⃣ Stack 2의 top을 Pop한다. - O(1)

3️⃣ Stack 2의 element들을 다시 1번처럼 Stack 1로 되돌린다. - O(N)

👉 Time Complexity: O(N) + O(1) + O(N) = O(N)

 

하지만 Stack 2가 너무 임시방편으용으로만 사용된다는 문제점이 있었고, 굳이 Stack 1로 다시 옮겨줘야 하나?라는 의문이 생겼습니다

 

Stack 1은 Enqueue 전용으로, Stack 2는 Dequeue 전용으로 분리시켜 주었습니다.

일반적으로 ADT Stack의 operation은 create, enqueue, dequeue, isEmpty, peek으로 5개가 있지만 이 글에서는 enqueue와 dequeue만 다룹니다.

 

Enqueue 연산: 스택을 두 개로 나누어서 Enqueue 시 Stack 1에 Push한다

👉 일반 스택의 Push연산과 동일하므로 Time Complexity: O(1)

 

Dequeue 연산:

1️⃣ Stack 2가 비어있을 때:

Stack 1의 모든 Element들을 Stack 2로 이동한다 (하나씩 Pop하면서, Pop된 Value를 동시에 Stack 2로 Push한다).

👉 Time Complexity: O(N)

2️⃣ Stack 2가 비어있지 않을 떄:

Stack2의 top을 Pop한다.

👉 Time Complexity: O(1)

 

로 분리해주었습니다. 

처음에 생각했던 러프한 내용과는 달리, Stack 2가 비어있지 않을 때 에는 top에 있는 element를 바로 pop해서 시간복잡도를 O(1)로 줄일 수 있다는 장점이 있습니다.

 

C++ 구현 코드

#include <cstdio>
#include <stack>
using namespace std;

void enqueue(stack<int>& s1, stack<int>& s2, int value) {
	s1.push(value);
}

int dequeue(stack<int>& s1, stack<int>& s2) {
	if (s1.empty() && s2.empty()) {
		printf("Queue is empty");
		return -1;
	}
	if (s2.empty()) {
		while (!s1.empty()) {
			s2.push(s1.top());
			s1.pop();
		}
	}

	int front = s2.top();
	s2.pop();
	return front;
}

int main() {
	stack<int> s1, s2;
	
	enqueue(s1, s2, 1);
	enqueue(s1, s2, 2);
	enqueue(s1, s2, 4);
	enqueue(s1, s2, 8);

	for (int i = 0; i < 4; i++) {
		int value = dequeue(s1, s2);
		printf("%d ", value);
	}
    // 출력: 1 2 4 8
}