#6 Stack(스택) - 개념(FILO : First In Last Out)

● Stack이란?

- Stack은 단순한 규칙을 가지고 있는 리스트이다. 여기서 규칙은 FILO(First In Last Out)이다.

- FILO(First In Last Out) : 먼저 들어간 데이터가 나중에 나오는 규칙

ex) 10명의 사람이 모두 1층에서 엘베를 탄 후 5층에서 내린다고 했을 때 가장 먼저 탄 사람이 가장 나중에 내린다.

- Stack은 먼저 들어온 게 나중에 나오는 조건만 충족한다면 어떠한 자료구조로 구현하든 상관없다.

- 배열과 연결리스트를 이용해서도 각각 Stack을 구현할 수 있다.

---

● 연결리스트를 이용해 Stack 구현

- 연결리스트의 맨 첫 번째 node를 head 라고 했을 때 이 haed를 가지고 모든 node를 연결할 수 있다.(아래 사진 참고)

출처 - 인프런, 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

- 바로 이 head를 이용하면 Stack을 구현할 수 있다.

- 어떻게? 데이터의 삽입과 삭제를 무조건 첫 번째 인덱스(= 노드)에서 하는 것이다.

 

ex1) 정수 1, 2, 3, 4 를 첫 번째 인덱스에만 삽입해서 연결리스트 만들기

- 1을 삽입하면 리스트에는 1을 담은 node 하나만 존재

출처 - 인프런, 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

- 2를 삽입할 때 리스트의 가장 앞 부분(= head)에 삽입

- 그로인해 당연히 2를 담은 노드가 1을 담은 노드보다 앞에 위치

출처 - 인프런, 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

- 마찬가지로 3과 4를 차례대로 가장 앞 부분에 삽입, 그렇게 되면 4를 담은 node가 가장 앞에 위치한다.

출처 - 인프런, 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

출처 - 인프런, 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

 

ex2) 위에서 만든 연결리스트의 node 삭제

- 제거 또한 리스트의 가장 앞 부분(head에 있는 node)을 제거한다.

- 가장 앞 부분인 4를 제거

출처 - 인프런, 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

- 가장 앞 부분인 3을 제거

출처 - 인프런, 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

- 가장 앞 부분인 2를 제거

출처 - 인프런, 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

- 마지막으로 1을 제거

출처 - 인프런, 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

---

● 정리

- 위와 같이 한쪽으로만 데이터를 삽입 및 제거하는 방법으로 Stack을 구현할 수 있다.

- Stack 같은 자료구조는 아래와 같은 경우에 필요하다.

1.

- Word, 포토샵 등을 작업할 때 ctrl + z 키를 이용하면 이전 작업 내용으로 돌아갈 수 있다.(되돌리기)

- 이는 컴퓨터가 사용자의 작업을 모두 Stack에 기록하고 있기 때문에 가능한 기능이다.

- 즉, 계속해서 Stack에 사용자의 작업 내역을 기록하고 있다가 ctrl + z 명령이 들어오면 가장 최근에 기록한(들어온) 작업을 버리는 것이다.

출처 - 인프런, 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

 

2. 

- VSCode에 코드를 작성하면 자동으로 문법 검사를 해준다.

{
   const garden = (3 + 16);
}

- 위의 코드에서 중괄호, 소괄호에 대한 문법 검사는 아래와 같은 방식으로 이루어진다.

- 문법검사기(이하 검사기)는 여는 괄호를 만나면 해당 괄호를 Stack에 넣고 이후 닫는 괄호를 만나면 미리 Stack에 넣어놨던 여는 괄호와 같은 종류인지를 체크한다.

 

1. 여는 괄호를 만났으므로 Stack에 넣는다.

출처 - 인프런, 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

 

2. 여는 괄호를 만났으므로 또 Stack에 넣는다.

출처 - 인프런, 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

 

3. 닫는 괄호를 만났으므로 가장 최근에 Stack에 넣어놨던 괄호를 꺼내 서로 일치하는 괄호인지 체크한다.

- 서로 일치하는 괄호이기에 문법 검사 통과 & 꺼냈던 괄호는 Stack에서 버린다.

출처 - 인프런, 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

 

4. 또 닫는 괄호를 만났으므로 또 가장 최근에 Stack에 넣어놨던 괄호를 꺼내 서로 일치하는 괄호인지 체크한다.

- 서로 일치하는 괄호이기에 문법 검사 통과 & 꺼냈던 괄호는 Stack에서 버린다.

- 검사기는 더 이상 체크할 코드도 없고 Stack도 비어있기에 문법 에러가 발생하지 않았다고 판단한다.

- 코드를 전부 검사했는데 Stack에 데이터가 남아있거나 괄호의 짝이 맞지 않으면 문법 에러가 발생했다고 판단한다.

출처 - 인프런, 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)