스택 - 개념

📌 스택이란?

• 스택은 안주 단순한 규칙을 가지고 있는 리스트이다.

• First in Last out(FILO)으로 먼저 들어간 데이터가 나중에 나오는 규칙을 가지고 있다.

• 스택은 먼저 들어온 것이 나중에 나오는 조건만 충족한다면 어떤 자료구조로 구현하든지 상관이 없다.

✅ 앞서 포스팅한 자료구조인 연결리스트로 스택을 구현해보자.

• 전 포스팅의 연결리스트는 head 하나로 모든 노드를 연결했다.
• head를 이용하면 스택을 아주 간단하게 만들 수 있다.
  • 데이터 삽입을 무조건 첫 번째 인덱스에 한다.
  • 마찬가지로 데이터 제거도 무조건 첫 번재 인덱스에 하는 것이다.

정수 1, 2, 3, 4를 첫 번재 인덱스에만 삽입시켜보자.

• 먼저 1을 삽입하면 리스트에 1을 담은 노드 하나만 존재한다.
• 이제 2를 삽입하는데 2를 가장 압부분, 즉 head에 삽입한다.
• 3과 4를 차례대로 삽입하면 4가 가장 앞에 위치하게 된다.

이제 이 데이터들을 제거해보자.

• 제거도 가장 앞 부분, 즉 head에 있는 노드를 제거한다. 위의 그림에서 4가 먼저 제거된다.
• 순서대로 4 > 3 > 2 > 1

한쪽으로만 데이터를 삽입, 제거하면 간단텍스트하게 스택이 된다.

🤔 여기서 궁금증이 하나 생긴다.

차례가 중요할 때는 스택은 쓸모없는 자료구조라고 생가할 수 있다. 하지만 스택이 딱 어울리는 상황이 있다.

ctrl + z 되돌리기 기능

포토샵으로 그림을 그린다고 가정할 때 실수를 하면 ctrl + z로 되돌리기를 한다. 이 되돌리기 작업이 단순히 전에 했던 작업으로 돌아가면 된다고 생각하지만 컴퓨터는 작업을 전부 스택에 기록하고 있다. 사용자가 ctrl + z를 누르면 가장 최근에 들어온 작업을 꺼내서 버린다

이렇게 자료구조 하나에 담기만 했는데 원하는 동작을 구현할 수 있다.

스택을 이용하면 어렵고 복잡한 작업을 쉽게 해결할 수 있는 상황이 있다. 스택의 특성을 잘 알아둬서 적절한 상황에 이용하면 작업의 효율이 높아진다.

with 그림으로 쉽게 배우는 자료구조와 알고리즘