자료구조 / 스택 (Stack)

스택(Stack)이란?

1️⃣ 스택은 뒤로 넣고 뒤만 뺄 수 있는 연결리스트이다.

2️⃣ 스택은 실행이 되는 특정한 순서를 따르는 선형적 데이터 구조이다.

 

스택의 구조

두가지 순서로 동작한다.

1️⃣ LIFO(Last In First Out) : 후입선출

2️⃣ FILO(First In Last Out) : 선입 후출

 

JS에서는 pop()과 push() 메서드를 이용하면 된다.

 

 

중요한 포인트!!!

스택은 크기를 고정해서 사용하기 때문에,

고정된 크기의 스택에 데이터를 계속 넣게 되면 다른 메모리 영역을 침범한다.

이를 StackOverFlow라고 한다.

 

스택 메모리 영역은 프로그램이 자동으로 사용되는 임시 메모리 영역이다.

(지역변수, 매개변수, 리턴 값 같이 잠시 사용되고 사라지는 데이터를 저장하는 영역)

 

프로세스가 메모리에 로드되면서 스택 사이즈가 고정이 되어,

런타임시 스택 사이즈를 바꾸지 못하게 되어 결국, 스택의 크기가 고정이 됩니다.

 

 

스택의 예시

• 기호 짝 맞추기(Balancing of symbos)
  예) 괄호의 짝이 맞는지 확인하는 문제
  
• 중위 표기법(Infix)에서 후기 표기법(Postfix) or 전위 표기법(Prefix)으로 전환
  
  
• 포토샵 같은 에디터에서 사용하는 Redo-undo & 웹 브라우저에서 사용하는 앞으로 가기 / 뒤로 가기
  
• 히스토그램(histogram), 주가 스팬(stock span), 트리 순회(tree traversal),
  하노이의 타워(Tower of Hanoi)와 같은 알고리즘
  
  
• 백트래킹(back tracking)은 알고리즘 설계 기법 중 하나로, 만약 길이 효율적이지 않다면,
  다시 이전 상태로 돌아와 다른 길로 가는 체스와 같은 게임이나
  미로 찾기 같은  Knight-Tour 문제, N-Queen 문제가 있다.
  우리가 현재 상태로 다시 이전 상태로 돌아가기 위해서 이전 상태가 저장되어 있는 스택을 사용한다.
  
  
• 그래프 알고리즘의 Topological 정렬과 Strongly Connected Components
  (현대 컴퓨터의 메모리 리는 주로 작동 목적을 위해 스택을 사용한다.)
  (컴퓨터에서 작동되는 프로그램은 각자 할당된 메모리가 있음)