[자료구조] 3. 스택

 

※ 방송통신대학교 컴퓨터공학과의 '자료구조' 강의 내용 기반으로 작성되었음

 

[1] 스택의 개념 ✅

🔑 스택의 정의

• 객체와 그 객체가 저장되는 순서를 기억하는 방법(=연산)에 관한 자료구조
• 가장 먼저 입력된 자료가 가장 나중에 출력되는 관계를 표현
  → 삭제와 삽입이 맨 위에서 발생함
  →  인덱스(첨자)라는 개념이 필요함
• 관계를 표현하기 위해서 연산이 필요하며, 객체에 대한 정의와 연산이 모여서 순서가 기억되는 스택의 추상 자료형이 완성됨
• 0개 이상의 원소를 갖는 유산 순서 리스트
• push(add) 와 pop(delete) 연산이 한 곳에서 발생하는 자료구조

 

 

---

 

 

[2] 스택의 추상 자료형 ✅

🔑 스택의 추상자료형

• 스택 객체 : 0개 이상의 원소를 갖는 유한 순서 리스트
  → '순서'는 연산을 통해 보장된다.

 

🔑 CreateStack 연산 

• Stack CreateStack(정수 maxStackSize) : 스택의 크기가 maxStackSize인 빈 스택을 생성하고 반환한다.

 

🔑 Push 연산

• Stack Push(stack, item) : 스택이 full이 아니라면 스택의 가장 위에 item을 삽입하고 스택을 반환한다. 스택이 full이라면 stackFull을 출력한다. 

 

 

 

🔑 Pop 연산

• Element Pop(stack) : 스택이 비어 있다면 stackEmpty를 출력하고, 그게 아니라면 스택의 가장 위에 있는 원소(element)를 삭제하고 반환한다.

 

 

🔑 StackIsFull / StackIsEmpty 연산

• Boolean StackIsFull(stack, maxStackSize)
  : stack의 elements의 개수가 maxStackSize 와 같다면 TRUE, 아니라면 FALSE
• Boolean StackIsEmpty(stack)
  : stack 이 CreateStack(maxStackSize)와 같다면 TRUE, 아니라면 FALSE

 

 

---

 

[3] 스택의 응용

🔑 스택의 다양한 응용

• 변수에 대한 메모리의 할당과 수집을 위한 시스템 스택
• 서브루틴 호출 관리를 위한 스택
• 연산자들 간의 우선순위에 의해 계산 순서가 결정되는 수식 계산
• 인터럽트의 처리와 되돌아갈 명령 수행 지점을 저장하기 위한 스택
• 컴파일러, 순환 호출 관리

 

 

---

 

 

[4] 스택의 연산

🔑 스택의 삭제 연산

• 'top--' 에서 사용된 '--' 연산자의 위치에 따라 연산의 적용 순서가 달라질 수 있음

 

 

 

 

---

 

 

[5] 사칙연산식의 전위/후위/중위 표현

🔑 수식의 계산

• 연산자의 계산 우선순위를 생각해야 함

 

🔑 수식의 표기 방법

• 중위 표기법(infix notation) : 연산자를 피연산자 사이에 표기하는 방법
  → A + B
• 전위 표기법(prefix notation) : 연산자를 피연산자 앞에 표기하는 방법
  →  + A B
• 후위 표기법(postfix notation) : 연산자를 피연산자의 뒤에 표기하는 방법
  →  A B +
• 일반적으로는 입력은 중위 표기법으로 수행하고 컴퓨터는 후위 표기법으로 계산하여 값을 도출한다.
• 중위 표기식의 후위 표기식 변환방법(=알고리즘)
  (1) 먼저 중위 표기식을 연산자의 우선순위를 고려하여 (피연산자, 연산자, 피연산자)의 형태로 괄호로 묶어줌
  (2) 각 계산뭉치를 묶고 있는 괄호 안에서 연산자를 계산뭉치의 가장 오른쪽으로 이동시킴
  (3) 각 계산뭉치를 하나의 피연산자로 고려하여 위를 반복함
  (4) 괄호를 모두 제거함