queuestack

• Prob
• Solv
• Check
• Feedback
• Ref

queuestack

Prob

Solv

stack은 연산에 영향을 미치지 않는다.
queue의 중간 부분도 약분되듯이 연산이 필요없다.
따라서 queue의 작동방식과 동일하게 입력과 출력만 연산한다.

queue	deque	stack
in-> = ->out	in,out <-> = <-> in,out	in, out <-> =
front, back	front, back	top
push	push_front, push_back	push
pop	pop_front, pop_back	pop

Check

1. queue
   x0인 2가 push하고 먼저 있던 1이 pop한다.
   pop한 1은 x1가 된다.
   결국 x인 1과 queuestack의 2가 자리를 바꾼 것과 동일하다.
2. stack
   x1인 1이 push되고 마지막에 들어온 1이 다시 나온다.
   따라서 x는 그대로 1로 유지되고 변화가 없다.

최종적으로 stack 부분은 연산할 필요가 없다.
입력이 1 2 3 4순으로 1부터 들어오니 양방향 입출력이 가능한 deque을 사용한다.

in	dq	x
	[1 4]
2	[2 1]	4
4	[4 2]	1
7	[7 4]	2

Feedback

Ref