개요

• 스택은 가장 마지막에 삽입된 데이터가 가장 먼저 나오는 LIFO(Last-in First-Out) 구조이다.
• 스택의 끝을 위(Top), 스택의 시작을 밑(Bottom)이라고 한다.
• 괄호의 쌍이 맞는지 검사하거나 후위 표기식, DFS 등에 사용될 수 있다.

1. 중위표기식 : 연산자가 가운데에 위치
2. 후위표기식 : 연산자가 가장 나중에 위치
   

추상 자료형

• 스택은 연산에 대해 아래와 같이 동작해야 한다.

1. 읽기 (Peek) : 스택의 위에 위치한 데이터에 접근한다.
2. 삽입 (Push) : 스택의 위에 데이터를 삽입한다.
3. 삭제 (Pop) : 스택의 위에서 데이터를 삭제한다.

• 스택은 리스트의 연산을 제한하는 기능도 하기 때문에 검색이 없다.

사용법

• C#에서는 Stack으로 구현되어 있다.
  

성능

• 각 연산에 대한 성능이다.

1. 읽기 : 위에 바로 접근할 수 있기 때문에 O(1)
2. 삽입 : 위에 바로 삽입하기 때문에 O(1)
3. 삭제 : 위에서 바로 삭제하기 때문에 O(1)