Stack 2개로 Queue 구현하기 [C++]

큐는 FIFO 성질을 가진 자료구조다. 즉 먼저 들어간 데이터가 먼저 나오게 된다. 스택 2개를 활용해서 큐를 구현할 수 있다. 스택 하나는 push 용도, 나머지 하나는 pop할 때 이용된다. 만일 pop 명령이 들어온다면 push 때 담긴 스택을 위에서부터 빼서 스택 2번에 넣을 수 있다. 그리고 스택 2에서 위에서부터 pop하면 큐와 똑같이 동작시킬 수 있다  

 

	#include <iostream>
	using namespace std;
	#define SIZE 1000
	int stack1[SIZE], stack2[SIZE];
	int top1 = -1, top2 = -1;
	void push(int data) {
	if (top1 >= SIZE - 1) return;
	stack1[++top1] = data;
	}
	int pop() {
	if (top2 == -1 && top1 != -1) {
	for (int i = top1; i >= 0; i--) {
	stack2[++top2] = stack1[i];
	}
	}
	return stack2[top2--];
	}
	int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
	int x;
	cin >> x;
	push(x);
	}
	for (int i = 0; i < n; i++) {
	cout << pop() << ' ';
	}
	cout << '\n';
	return 0;
	}

view raw queue_using_stack.cpp hosted with ❤ by GitHub