컴공과고씨

들어가기 앞서 Linked Queue 구현을 위한 더 쉬운 이해를 위해 스택에 관한 앞 글인 https://hagisilecoding.tistory.com/141 를 보고 오시는게 좋습니다. 큐는 스택과 반대입니다. 스택은 들어간 것이 먼저 나중에 나오지만 큐는 먼저 들어간 것이 먼저 빠져 나온다고 생각하면 됩니다. 그렇기에 구현 할 때도 조금 더 생각을 해주어야 합니다. 스택은 top 변수로 늘려주고 빼주고 하면 되지만 큐 같은 경우는 변수를 두 개 두고 앞쪽 dequeue할 변수 한 개 enqueue할 변수 한 개 총 두개를 컨트롤 해주어야합니다. 문제는 이렇게 하면 Dequeue를 했을 때 낭비되는 칸이 생기게 됩니다. 이런식으로 그래서 %연산을 이용해서 circular(순환) 하도록 만들어 주는 ..

https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 이 문제를 보고 처음에는 당연히 queue를 떠올리기 어려울 수 있지만 한 번 직접 괄호 지우다 보면 queue가 떠올라야한다. 이런식으로 앞에 나온 ( 가 있다면 ) 나왔을 때 (을 지워주는 형식으로 할 것이다. 그런데 만약 남아있는 ( 있거나 ( 가 나오지 않았는데 ) 나온다면 그것도 잘못된 괄호이다. 그래서 큐를 이용하는 것이다. 먼저 ( 일 경우 큐에 push..