[자료구조] 3강 - 스택

✅ 1. 스택의 개념

(1) 스택의 정의

• 객체와 그 객체가 저장되는 순서를 기억하는 방법에 관한 자료구조이다.
• 가장 먼저 입력된 자료가 가장 나중에 출력되는 관계를 표현함
• 쉽게말해, 스택은 후입선출로써 가장 나중에 넣은 객체가 가장 먼저 나온다.
• 이러한 추상 자료형을 구현하려면 구현과정에서 저장되는 순서를 기억해줘야 한다는 의미이다.
• 관계를 표현하기 위해서 연산이 필요하며, 객체에 대한 정의와 연산이 모여서 순서가 기억되는 스택의 추상 자료형이 완성됨
• 쉽게말해, 자료 구조에서 데이터를 단순히 저장하는 것뿐만 아니라, 데이터를 다루는 연산이 중요하며 스택(abstract data type, ADT)은 **데이터(객체) + 연산(push, pop 등)**이 모여 만들어지고 스택은 후입선출(LIFO) 순서를 유지한다는 특성을 가진다는 의미이다.
• 0개 이상의 원소를 갖는 유한 순서 리스트이다.
• push(add)와 pop(delete)연산이 한곳에서 발생되는 자료구조이다.

✅ 2. 스택의 추상 자료형

(1) 스택의 추상자료형

• 스택 객쳬: 0개 이상의 원소를 갖는 유한 순서 리스트

(2) CreateStack 연산 ( Stack 추상 자료형 )

• Stack 자료구조의 추상 자료형으로, CreateStack 연산의 대한 정의이다.

(3) Push 연산

• 스택의 Push 연산은 가장 위에 데이터를 삽입하고, 해당 스택을 반환을 해준다.
• 해당 부분은 Stack 의 Push 연산의 대한 정의인 추상 자료형이다.

(4) Pop 연산

• 가장 위의 있는 원소를 삭제하고 반환을 해주는 연산을 의미한다.

(5) 정리

• 스택은 메모리의 자유로운 사용(무작위 접근)을 억제하고, 데이터를 일정한 규칙(LIFO)으로만 접근하도록 구조화함으로써 효율적으로 관리할 수 있게 만든 자료구조이다. 즉, 규칙을 만듦으로써 제한을 둔다는 것이 핵심이다.
• 한 마디로, 스택은 자유를 제한해 순서 보장과 효율을 얻는 자료구조로 이해 할 수 있음.
• 스택은 기본적으로 push(삽입), pop(삭제), peek(맨 위 값 확인) 이 세 가지 연산만 제공한다.
• 그 외 임의의 위치에 접근하거나 중간 데이터를 삭제하는 것은 허용되지 않음
• 이러한 제한 때문에 메모리 관리가 간단해지고, 연산도 효율적이게 됨. ( 즉, 제한은 자료구조의 핵심인 것이다. )
• 데이터들 사이의 관계를 구조화한것이 자료구조이며, 추상 자료형을 통해서 데이터들의 사이의 관계를 정의하고 있다.

(6) Pop/Push 연산의 실행

• 1. CreateStack(3): 제일 초기상태로 3개의 공간을 가지는 Stack 이 만들어짐.
• 2. Push(stack, 'S'): 제일 첫 번째 위치에 'S' 데이터가 들어가게 된다.
• 3. Push(stack, 'T'): 두 번째 위치에 들어가게 된다.
• 4. Pop(stack): 제일 마지막 위치 즉, top의 위치에 있는 'T' 의 값이 삭제되면서 'T' 데이터를 반환받는다.
• 5. Push(stack, R): 해당 stack top 에 'R' 삽입
• 6. Push(stack, 'P'): 'P' 삽입 ( 이 부분에서 Stack 의 공간인 3칸이 다 차버림. )
• 7. Push(stack, 'Q'): Q는 삽입이 되지않는다. 이유는, 추상 자료형 설계 즉, ADT 설계에 의한 제약으로 막힘.
• 설계시점에서 연속된 메모리 공간을 미리 크기를 정해놓으면 할당이 한 번에 끝나므로 메모리 관리에 효율적이라서
• 스택이 LIFO 구조로 동작한다는 것은 제한된 연산 규칙을 갖는 뜻이며, 만약 제한 없이 계속 늘어난다면, 프로그램에서 예기치 못한 메모리 사용 증가 즉, 무한 스택으로 인해 시스템이 불안정해질 수 있기 때문임.
• 결과적으로 Stack 에서는 StackIsFull / StackIsEmpty 와 같은 연산을 통해 안전성을 확보하고 있음.

(7) StackIsFull / StackIsEmpty 연산

• StackIsFull: 스택이 미리 정해진 최대 크기까지 데이터를 채운 상태에서 Push 를 시도할 때 불리언 값 리턴
• StackIsEmpty: 스택에 데이터가 하나도 없는 상태에서 Pop 이나 Peek 를 시도할 때 불리언 값 리턴

---

✅ 3. 스택의 응용

(1) 스택의 다양한 응용

• 변수에 대한 메모리의 할당과 수집을 위한 시스템 스택
• 서브루틴 호출 관리를 위한 스택: 함수 호출 시 반환 주소를 스택에 저장(push)하고, 함수가 끝나면 스택에서 꺼내(pop) 해당 위치로 돌아가 실행을 이어가는 구조가 Call Stack 이며, 운영체제가 스택을 위한 메모리 공간을 할당을 해준다.
• 연산자들 간의 우선순위에 의해 계산 순서가 결정되는 수식 계산
• 인터럽트의 처리와 되돌아갈 명령 수행 지점을 저장하기 위한 스택
• 컴파일러, 순환 호출 관리

---

✅ 4. 스택의 연산

• 스택의 연산 구현하는 방법에 관한 내용임
• top: 스택에서 가장 마지막에 삽입된 데이터의 위치를 가리키는 값임.

(1) 스택의 삭제 연산

// < --a : 전위 감소 >
int a = 5;
int b = --a; // a = 4, b = 4

// < a-- : 후위 감소 >
int a = 5;
int b = a--; // b = 5, a = 4

• --a (전위 감소): 먼저 a 의 값을 1 줄이고 그 다음, 줄어든 값의 식의 결과값으로 사용
• a-- (후위 감소): 먼저 현재 a 의 값을 식의 결과값으로 사용하며 그 다음, a 를 1 줄임
• 즉, 연산을 하고 변수에 할당하느냐, 연산을 하지 않고 값만 변수에 할당하느냐의 차이임.

• 'top--' 에서 사용된 '--' 연산자의 위치에 따라 연산의 적용순서가 달라질 수 있음.
• top--: top 값을 1 감소시키는 연산을 의미함.
• 즉, 스택에서 데이터를 하나 삭제(pop)한 후, top을 아래로 이동시키는 것을 의미함.

[ 스택의 생성 연산 ]

[ 스택의 삭제 연산 ]

[ 스택의 삽입 연산 ]

[ 정리 ]

• 추상자료형 즉, 자료구조가 추상화 된 인터페이스를 구현한 내용이라고 볼 수 있음.

---

✅ 5. 사칙연산식의 전위, 후위, 중위 표현

(1) 수식의 계산

• 연산자의 계산 우선순위를 생각해야 함
• ex) A + B * C + D -> ((A + (B * C)) + D)
• 이러한 우선순위 계산은 사람은 한 번에 나눠서 할 수 있지만, 컴퓨터는 전체를 못보지만 방법이 있음.
• 컴퓨터는 왼쪽부터 오른쪽으로 입력이 되기 때문에 우선순위 파악이 어려움 ( 스택을 활용 함 )

(2) 수식의 표기 방법

[ 중위 표기법 (infix notation) ]

• 연산자를 피연산자 사이에 표기하는 방법
• A + B
• 사람이 읽고 이해하기는 쉽지만, 컴퓨터 입장에서는 연산자 우선순위와 괄호 처리를 해석해야 해서 복잡함.

[ 전위 표기법 (prefix notation) ]

• 연산자를 피연산자 앞에 표기하는 방법
• +AB

[ 후위 표기법 (postfix notation) ]

• 연산자를 피연산자의 뒤에 표기하는 방법
• AB+ : A와 B를 더하겠다는 연산임
• 괄호가 필요 없음 (우선순위가 표기 방식 안에 이미 반영이 됨)
• 컴퓨터가 스택을 사용해서 계산하기 매우 간단해짐

(3) 후위 표기법

• 중위 표기법은 우선순위와 괄호를 해석해야 해서 복잡하지만, 후위 표기법은 스택만으로 바로 계산이 가능함.

// 예시: AB+ (후위 표기법)
// A -> push
stack: [A]
// B -> push
stack: [A, B]
// + -> pop 2개 꺼냄 (B, A) -> A + B 계산 -> 결과 push
stack: [A+B]
// 최종 결과: A + B

• 그래서 중위 표기법을 후위 표기법으로 바꾸게 된다. 즉, 사람이 쓰기 좋은 수식을 컴퓨터가 계산하기 좋은 수식으로 변환

• 즉, 첫번째 수식은 중위 표기법 이며, 아래로 갈수록 후위 표기법으로 변경 ( 컴퓨터가 알아보기 쉽게 )
• B + K 는 BK+, /D 나누기 연산 또한 D/ 로 스택형식으로 정의

(4) 중위 표기식의 후위 표기식 변환 방법

• 먼저 중위 표기식을 연산자의 우선순위를 고려하여(피연산자, 연산자, 피연산자)의 형태로 괄호로 묶어줌
• 각 계산뭉치를 묶고 있는 괄호 안에서 연산자를 계산뭉치의 가장 오른쪽으로 이동시킴
• 각 계산뭉치를 하나의 피연산자로 고려하여 위를 반복함
• 괄호를 모두 제거함 ( 스택에 넣고 2개씩 pop 하는 방식 )

1. 피연산자(숫자, 변수) → 스택에 push
2. 연산자 → 스택에서 2개 pop → 계산 → 결과를 다시 push
3. 끝까지 다 처리하면 → 스택에 최종 결과 1개만 남음

• 즉, 하나씩 처리하면서, 중간 결과를 계속 스택에 쌓아나가는 방식임.

[ 정리 ]

• 결국 해당 중위 표기식과 후위 표기식 변환 방법은 스택의 응용에 이런게 씌인다는 것을 알려주기 위함임.
• 결국 중위나 후위 표기식의 개념들은 인터프리터나 컴파일러에서 이용되는 느낌

(5) 후위 표기식의 계산 알고리즘 ( 스택 응용 )

• 데이터를 받아서 저장할 변수 선언 및 초기화 과정

• 반복문을 통해서 exp[i] ( 후위 표기식 ) 의 값들을 하나씩 피연산자인지 조건문을 통해 체크
• 만약 피연산자인 경우에는 push 를 통해 stack 에 값을 하나씩 채움

• 위의 조건문이 이어져있는 부분이며, else 만약 연산자인 경우에는 즉, +-*/ 인 경우에 실행됨.
• 즉, symbol 변수에 피연산자가 들어가 있는 경우에 else 문이 실행 됨.
• oper2 , oper1 각 변수에 pop() 을 통해 stack 에서 값을 두개 제거하면서 리턴을 받아 변수에 할당을 함.
• 해당 symbol 변수에 피연산자
• switch 문을 통해 symbol 피연산자가 어떤건지 파악한 뒤 조건에 맞게 연산을 수행함
• 최종적인 return pop(); 은 모든 반복문을 수행한 뒤 수식의 내용이 비었다. 즉, 배열의 모든 값을 본 경우에 해당됨.
• 결론은 모든 반복문을 수행했으니, 최종 결과값이 나온 상태일거임. 즉, pop() 을 함으로써 최종 값을 뽑아서 리턴을 해줌.

[ 정리 ]

• 해당 알고리즘은 C 프로그래밍 언어의 코드로 구현한 내용을 기반함.