3-5강 - Multiple Stack and Queue (다중 스택, 다중 큐)

7. Multiple Stack and Queue

1) 개념

1> 정의 : 하나의 array 안에 여러 개의 stack(queue)를 구현

2> idea : m개의 원소를 가진 array를 n개의 stack이 들어갈 수 있게 n등분한다.

 

2) 구현

1> 선언

- MEMORY_SIZE : array의 size

- MAX_STACKS : stack의 최대 개수 + 1 (boundary[0] ~ boundary[n]까지 넣어야하니까)

- element memory[MEMORY_SIZE] : array 선언
- int top[MAX_STACKS] : memory(array)를 n등분하는 index
- int boundary[MAX_STACKS] : memory(array)를 n등분하는 index
- int n : 사용자가 정의할 stack의 개수 (MAX_STACKS >= n+1)

2> memory n등분된 공간에 1~n까지의 index를 부여한다.

- 기존 의미처럼 top[0]은 한 칸 물러선 -1이다. (그림에서도 약간 왼쪽을 가리킨다.)

- top[i]과 boundary[i]의 값이 같다. 

- top[i]과 boundary[i] 둘 다 등분을 의미한다.

- top[i]과 boundary[i] 모두 array의 특정(n등분하는) index-1이다.

- boundary[n]까지 존재, top[n-1]까지 존재

3> top[0]와 boundary[0] 초기화

모두 -1로 초기화

4> memory를 n등분

top[i] = (MEMORY_SIZE / n) * i

 

#include <stdio.h>
#include <string.h>
#define MEMORY_SIZE 100 /* size of memory */
#define MAX_STACKS 10 /* maximum stack size */

#define MAX_STACK_SIZE 100 /* maximum stack size */
typedef struct
{
	int key;
}element;

element memory[MEMORY_SIZE];
int top[MAX_STACKS];
int boundary[MAX_STACKS];
int n = 9;

int main()
{
	top[0] = boundary[0] = -1;
	for (int i = 1; i < n; i++) {
	top[i] = boundary[i] = (MEMORY_SIZE / n)*i;
	printf("%d\n", boundary[i]);
	}
	boundary[n] = MEMORY_SIZE - 1;
}

 

3) 수정된 add/delete

void AddS (int i, element item)
{ /* add an item to the ith stack */
	if (top[i] == boundary[i+1]) /* stack full ? */
		return stack_full (i);
	memory [++top[i]] = item;
}
void DeleteS (int i)
{ /* remove top element from the ith stack */
	if (top[i] == boundary[i]) /* stack empty ? */
		return stack_empty (i);
	return memory [top[i]--];
}

 

4) 문제점

특정 stack 내부에만 원소가 많아서 다른 구간을 침범하는 문제가 생긴다.

=> 자리 남는 부분을 빌려 쓴다.