[ Data Structure ] - Stack & Queue

스택과 큐를 들어가기에 앞서, 자료구조에 대해 알아야 한다.

자료구조

자료구조의 정의는 인터넷에 널리고 널렸다.

내가 생각하는 자료구조는, "섹시하게 데이터를 다루는 방법"이다.

그 방법중에 스택과 큐가 존재하는 것이다.

자료구조는 서비스나 어플리케이션에서 필요한 데이터를 메모리에 어떻게 구조적으로 잘 정리해서 담아주고 관리하고, 최종적으로 가장 효율적인 방식으로 필요한 데이터에
빠르게 접근하고 추가, 수정, 삭제할 수 있도록 도와준다.

Stack(스택)과 Queue(큐)는 ADT 라고도 불린다.

ADT

• ADT(Abstract Data Type), 추상적 자료구조.

ADT는 자료구조의 한 형태인데, 자료구조의 방법이 코드로 정의 된 것이 아니라 그 구조의 행동 양식만 정의된 것을 뜻 한다.

실제로 존재하지 않지만, 규칙을 제공한다.
덕분에 자료를 좀 더 구조적으로 생각할 수 있다.

스택과 큐가 그러하다.

큐와 스택은 배열 위에 어떤 규칙을 설정한 모습이다.

Queue

큐의 사전적 의미는 줄 또는 줄을 서서 기다리를 것을 의미한다고 한다.

따라서 일상생활에서 놀이동산에서 줄을 서서 기다리는 것, 은행에서 먼저 온 사람의 업무를 창구에서 처리하는 것과 같이 선입선출인 FIFO(First In, First Out)방식이다.

큐는 한쪽 끝에서 추가가, 다른 쪽 끝에서는 삭제가 발생한다.

Queue - Front

삭제 연산이 수행되는 곳을 프론트(Front)라고 한다.
이때, Front에서 수행되는 삭제 연산을 디큐(dnQueue)라고 한다.

Queue - Rear

삽입 연산이 수행되는 곳을 리어(Rear)라고 한다.
이때, Rear에서 수행되는 삽입 연산을 인큐(enQueue)라고 한다.

큐의 데이터들은 Rear로 들어와 Front로 나가고,
Front에 있는 데이터는 가장 먼저 들어온 데이터고,
Rear에 있는 데이터는 가장 늦게 들어온 데이터이다.

Queue - Ex)

1. 프로세스 관리
2. BFS(너비 우선 탐색) 구현
3. 은행 업무

Stack

스택은 쌓아 올린다 라는 의미를 가지고 있다.

책을 쌓는 것처럼 쌓아올리는 형태의 자료구조이다.
따라서 위 사진처럼, 정해진 한 방향으로만 쌓을 수 있고
그 곳을 통해서만 데이터에 접근이 가능하다.

Stack - Top

큐는 들어오고 나가는 방향이 다르지만,
스택은 한 방향에서 들어오고 나간다.

이를 Top이라 한다.

방향이 하나라,
가장 먼저 들어온 데이터는 맨 마지막에 나가게 되고,
가장 늦게 들어온 데이터가 가장 먼저 나가게 된다.

따라서 후입선출인 LIFO(Last In, First Out)방식을 따른다.

Stack - Ex)

1. 웹 브라우저 방문기록(뒤로가기)
2. 실행 취소(Undo)