넘치게 채우기

스택은 LIFO, 큐는 FIFO 자료구조이다. 어떻게 하면 두 개의 스택으로 하나의 큐를 구현하는데, 대부분의 경우에서 O(1)으로 구현할 수 있을까? 하나를 입력용 스택, 하나를 출력용 스택이라고 해보자. 입력용 스택은 입력만 받는다. 출력용 스택은 출력만 한다. 단, 출력용 스택이 empty인 경우, 입력용 스택의 원소들을 pop하여 출력용 스택에 push하면 된다. 이때 출력용 스택에는 입력의 역순으로 들어오게 되어 기존의 출력 순서가 반대로 되어 FIFO가 된다. 이 경우만 제외하고는, O(1)의 시간복잡도를 가진다. class MyQueue { stack i,o; public: MyQueue() { } void push(int x) { i.push(x); } int pop() { int x; i..

https://leetcode.com/problems/implement-queue-using-stacks/description/?envType=daily-question&envId=2024-01-29 LeetCode - The World's Leading Online Programming Learning Platform Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com LeetCode - Implement Queue using Stacks 문제 유형 : 스택/큐 문제 난이도 : E..