[자료구조] 스택 큐

스택(Stack)과 큐(Queue)

---

👩🏻‍💻 발표자 : 임서인

스택 (Stack) 이란?

---

스택은 사전적으로 쌓다, 더미라는 뜻을 가지고 있으며, 접시 스택처럼 쌓아놓은 구조를 의미한다.

아래 그림과 같이 스택은 마지막에 저장한 데이터를 가장 먼저 꺼내게 되는 구조 특징이 있는데,
이러한 자료의 구조를 LIFO(Last In First Out/후입선출) 구조라고 말한다.
구조의 top을 통해서만 데이터의 삽입, 삭제가 일어난다.

 

 

스택의 활용 예시

스택은 서로 관계가 있는 여러 작업을 연달아 수행하면서 이전의 작업 내용을 저장해 둘 필요가 있을 때 널리 사용된다.

 

실행 취소 (CTRL+Z)

가장 마지막에 실행된 것부터 실행을 취소한다.

웹 브라우저 방문기록 (뒤로 가기)

가장 마지막에 열린 페이지부터 다시 보여준다.

역순 문자열 만들기

가장 마지막에 입력된 문자부터 출력한다.

수식의 괄호 검사

연산자 우선순위 표현을 위한 괄호 검사

스택의 연산

push(item): item을 스택의 맨 위(top)에 추가한다.

pop(): 스택의 맨 위 항목을 제거하고 반환한다.

peek(): 스택의 맨 위 항목을 제거하지 않고 반환한다.

큐 (Queue) 란?

큐는 사전적으로 "줄을 서다", "대기줄"이라는 의미를 가지고 있으며, 입구와 출구가 모두 뚫려 있는 터널과 같은 형태이다.

사람이 줄을 서서 기다린다는 것처럼 먼저 들어온 데이터가 먼저 나가는 형태의 구조로 FIFO(First In First Out/선입선출)방식을 가지고 있다.

 

큐의 특징

큐는 삽입, 삭제가 다른 방향에서 이루어진다.

삭제 연산만 수행되는 곳을 프론트front, 삽입 연산만 수행되는 곳을 리어rear라고 한다.

프론트front에서 이루어지는 삭제 연산을 디큐deQueue라고 하며,

리어rear에서 이루어지는 삽입 연산을 인큐enQueue 라고 한다.

front 와 rear가 같아지면 큐가 비어있다고 간주한다.

enQueue : 큐에 요소를 추가한다. rear + 1을 하고 그 자리에 요소를 추가한다.

deQueue : 큐에서 맨 앞의 요소를 빼낸다. front + 1을 하고 그 자리에 있던 요소를 출력한다.

큐의 활용예시

큐는 주로, 데이터가 입력된 순서에 따라 처리되어야 할 때 사용된다.

일상생활에서, 줄을 서서 기다려야하는 모든 행동

은행 업무

콜센터 고객 대기시간

놀이동산

캐시(Cache) 구현

새 항목을 뒤에 넣고(rear), 용량을 넘으면 앞(front)에서 먼저 들어온 항목을 제거한다.

우선순위가 같은 작업 예약 (인쇄 대기열)

 

큐의 연산

add(item): item을 리스트의 끝부분(뒤, rear)에 추가한다.

remove(): 리스트의 첫 번째 항목(앞, front)을 제거하고 반환한다.

peek(): 큐의 맨 앞(front)에 있는 항목을 제거하지 않고 반환한다.

 

---

선형큐(Linear Queue)와 원형큐(Circular Queue)

일반적으로 생각하는 큐의 형태를 선형 큐 (Linear Queue)라고 부르며 선형 큐에는 단점이 존재한다.

 

큐에 데이터가 꽉 찼다면 데이터를 더 추가할 수 없다.

선형 큐에서 삽입 및 삭제를 반복하다 보면, rear가 맨 마지막 인덱스를 가리키고, 앞에는 비어 있을 수 있지만 이를 꽉 찼다고 인식한다.

선형큐는 포화상태를 확인하기 위해 rear의 위치가 마지막인지를 검사하기 때문에 

삽입 연산을 수행하면 배열의 앞자리가 비었음에도 포화상태로 인식하고 삽입연산을 수행하지 않는다.  

만일 다시 큐의 빈자리를 사용하려면 저장되어 있는 원소를 배열의 앞부분으로 이동시켜서 위치를 조정해주어야 한다.  

하지만 이동 작업 연산은 오버헤드를 수반하여 큐의 효율을 떨어뜨린다.

 

dequeue할 때마다 front가 뒤로 넘어가서 메모리 낭비가 심해짐(노란색 부분이 버려지는 부분)

그래서 처음과 끝이 원형처럼 이어져 있다고 가정하는 원형큐(Circular Queue)가 생겼다.

 

선형큐의 문제점을 해결하기 위해 고안된 것이 원형큐이다.

원형큐는 배열을 선형이 아닌 처음과 끝이 연결된 원형으로 생각하면 된다.

즉, front와 rear의 값이 배열의 끝 부분인 (MAX_QUEUE_SIZE - 1)에 도달하고 다시 증가하면 0이 된다.

원형큐는 공백 상태와 포화 상태를 구분하기 위해 하나의 자리를 항상 비워두어야 한다.

 

front와 rear의 값이 같으면 공백 상태이고, front가 rear보다 하나 앞에 있으면 포화 상태이다.

front는 첫 번째 데이터의 앞을 가리켜야하므로

공간 하나는 비어있는 채로 유지된다.

front == rear 일 경우는 큐가 비어있을 때 뿐이다.

공간 하나를 포기하더라도 원형 큐를 쓰는 게 효율적이다!

---

+

스택오버플로우(Stack Overflow)?

개발을 하다가 모르는 점이 생기면, Q & A 형식으로 개발자들 사이에서 활발하게 열려진 토론장의 이름이 스택오버플로우이다.

그러면 이 스택오버플로우의 진짜 의미는 무엇일까?

스택오버플로우는 Stack 영역의 메모리가 지정된 범위를 넘어갈 때 발생한다. 

Stack 메모리는 보통 지역 변수가 저장되는 영역이다.

함수에서 지역 변수를 선언하면 지역 변수는 Stack 메모리에 할당되고 함수를 빠져 나오면 Stack 메모리에서 해제된다.

하나의 프로그램이 실행 될 때 수많은 함수를 호출하고 빠져 나오게 되는데,

그 때마다 함수에서 사용하는 지역 변수는 Stack 영역에 할당되고 해제되는 것을 반복하게 되며 그에 따라 사용되는 Stack 영역도 변하

게 된다.
 

만약 한 함수에서 너무 큰 지역 변수를 선언하거나 함수를 재귀적으로 무한정 호출하게 되면 Stack Overflow가 발생할 수 있다.
 

Stack Overflow가 발생하면 컴파일러 옵션에서 Stack 영역의 크기를 늘리거나 또는 함수에서 사용하는 지역 변수의 크기를 줄이거나 아니면 지역 변수를 전역 변수로 바꾸어 해결할 수 있다.

 

스택과 큐의 장점을 합친 덱(Deque;Doubly-ended Queue)

한쪽에서만 삽입, 다른 한쪽에서만 삭제가 가능했던 큐와 달리 양쪽 front, rear 에서 삽입 삭제가 모두 가능한 큐를 의미하는 자료구조이다.

연속적인 메모리를 기반으로 하는 시퀀스 컨테이너 이고 선언 이후 크기를 줄이거나 늘릴 수 있는 가변적 크기를 갖는다.(단점 1 해결)

또한 중간에 데이터가 삽입될 때 다른 요소들을 앞, 뒤로 밀 수 있다.

양쪽 끝에서 추가, 삭제가 가능한 선형 구조 형태의 자료구조