<4> 스택(Stack)

이 글은 시험이 21시간정도 남은 사람이 내용 정리를 위해 적는 글입니다.
*[C언어로 쉽게 풀어쓴 자료구조]  책과 숙영리 교수님의 강의를 참고하여 작성하였음을 밝힙니다.

공부하기 실ㅎ어서 이모티콘이라도 바꿔야겠음! 🪸😎

 

 

 

 

🪸 특징

: 후입선출(LIFO) - 스택의 상단에서만 삽입/삭제 연산이 일어남

 

- push () : 스택에 데이터를 추가

- pop () : 스택에서 데이터를 삭제

 

 

🪸 스택을 쓰는 경우

• call stack (recursion)
• undo-redo stack (ctrl+z 같은_)
• string reversal
• graph algorithm
• back tracking - maze solving problem
• balanced parenthesis stack (괄호 검사 알고리즘)
• expression evoluation stack

 

🪸 스택 구현 방법

1) 정적 스택 - 배열을 이용한 스택 구현

장점: 간단하고 빠른 연산 가능

단점: 스택 크기가 컴파일러 타임에 고정되어 프로그램 실행 중 변경 불가능

 

2) 동적 스택 - 연결리스트로 구현 (포인터 이용)

장점: 런타임때 필요한 만큼만 메모리 사용가능. 가변적으로 크기 조정 가능단점: 포인터를 위한 추가 메모리 공간 필요 

 

 

 

---

😎 배열을 이용한 스택 구현  

* 스택에서 가장 최근에 입력되었던 자료를 가리키는 top 변수가 정의됨.

 

 

- 연산 코드

1) 공백(is_empty) : top ==-1인 경우 

* top ==0이라면 index 0에 요소가 들어있다는 것임.

 

2) 포화(is_full) : top == MAX_STACK_SIZE -1  인 경우

*if MAX_STACK_SIZE가 10이면 , 0~9 index 사용 가능하기 때문에 top == 9인 경우 full

 

3) push :

top <- top+1 // top 먼저 1 증가

stack[top] <- x (삽입할 요소)

++ 먼저! (전역변수)

++ 먼저! (구조체)

4) pop :

e <- stack[top] // 삭제할 요소 e에 저장

top <-top-1 // 다음에 top 1 감소

-- 나중에! (전역변수)

-- 나중에! (구조체)

✔️ 배열을 전역변수로 구현하는 경우 -> 스택을 1개밖에 못 씀.

✔️ 배열을 구조체로 구현하는 경우 -> (데이터를 구조체로 묶어서 함수의 파라미터로 전달) -> 스택 여러 개 사용 가능

    ㄴ메모리 번지수를 copy하여 사용(포인터)

 

---

😎 동적 배열(linked list) 스택

- malloc() 을 호출하여 실행 시간에 메모리 할당 받음. 

-스택 삭제시,  free(s);

 

* int capacity -> 현재 크기를 알려주는 변수

*push 연산 : realloc() 사용하여 현재 내용은 유지하면서 동적 mem의 크기 변경

 

 

---

응용

 

🪸 괄호 검사 - [, { , (

1) 왼쪽 괄호 개수 = 오른쪽 괄호 개수

2) 같은 괄호에서, 왼쪽이 오른쪽보다 먼저 나와야 함.

3) 괄호 사이에는 포함관계만 존재

 

😎 알고리즘

: 문자열에 있는 괄호를 차례대로 조사하면서, 왼쪽 괄호가 나오면 스택에 push () -> 오른쪽 괄호가 나오면 top 괄호를 pop() 한 후, 오른쪽 괄호와 짝이 맞는지 검사함. 

 

왼쪽 괄호 push

오른쪽 괄호 만나면 pop하고 비교검사

 

---

🪸 수식의 계산

 

😎 전위(prefix), 중위(infix), 후위(postfix) 

- 전, 중, 후는 연산자 기준! (후위표기법의 경우, 연산자가 피연산자 뒤에 위치함)

*컴파일러는 주로 후위연산자를 사용함. (스택을 사용 -> 연산자의 우선순위 때문에!!!) 

 

 

😎 1) 후위 표기식의 계산

: 수식을 왼->오 로 스캔하면서 피연산자이면 스택에 push()하고, 연산자이면 필요한 수만큼의 피연산자를 스택에서 pop()하여 연산을 실행 -> 결과를 다시 스택에 push()!  (최종적으로 스택에 남아있는 수가 답)

 

 

-코드

*value = ch - '0';  : 숫자를 문자로 바꾸는 ! (피연산자를 의미함)

 

---

 

😎 2) 중위 -> 후위로

* 중위표기식과 후위표기식의 공통점은 "피연산자의 순서가 동일" 하다는 것! 

-> 고려해야할 것은 연산자들의 순서 (✨연산자들의 우선순위 고려!!)

 

: 피연산자의 경우 그대로 출력하고, 연산자의 경우 스택에 저장함.

이때, 스택 안에 들어있는 연산자의 우선순위가 더 높다면? => 스택 안의 연산자를 출력 후에 저장함.

prec는 우선순위 ! s의 우선순위가 더 높기 때문에 pop하고 새 연산자를 push함.

: 우선 순위가 높은 연산자가 먼저 출력되어야 하기 때문!  (*우선순위가 같은 경우에도 일단 출력함*)

 

 

 

* '('(왼쪽괄호)는 제일 우선 순위가 낮은 연산자로 취급됨 / 오른쪽 괄호를 만나면 그 사이의 연산자 모두 출력!

스택에서 왼쪽 괄호를 만날 때까지 pop!

 

 

---

 

🪸 미로탐색 문제

: 현재의 위치에서 가능한 방향(위, 아래, 왼, 오 순)을 스택에 저장해놓았다가 막다른 길을 만나면 스택에서 다음 탐색 위치를 꺼냄. 

* try할 때 최근에 try한 길과 가장 비슷한 길을 try하고 싶다 --> 내가 기억해둔 가장 가까운 길부터 다시 시작 - 스택 필요! 

 

 

-알고리즘

아직 방문되지 않았고 + 벽이 아니면 -> 스택에 push

 

-코드 

*미로는 행렬로 표시

*[][] ==1인 경우는 벽이라서 갈 수 없음 , [][] == '.'인 경우는 방문이 끝난 위치

x는 출구 !