오늘은 스택(STACK)과 QUEUE(큐)의 개념에 대해 알아보자 🥁

스택(STACK)📚

개념✅

스택이란 말 그대로 쌓아 올린다는 것을 의미한다. 따라서 스택 자료구조라는 것은 책을 쌓는 것처럼 차곡차고 쌓아 올린 형태의 자료구조를 말한다.

특징✔️

• 스택은 위의 사진처럼 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있고 top으로 정한 곳을 통해서만 접근할 수 있다.

• top에는 가장 위에 있는 자료는 가장 최근에 들어온 자료를 가리키고 삽입되는 새 자료는 top이 가리키는 자료 위에 쌓이며 삭제할 대도 top을 통해서만 가능하다.

• 여기서 top을 통해 삽입되는 연산을 push , top을 통한 삭제하는 연산을 pop이라고 한다.

따라서 스택은 시간 순서에 따라 자료가 쌓여서 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다는 구조적 특징을 가지게 된다. 이러한 스택의 구조를 후입선출(LIFO, Last-In-First-Out) 구조이라고 한다.

예외처리 부분

• 단, 자료가 없을 때 Pop을 한다면 자료가 없기에 뺄수도 없다. 이때 발생하는 Err를 Stack Underflow라고 한다.
• 또한 반대로 스택의 크기, 즉 배열의 크기 이상의 자료를 Push 할 때도 자료를 넣을 수 없으므로 Stack Overflow Error가 발생한다

  개발자들의 지식인 사이트 Stack Overflow 이름도 이런 뜻을 가지고 있다.

출처: https://winplz.tistory.com/entry/자료구조스택과-큐-stack-and-queue [윈플]

활용예시🙋‍

• 웹 브라우저 방문기록 (뒤로 가기) : 가장 나중에 열린 페이지부터 다시 보여준다.
• 역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력한다.
• 실행 취소 (undo) : 가장 나중에 실행된 것부터 실행을 취소한다.
• 후위 표기법 계산
• 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)

STACK의 단점 😡

- 놀이동산이나 은행의 줄을 기다리고 있는데 스택의 방식으로 맨 마지막에 온 사람을 먼저 처리해준다면? 굉장히 화가난다.

큐(QUEUE)란

개념✅

- 사전적 의미는 (무엇을 기다리는 사람, 자동차 등의) 줄, 혹은 줄을 서서 기다리는 것을 의미 >따라서 일상생활에서 놀이동산에서 줄을 서서 기다리는 것과 같이 선입선출 방식의 자료구조를 뜻한다.

특징✔️

• 정해진 한 곳(top)을 통해서만 삽입, 삭제가 이루어지는 스택과 달리 큐는 한쪽 끝에서 삽입 작업이, 다른 쪽 끝에서 삭제 작업이 양쪽으로 이루어 진다.

• 이때 삭제연산만 수행되는 곳을 프론트(front), 삽입연산만 이루어지는 곳을 리어(rear)로 정하여 각각의 연산작업만 수행된다.

• 이때, 큐의 리어에서 이루어지는 삽입연산을 인큐(enQueue) 프론트에서 이루어지는 삭제연산을 디큐(dnQueue)라고 부른다.

즉, 큐에서 프론트 원소는 가장 먼저 큐에 들어왔던 첫 번째 원소가 되는 것이며,
리어 원소는 가장 늦게 큐에 들어온 마지막 원소가 되는 것이다.

활용예시🙋‍

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

• 우선순위가 같은 작업 예약 (프린터의 인쇄 대기열)
• 은행 업무
• 콜센터 고객 대기시간
• 프로세스 관리
• 너비 우선 탐색(BFS, Breadth-First Search) 구현
• 캐시(Cache) 구현

QUEUE의 단점 😡

• 큐의 문제점은 일반적으로 배열을[1][2][3][4][5] 이런 직선 형태로 보왔을 때,
  [Pop][2][3][4][5] 가장 오래기다린, 처음 들어온 [1]이라는 데이터가 Pop이 되면 다른 데이터들을 차례대로 땡겨주어야 한다.
  ( 소수의 자료의 경우는 상관이 없지만 많은 데이터의 경우 연산에 많은 시간이 걸린다. )

• 이런 문제를 해결하기 위해 나온 것이 원형 큐, 순환 큐 라고 불리는 방법이 있다

  

Reference

(1) 참고사이트
(2) 참고사이트