스택은 LIFO(Last-In First-Out) 구조를 가진 자료구조입니다. 즉, 가장 나중에 들어온 데이터가 가장 먼저 나가는 방식으로 작동합니다. 마치 접시를 쌓아 올리는 것처럼, 가장 나중에 쌓은 접시가 가장 먼저 꺼내지는 것과 비슷하다고 생각하면 됩니다.
스택 명령어
| 명령어 | 설명 |
| init() | 스택을 초기화 |
| push(e) | 요소e를 스택의 맨 위에 추가한다. |
| pop() | 스택의 맨 위에 있는 요소를 꺼내 반환한다 그리고 반환하면서 무엇을 반환하는지 알려준다 |
| is_empty | 스탯이 비었으면 TRUE를 아니면 FALSE를 반환한다. |
| is_full() | 스택이 가득 차 있으면 TRUE를 아니면 FALSE를 반환한다 |
| peek() | 스택의 맨 위에 있는 항목을 삭제하지 않고 반환한다. |
스택이 포화 상태이면 push()가 수행되어도 입력할 수 없으므로 오류가 발생합니다. 이를 스택 오버플로(overflow) 오류라고 합니다.
반대로 봉백이면 pop()이나 peek()을 호출했을 때 삭제나 참조할 수 없습니다 이를 스택 언더플로(underflow) 오류라고 합니다.
스택 활용 예시
- 재귀 알고리즘: 재귀 함수를 호출할 때 필요한 데이터를 스택에 저장하여 사용합니다.
- 웹 브라우저 방문 기록: 앞/뒤로 가기 기능을 구현할 때 스택을 사용합니다.
- 실행 취소: 텍스트 편집기에서 '되돌리기' 기능을 구현할 때 스택을 사용합니다.
- 역순 문자열 만들기: 문자열을 뒤집어서 출력해야 할 때 스택을 사용합니다.
- 수식의 괄호 검사: 괄호의 짝 맞춤을 검사할 때 스택을 사용합니다.
스택은 배열구조와, 연결된 구조(링크드 리스트 )로 구현할 수 있습니다
배열로 스택 상단을 표시하기엔 변수가 필요합니다. 이를 top이라 합니다 top은 가장 최근에 입력된(상단) 요소의 위치(인덱스)를 저장합니다
새로운 요소 e를 삽입하는 push() 연산
top을 증가시키는 명령을 무조건 먼저 해줘야한다 top을 증가시키지 않고 스택에 데이터를 넣으면 원래 있는 데이터 자리에 덮어 씌워지는 사태가 발생하기 때문에 top을 먼저 증가시키고 데이터를 삽입해야 합니다
push(e)
if is_full() :
error "overflow"
else :
top <- top +1
data[top] <- e
상단 요소를 삭제하는 pop() 연산도 마찬가지입니다
pop()
if is_empty() :
error "underflow"
else :
top <- top -1 // 함수는 return 밖으로 나가면 코드가 끝나기 때문에 top을 무조건 return이 끝나기전에 처리를 해줘야한다그것이 아니면 전역 변수로 지정 해줘 밖으로 꺼내도 되지만 코드가 쓸대없이 1줄이 더 길어진다
return data[top+1]
괄호 검사 알고리즘
스택은 괄호를 검사할 때도 사용되며 괄호들끼리는 서로 쌍을 이루어야 하고 쌍을 이룬 괄호들은 더는 고려할 필요가 없다는 것을 알 수 있습니다
- 괄호를 저장할 스택을 준비한다
- 입력된 문자를 하나씩 읽어 왼쪽 괄호를 만나면 스택에 삽입한다
- 오른쪽 괄호를 만나면 가장 최근에 삽입된 괄호를 꺼낸다. 이때 스택이 비었다면 오른쪽 괄호가 먼저 나온 상황이므로 조건 2에 위배된다
- 꺼낸 괄호가 오른쪽 괄호와 짝이 맞지 않으면 조건 3에 위배된다.
- 입력 문자열을 끝가지 처리했는데 스택에 괄호가 남아 있으면 괄호의 개수가 같지 않으므로 조건 1에 위배된다.
- 모든 문자를 처리하고 스택이 공백 상태이면 검사 성공이다.
스택의 응용 : 계산기 프로그램
연산자 우선순위를 고려하여 컴퓨터가 인식하기 편하게 표기법을 변경해서 계산을 합니다
| 전위(prefix) | 중위(infix) | 후위(postfix) |
| 연산자 피연산자1 피연산자2 | 피연산자1 연산자 피연산자2 | 피연산자1 피연산자2 연산자 |
| +AB | A+B | AB+ |
| +5*AB | 5+A*B | 5AB*+ |
사람은 중위 표기법에 익숙하지만 컴퓨터는 후위 표기법을 선호합니다 후위 표기법에는 여러 가지 장점이 있습니다
- 괄호를 사용하지 않아도 계산 순서를 알 수 있다.
- 연산자의 우선순위를 생각할 필여가 없다. 식 자체에 우선순위가 이미 포함되어 있기 때문이다
- 수식을 읽으면서 바로 계산할 수 있다. 중위 표기는 괄호와 연산자의 우선순위 때문에 수식을 끝까지 읽고 나서야 계산할 수 있다.
중위 표기의 후위 표기식 변환
중위를 후위 표기식으로 변환해 봅시다. 연산자의 순서는 연산자 우선순위, 괄호에 의해 결정 됩니다.
- 중위 표기식을 순서대로 하나씩 스캔한다.
- 피연산자를 만나면 바로(후위 표기식으로) 출력한다
- 연산자를 만나면 어딘가에 잠시 저장해야 한다. 후위 표기식은 연산자가 피연산자 뒤에 나오기 때문에 적절한 위치를 찾을 때까지 출력을 보류하는 것이다. 이때 스택이 사용된다.
시스템 스택과 순환 호출
스택은 운영체제에서도 중요한 역할을 합니다. 함수의 호출과 반환을 위한 정보를 저장하기 위해 사용됩니다.
함수가 호출될 때마다 활성화 레코드 가 저장되는데 호출된 함수가 종료되면 되돌아갈 프로그램 위치와 매개변수, 지역 변수등이 저장되어 호출한 함수로 복귀했을 때 이전 상태를 손쉽게 복원할 수 있도록 합니다.
순환
함수가 자기 자신을 다시 호출하여 문제를 해결하는 프로그래밍 기법입니다. 변수, 코드의 개수를 줄일 수 있지만 자신을 다시 호출하는 것은 큰 리스크가 있으며 무한 루프에 빠질 수도 있습니다 잘못하면 프로그램에 치명적인 오류를 범할 수 있어 심도 있게 조심히 사용해야 합니다.
