스택(Stack)

스택(stack)

스택: 차곡차곡 쌓아올린 형태의 구조

같은 구조, 같은 크기의 자료를 정해진 방향으로만 쌓는다. top(맨윗층)에서만 접근할 수 있다.

크레페처럼 생각하면 된다. 한 층 한 층 쌓아올려서 맨 윗층부터 하나씩 벗겨먹는것.

• LIFO: Last-In-First-Out 구조: 먼저 들어간 게 바닥에 깔림(오래됨) , 최근에 들어간 게 맨 위층에 얹혀짐. 꺼낼때는 윗층(최근꺼)부터.

• push: 삽입(넣기)

• pop: 삭제(꺼내기)

스택에 push

1. top 포인터가 +1을 하면 stack의 크기를 넘지 않는가 확인하고 (overflow)

2. top+1한 포인터에 push

스택에 pop

1. top포인터가 -1을 하면 땅바닥을 뚫지 않는가 확인하고(underflow1)

2. top에 있는 포인터에 pop

stack뿐만 아니라 모든 코드를 짤 때, 예외가 있는지부터 확인해야한다!!

ex) stack: 크기 넘어감 / 나눗셈: 0으로 나눔. / char str[5]: 글자가 4글자를 넘어가는지 / ...

스택의 구현은 배열. 리스트 둘 다 가능하다.

빈 스택에서는 (스택 막 생성하고나서 아무것도 안 넣었을 때) ; top의 index를 -1로 둔다.

원소 하나하나 넣어가면서 그 원소의 index를 top으로 설정해주는 것!

스택의 응용

1. 역순 문자열 만들기

2. 시스템 스택

3. 수식의 괄호 검사

4. 수식의 후위 표기법 변환