스택, 큐

스택과 큐는 자료구조에서 가장 먼저 배우는, 가장 기본적인 자료구조이다.

 

알고리즘에서 많이 쓰인다는 자료구조들이 점차 배열로 해결가능해지자 자료구조를 이해하지 않고 코딩을하는

사람이 늘기 시작했다.

 

하지만 자료구조의 개념을 인지하고 활용하면 분명 코드와 개발에 도움이 될것이라 생각하기에 이 글을 작성해본다.

 

스택, 큐

 

대부분의 사람들 모두가

스택과 큐의 차이점을 말하라고 하면,

 

스택은 후입선출(LIFO), 큐는 선입선출(FIFO)라고 말한다.

 

후입선출은 가장 늦게 넣은 데이터가 가장 빨리 나가는 것.

선입선출은 가장 빨리 넣은 데이터가 가장 빨리 나간다는 뜻이다.

 

아마 이보다 더 쉽게 설명할 수 있는 글은 없는 것 같다.

 

하지만 작성자는 여기서 조금 더 설명해 보겠다.

 

1. 스택

스택은 객체들의 집합소로써, 데이터를 기록하는 구조라고 보면 된다.

아까 말한 LIFO와 함께 이 그림과 아래 예시를 본다면 이해하기 쉬울 것이다.

 

스택에서 삽입 연산은 Push, 삭제 연산은 Pop이라고 부른다.

 

가장 처음 First를 Push

그 다음으로 Middle,

그리고 Last 순으로 Push했다.

 

하지만 Pop한 순서는 Last -> Middle -> First다.

 

이것이 후입 선출(가장 늦게 들어간 데이터가 가장 빨리 나온다)이다.

 

 

 

 

만약 비어있는 스택에서 원소를 추출하려고 하면, stack underflow라는게 있고,

스택이 넘치는데서 스택을 추가하려고 하면, stack overflow라고 한다.

 

이제 스택을 어디서 사용하는지 알아보겠다.

 

당연한 이야기지만 스택은 알고리즘에 많이 활용된다.

 

작은 예로 당신이 역순 문자열을 만든다고 할때, 스택의 LIFO 성질을 이용한다면 간단하게 만들 수 있을 것이다.

 

 

가. 문자열을 처음부터 순서대로 스택에 삽입한다.

나. 그 후 스택에 있는 원소들을 공백 스택이 될 때 까지 삭제한다.

다. 삭제하며 반환된 문자를 나열하면 원래 문자열의 역순이 된다.

 

그 이외에도 

 

1. 웹 브라우저 방문 기록 (뒤로가기)
2. 실행 취소 (undo)
3. 수식의 괄호 검사
4. 후위표기법 계산

 

등에서 쓰일 수 있다.

 

 

2. 큐

 

큐는 집합에서 가장 오랜 시간 존재했던 원소를 삭제한다.

 

쉽게 설명하면 선입 선출 (FIFO)이다

 

큐에서의 삽입은 Enqueue, 삭제는 Dequeue라고 한다

스택과 해깔리지 않도록 하자.

 

스택에서는 원소의 삽입, 삭제가 스택의 한 끝에서 이루어졌다.

하지만 큐에서는 원소의 삽입, 삭제가 다른 끝에서 이루어진다.

 

가. 양방향 큐 (deque) - 덱

 

덱은 큐를 양 방향으로, 즉 삽입 삭제가 양쪽 방향에서 이루어진 것이다.

(큐와 스택을 합친 것으로 선입선출/후입선출의 복합적인 성격을 띈다.)

 

큐의 예시

 

1. 우선순위가 같은 작업 예약 (프린터 출력)

2. 대기열(커피 주문 대기열)

 

등등