스택(stack), 큐(queue)

스택(stack)

스택은 제약을 갖는 배열로, 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 LIFO 자료 구조이다.

자료를 넣는 것을 '밀어넣는다' 하여 푸쉬(push)라고 하고 반대로 넣어둔 자료를 꺼내는 것을 팝(pop)이라고 하는데, 이때 꺼내지는 자료는 가장 나중에(최근에) 푸쉬한 자료부터 나오게 된다. 나중에 넣은 값이 먼저 나오는 Last In, Frist Out(LIFO) 구조로 이루어져 있다.

 

제약을 갖는 자료 구조인 스택이 중요한 이유

1) 잠재적 버그를 막을 수 있다. 스택 위 항목을 제외하고는 삭제할 수 없으므로 배열 중간의 데이터를 삭제하는 코드를 작성하면 오류가 발생한다.

2) 문제를 해결하는 새로운 사고 모델을 제공한다. 스택은 마지막에 들어온 데이터부터 먼저 처리하는 후입 선출 방식이다. HWP 문서를 작성 할 때 '되돌리기' 함수가 스택의 좋은 활용 사례다.

 

큐(queue)

먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)의 자료 구조이다. 한쪽 끝에서만 삽입/삭제가 이루어지는 스택과 달리 큐의 rear에서는 삽입이, 큐의 front에서는 삭제가 이루어진다. 영어 단어 queue는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 연상하면 된다.

큐에 자료를 추가하는 인큐(Enqueue, En-Queue), 큐에서 자료를 꺼내는 디큐(Dequeue, De-Queue)가 있다.

• rear : 큐의 맨 뒤의 위치(인덱스), 마지막에 온 손님의 번호
• front : 큐의 맨 앞의 위치(인덱스), 다음 서비스를 받을 손님의 번호
• Peek : front에 위치한 데이터를 읽음, 다음 서비스를 받을 손님이 누구인지 확인

큐는 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 유용하다.

1) 선입선출이 필요한 티켓 대기열

2) 프린터 출력 처리: 인쇄 작업물을 Queue에 임시 저장하고 들어온 순서대로 출력