[PS일지]큐, 스택, 덱

"코딩 초보 페놀"의 PS일지

 

종만북 2권에서 큐와 스택 덱을 배웠다.

셋 다 간단한 자료구조지만 그만큼 쓸모가 많다고 생각이 들었다.

 

스택은 후입선출로, 나중에 들어간게 먼저 나오는 자료구조이다.

간단하게 생각해보자

 

1부터 5까지의 숫자공을 바닥이 열리지 않는 상자에 넣어보자

바닥-1-2-3-4-5

뺄때는 5부터 빼내야한다

이것이 바로 스택의 후입선출이다

 

빼는 연산을 POP이라한다. 

상자에 공을 넣는 연산을 PUSH라한다.

사실, C에는 없지만 (C++만세)

C++에는 stack 헤더파일을 제공한다.

 

자세한 내용은 STL stack으로 구글링하면 많은 설명이 있다.

 

 

그럼 대체 이 stack을 어디에 이용하는가?

바로 괄호이다.

"("은 ")"와 짝을 맺어야한다.

(((((((((() 이라는 괄호식이 있다면 괄호가 맺어져있는 것은 저 빨간색 부분이라고 많은 사람들이 말할 것이다.

그렇다면 )을 하나 더 추가해보자 (((((((((()) 따라서 이것은 괄호기호 ")"가 추가 될 때마다 가장 오른쪽에 있는 "("과 짝을 맺는 것을 볼 수 있다.

 

잠깐, 어디서 많이 보지않았는가? 이것은 스택의 후입선출과 닮아있다.

()()( 이 잘못된 괄호인지 판단하는 과정을 스택으로 표현해보자 

index = 0, "("을 스택에 넣는다.(push)

index = 1, "("을 스택에서 제거한다.(pop)

index = 2, "("을 스택에 넣는다. (push)

index = 3, "("을 스택에서 제거한다. (pop)

index = 4, "("을 스택에서 제거한다??

그렇다 없는 스택에서 괄호를 빼냈다.

없는 곳에서 있는걸 빼낸다니, 마술사인가?

아니다.

이를 스택 언더플로우라고 한다.

 

스택 언더플로우가 나면 괄호쌍이 안맞는다는 것은 자명하다

 

하지만 오히려 스택이 남는 경우가 있다

(( 와 같은 경우이다.

이 경우에도 괄호쌍이 맞지않는다.

 

우리는 이 두 가지 사실로 하나를 알 수 있다.

 

괄호쌍이 맞기 위해선 중간에 스택 언더플로우가 나지 않으면서 마지막에 스택이 비어있어야한다.

 

이처럼 스택은 괄호쌍과 같은 일상생활의 문제를 해결할 때 도움이 될 수 있다.

 

스택을 배웠으니 큐를 배우는 것은 어렵지 않은 일이다.

큐는 선입선출로, 먼저들어온게 먼저나가는

 

 

잠깐, 어디서 많이 봤지않는가?

 

놀이동산에서는 모든 줄이 선착순이다.

먼저 선 사람이 먼저 놀이기구를 탄다.

54321 순으로 이해하면된다. 1번(먼저온사람)이 먼저 나가니까...

그렇다, 큐는 선착순이다.

큐는 줄을 세우는 문제, 순서를 지키는 문제를 해결할 때 도움이 된다.

 

큐는 C++(와 C++선생!)에서 queue헤더가 지원한다.

 

이것도 STL queue라고 치면 나오므로 적절히 구글링하도록 하자

 

queue도 stack과 마찬가지로 push와 pop연산이 있다.

 

 

 

이제 덱(deque)를 배워보자

 

근데... 갑자기 내가 선생님이 됬는데 오해하지말자(물론 이게 도움은 될 수 있겠지만은...)

나는 그냥 내가 배운 내용을 정리하기위해 나 자신에게 가르치는 것(?) 이다.

 

덱은 사기다.

그냥 사기다

스택과 큐를 합쳐놓았다.

 

숫자를 뒤에서 뺄 수도있고 앞에서 뺄 수도 있고

추가도 자유자재이다.

오!

 

Q. 그럼 구현하기 어렵지않나요?

A. 구현하긴 어렵진 않지만 구현할 필요는 없을겁니다. 우리의 선생 C++은 deque헤더를 지원합니다!

 

덱은 여러모로 쓸데가 많으므로 개인적으로 배우길 추천한다.

 

 

자료구조가 중요하다는 것을 새삼느꼈다.

사실 컴퓨터 자체가 자료저장이 되게 중요하다.

 

이제 하나하나 기억하고 익히는 습관을 길러야겠다.