3장: 스택과 큐

3.1 스택

삽입, 삭제가 top에서만 이루어진다.

LIFO(Last In First Out)

* 시스템 스택: 프로그램이 런타임에 함수 호출 시 사용

처음 top을 -1로 정해 빈 스택 확인

3.1.1 추상자료형

생성

삽입, isFull: 스택이 가득 찼는지 확인한 후 삽입

삭제, isEmpty: 스택이 비어있는지 확인 후 삭제

push(item);
item = pop();

---

3.2 동적 배열을 이용한 스택

위의 방식처럼 MAX_STACK_SIZE를 통해 스택을 생성하는 경우 최적의 크기를 알아야 한다는 결점 -> 동적 할당된 배열을 통해 해결

처음 스택의 크기를 1로 설정하여 배열 생성

스택이 가득 차있는 경우 realloc( )을 이용하여 기존 스택의 크기를 2배로 증가

: 시간 비용이 많이 드는 것처럼 보이지만 아니다!

​ => 메모리 할당에 O(1), 스택 원소 복사에 O(1)의 시간 복잡도가 요구된다는 가정하에 O(스택_크기)의 시간 복잡도(스택 크기는 2의 멱수)

​ => 2^k^의 원소에 대한 총 시간 복잡도 다음과 같다.
$$
{O(\sum\limits_{i=1}^{k}2^i)} = O(2^{k+1}) = O(2^k)
$$

---

3.3 큐

삽입과 삭제가 다른 끝에서 발생하는 리스트

삽입되는 끝: rear

삭제되는 끝: front

스택에서는 top만 이용하는 것과 달리 rear, front 2개의 변수 사용

* 작업 스케줄링: 우선순위를 사용하지 않는 OS에서 작업을 들어오는 순서대로 처리

​

3.3.1 추상자료형

생성

삽입, isFull: 큐가 가득 찼는지 확인 후 삽입

삭제, isEmpty: 큐가 비었는지 확인 후 삭제

rear가 MAX_QUEUE_SIZE-1가 됐을 때(큐가 가득 찼을 때), 전체 큐를 이동시켜 front가 -1이 되도록 이동 -> 비용 多

=> 원형 큐를 이용해 해결: (MAX_QUEUE_SIZE-1) + (1) = (0), (0) - (1) = (MAX_QUEUE_SIZE-1) : 모듈러 연산 이용

​ * 원형 큐의 문제점: 큐가 가득 차거나 비어있을 때 모두 rear == front, 구분 불가

​ => 큐가 가득 차기 직전에 큐의 크기를 늘려서 rear == front인 상황이 비어있는 경우만 존재하도록 제한

---

3.4 동적 할당 배열을 이용한 원형 큐

realloc을 이용해 배열의 크기를 2배로 만들고 추가적인 작업 필요

[0]	[1]	[2]	[3]	[4]	[5]
C	D	E		A	B

front = 3, rear = 2

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]	[10]	[11]
C	D	E		A	B

front = 3, rear = 2

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]	[10]	[11]
C	D	E								A	B

front = 9, rear = 2

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]	[10]	[11]
A	B	C	D	E

front = 11, rear = 4

1. 새로운 큐 newQueue 생성
2. 뒷부분에 해당하는 queue[front+1]부터 queue[capacity-1]까지를 newQueue[0]부터 newQueue[capacity-front-2]에 복사
3. 앞부분에 해당하는 queue[0]부터 queue[rear]까지를 newQueue[capacity-front-1]부터 newQueue[capacity-front-1+rear]에 복사

---

3.5 미로 문제

---

3.6 수식 계산

3.6.1 수식

연산 순서를 결정하는 상위 계층 존재

안쪽 괄호 먼저 계산

C에서의 연산자 순서

1. ->

   ( ): 함수 호출

   [ ]: 배열

   ->, .: 구조체 또는 공용체 멤버

2. ->

   --, ++: 후위 연산자

3. <-

   --, ++: 전위 연산자

   !: not

   ~: 보수

   , +: 단항(부호)

   &, *: 역참조, 참조

   sizeof: 크기(바이트 단위)

4. <-

   (type): typecast

5. ->

   *, /. %: 곱

6. ->

   +, -: 합, 차

7. ->

   <<, >>: shift

8. ->

   >, =>, <, <=: 비교

9. ->

   ==, !=: 등위

10. ->

    &: 비트연산자 and

11. ->

    ^: 비트연산자 xor

12. ->

    |: 비트연산자 or

13. ->

    &&: 논리연산자 and

14. ->

    ||: 논리연산자 or

15. <-

    ?:: 조건연산자

16. <-

    =, +=, -=, /=, %=, <<=, >>=, &=, ^=, |=: 할당

17. ->

    ,: 콤마

3.6.2 전위식

대부분의 컴파일러가 사용하는 수식

계산 시 왼쪽에서 오른쪽으로 스캔

연산자를 만날 때까지 스택에 피연산자 삽입

연산자를 만나면 스택에서 필요한 피연산자를 삭제 후 계산 결과를 삽입

* 입력받은 숫자가 ASCII 값이기 때문에 '0'을 빼서 원하는 값을 갖도록 한다. ex ) '1' - '0' = 1

** 호출되는 함수에서 case문을 사용 시 각 케이스에 return을 사용하면 break 불필요

3.6.3 중위식 -> 전위식

1. 수식의 모든 계산에 괄호
2. 연산자를 닫는 괄호로 이동
3. 괄호 제거

스택을 이용한 수식 전환

괄호가 없는 식

피연산자는 즉시 출력

연산자를 만나면 top에 있는 연산자와 비교하여 우선순위가 낮을 때까지 pop한 후 push

수식의 끝에 도달했을 때 스택이 비어있지 않다면 모두 pop

괄호가 있는 식

위와 동일한 방식으로 진행하되 닫는 괄호가 나올 경우 여는 괄호까지의 연산자 pop

여는 괄호는

• 스택 내부에서의 우선순위(isp)는 가장 낮아야 하고 - 스택에 들어간 이후 다른 토큰이 스택에 들어갈 수 있기 때문
• 삽입 시 우선순위(icp)는 가장 높아야 한다. - 입력 시 반드시 스택에 들어가 위해

분석: O(n)

* 중위식 -> 후위식

1. 입력된 문자열 뒤집기
2. 뒤집어진 문자열을 전위식으로 정리
3. 전위식 뒤집기

---

3.7 다중 스택과 큐

• m의 메모리에 n개의 스택을 사용하는 경우

  공간을 n등분하여 boundary로 구분 (# of boundary = n+1)

  • top[i] == boundary[i+1]: stackFull
  • top[i] == boundary[i]: stackEmpty
• 다른 스택에 여유 공간이 있는데 꽉 찬 스택(i)에 삽입이 발생하는 경우
  1. 사용하지 않고, i < j < n을 만족하는 최소의 j를 찾아 i+1부터 j까지 오른쪽으로 한 스택씩 이동
  2. 1로 해결되지 않은 경우, 사용하지 않고, 0 <= j < i를 만족하는 최대의 i를 찾아 0부터 i까지 왼쪽으로 한 스택 씩 이동
  3. 2로 해결되지 않은 경우, stackFull

worst case: O(MEMORY_SIZE)

* 단어

• shortcomming 결점
• * This is not the case 사실이 아니다
• intriguing 흥미로운
• precedence 상위
• mnemonics 기억술
• auxiliary 보조적인
• empirically 경험적으로
• futile 쓸모없는