제한된 자료구조

스택 (Stack)

 

• 스택의 특성
  - LIFO(Last In First Out) : 스택의 모든 작업은 항상 최근의 위치에 국한
  - 주요 작업은 삽입, 삭제이며 시작복잡도는 O(1)
  - 배열로 구현하는 방법은 간단한 반면 스택의 크기가 고정된다는 단점이 있음
  - 연결리스트를 이용하면 구현은 약간 복잡하지만 스택의 크기를 필요에 따라 가변적으로 변경할 수 있는 장점이 있음

//배열 구조에서 스택의 삽입
void push(element item)
{ //전역stack에 item의 삽입
	if(top >= MAX_STACK_SIZE-1)
    	stackfull();
    stack[++top] = item;
}

//배열 구조에서 스택의 삭제
element pop()
{ //stack의 최상위 원소를 삭제하고 반환
	if(top == -1)
    	return stackempty();
    return stack[top--];
}

 

• 스택의 응용 : 복귀 주소 관리, 수식 계산, 순환, 이진 트리 순회, 퀵 정렬, 깊이우선 탐색 등

• 복귀주소 관리
  - 프로그램에서 부프로그램을 호출할 때 PC에 들어있는 다음 명령문의 주소를 기억해야 하는데 이 기억된 주소는 부프로그램의 실행이 완료되었을 때 복귀주소로 사용
  
  
• 중위표기식 연산

30 + 50 * 3 - 8

 

1. 연산자 스택과 피연산자 스택 필요

2. 처리할 요소가 피연산자이면 피연산자 스택에 입력

3. 처리할 요소가 연산자이면 우선순위에 따른 비교
-> (처리할 요소의 우선순위 > 연산자 스택의 우선순위)면 연산자 스택에 입력

-> (처리할 요소의 우선순위 <= 연산자 스택의 우선순위)면 피연산자 스택에서 두 번 출력하고 연산자 스택에서 출력한 연산자로 연산 후 결과를 피연산자 스택에 입력

피연산자 스택	연산자 스택
3
50	*
30	+

- 보다 연산자 스택(*)가 우선순위가 높으므로 3 출력 50 출력 * 출력하여 30 * 50 계산 후 150을 피연산자 스택에 삽입

피연산자 스택	연산자 스택
150
30	+

-와 +의 우선순위는 같으므로 150 + 30 계산 후 180을 피연산자 스택에 삽입

피연산자 스택	연산자 스택
8
180	-

최종 계산값으로 172 출력

 

• 후위 표기식

30 50 3 * + 8 -

 

1. 피연산자 스택만 사용

2. 처리할 요소가 연산자일 경우 피연산자 2개를 출력하여 연산 후 결과를 다시 입력

3. 연산자들의 우선순위가 필요없음

4. 괄호가 필요없음

		3
	50	50	150		8
30	30	30	30	180	180	172
30 삽입	50 삽입	3 삽입	* 연산자이므로 피연산자 3, 50 출력하여 연산 후 결과 삽입	30 + 180	8 삽입	180 - 8

 

* 중위표기식을 후위표기식으로 변환규칙

1. 피연산자 스택만 필요! 숫자는 그대로 출력

2. 스택이 비어있으면 연산자 삽입

3. 스택 top 연산자 우선순위 < 현재 연산자 : 스택 삽입

4. 스택 top 연산자 우선순위 >= 현재 연산자 : 스택 삭제

5. ( 괄호는 스택에 그냥 삽입

6. ( 괄호 다음에 오는 연산자는 우선순위 상관없이 스택 삽입

7. ) 괄호가 나오면 ( 괄호가 나올 때까지 연산자 삭제 -> 이후 () 괄호는 그냥 버림! 표기하지 않음

 

Q. 다음의 중위 표기식을 후위 표기식으로 변환하고자 한다. 스택을 이용한 변환 과정 중 토큰 'd'가 처리될 순간에 스택에 저장되어 있는 연산자를 올바르게 나타낸 것은?

a * ( ( b + c ) / d ) * e

1. /

   (

   *

2. /

   +

   (

   (

   *

3. /

   *

4. /

   (

   (

   *

 

-> 피연산자들은 그대로 출력하고 스택에 넣지 않는다.

1. a 출력

2. 스택이 비어있으므로 * 삽입

3. 여는 괄호가 나왔으므로 스택에 (( 추가

4. 피연산자 b 출력

5. 연산자 +는 여는 괄호 다음이므로 우선순위를 따지지 않고 스택에 추가! 현재 스택: * ( ( + (Top)

6. 피연산자 c 출력

7. 닫는 괄호가 나오면 ( 괄호가 나올 때까지 삭제! 따라서 + 연산자 삭제 후 출력 -> 이후에 여는 괄호가 나왔으므로 ( 삭제 (출력X) 현재 스택: * ( /

8. 피연산자 d 출력 => 따라서 정답은 1번

----------------- 이후 스택 과정 ---------------------

9. 닫는 괄호가 나왔으므로 여는 괄호가 나올 때까지 스택 삭제! / 연산자 삭제 후 출력, 이후에 여는 괄호가 나왔으므로 ( 삭제! 현재 스택 : *

10. * 연산자와 스택의 * 연산자는 우선순위가 같으므로 스택에 있는 * 연산자 삭제 후 출력, 현재 연산자 * 삽입

11. 피연산자 e 출력 후 남은 * 연산자 삭제 후 출력

 

출력값 : a b c + d / * e *

 

 

 

 

큐 (Queue)

 

• 큐의 특성
  - FIFO (First In First Out) : 먼저 입력된 데이터부터 출력하고 입력과 출력을 서로 다른 쪽에서 하는 제한된 자료구조
  - Front : 큐의 앞쪽을 가리키는 포인터, 데이터의 출력(삭제)와 관계가 있음 (Head)
  - Rear : 큐의 뒤쪽을 가리키는 포인터, 데이터의 삽입과 관계가 있음 (Tail)
  - 주요 작업은 삽입, 삭제이며 시작복잡도는 O(1)
  - 배열이나 연결리스트로 구현 가능
  
  
• 큐의 응용
  - 작업 스케줄링, 그래프의 너비 우선탐색, 트리의 레벨 순회, 스풀링
  
  
• 순차 큐의 운행

 

선형 큐에서는 rear가 배열의 크기와 같아지면 큐가 꽉 찼다고 판단하며, front와 rear가 동일한 위치를 가리키면 큐가 비었다고 판단

//초기상태
front = rear = -1
//큐가 공백
front = rear
//큐가 꽉 찼음
rear = MAX_QUEUE_SIZE - 1

//순차 큐에서의 삽입
void addq(element item)
{ 
	if (rear == MAX_QUEUE_SIZE - 1)
    	queueFull();
    queue[++rear] = item;
}

//순차 큐에서의 삭제
element deleteq()
{
	if(front == rear)
    	return queueEmpty();
    return queue[++front];
}

 

• 원형 큐
  - 순차 큐에서는 데이터가 실제로 다 차지 않아도 오버플로우 현상이 일어날 수 있는 단점이 존재! 이를 해결하고자 데이터의 이동없이 큐의 처음과 끝을 연결
  - 개념적인 것이고 실제로는 선형배열
  - 두 포인터의 값이 n - 1에 도달하고 1 증가할 때 다시 0이 되어야 하므로 나머지 연산자 %를 사용
  - 삽입, 삭제 시 포인터 값을 증가시킨 후 자료의 입출력이 이루어지며 큐가 가득찬 상태에서도 하나의 빈 공간을 갖게 됨. 하나의 빈 공간은 위치와는 관계없음

front = (front + 1) % n;
//삭제를 위해 front 증가 -> n이 되지 않고 n-1에서 0이 되어 순환
rear = (rear + 1 ) % n;
//삽입을 위해 rear 증가 -> n이 되지 않고 다시 0으로 되돌아옴

//원형 큐 삽입
void addq(element item)
{
	rear = (reat + 1) mod MAX_QUEUE_SIZE;
    if(rear == front)
    	queueFull();
    queue[rear] = item;
}

//원형 큐 삭제
element deleteq()
{
	if(front == rear)
    	return queueEmpty();
    front = (front + 1) mod MAX_QUEUE_SIZE;
    return queue[front];
}

 

• 덱 (Double-Ended Queue : Deque)
  - 큐의 전단과 후단에서 모두 삽입과 삭제가 가능한 큐
  - 입력이나 출력방법에 제한규칙을 갖는 큐, 스택, 원형큐 등의 선형리스트 중에 가장 융통성 있는 자료구조로 양 끝에서 모두 입출력이 가능
  - 단순 연결리스트나 이중 연결리스트로도 표현이 가능
  - 1차원 배열을 이용
  - 입력제한 덱(Scroll) : 출력은 양쪽 다 가능하지만 입력은 한쪽에서만 가능한 구조
  - 출력제한 덱(Shelf) : 입력은 양쪽 다 가능하지만 출력은 한쪽에서만 가능한 구조