Multiple Stack

Programming/Data Structure 2012.10.12 05:20

Multiple Stack

: 배열스택은 처음에 크기가 고정되어 있다는 단점이 있다.

 적게 잡을경우 데이터가 많이 몰려 스택에 데이터를 넣지 못하는 문제가 있을 수 있고, 이를 고려해 스택의 사이즈를 최대로 

 잡아 버리면, 쓰이지 않는 메모리 공간이 많이 낭비가 된다는 점이다.

 Multiple Stack은 이러한 배열스택의 문제점을 조금이나마 줄이고자 하는데 있으며, 기본적인 개념은 스택과 동일하다.

 Multiple Stack에서 추가된 개념은 각 스택을 구분하는 경계선(Boundary)이다. 

 Boundary는 Stack의 개수 +1이며 Boundary[0]< Stack[0] <= Boundary[1], Boundary[1]< Stack[0] <= Boundary[2]

 예를 들어 3개의 스택을 사용하고 있을때 1번스택이 Full이고 2번과 3번에서 메모리가 남을경우 경계선을 조정하여 2번 또는 3번의 경계선을 조정하여 2,3번의 스택사이즈를 줄이는 반면 사용하고자 하는 1번스택을 확장시켜 사용하는 개념이다.(전체 스택 사이즈는 동일)


::Stack Concept

http://effort4137.tistory.com/entry/Stack

 

 Keyword

Description 
  FULL_STACK_SIZE

  전체 스택의 크기

  STACK_NUMBER

  생성할 스택의 개수

  boundary

  스택의 경계값( begin<Stack <=end)

  ShiftLeft

  좌측스택 쉬프트(좌측 스택에 빈 공간이 있을경우)
  ShftRight

  우측스택 쉬프트(우측 스택에 빈 공간이 있을경우)

 

::Reference 

     1)데이터가 비어있는 다중스택

     

2) 1번스택과 2번스택 FULL, 0번스택 여유공간 있음. 이때, 1번스택에 데이터가 추가 될경우(다음)

     

3) 1번스택의 자료를 왼쪽으로 한칸 쉬프트 시킨후 데이터 삽입, 바운드리 변경.

 

 

 

::Source

더보기

 다음에는 큐!!

 

'Programming > Data Structure' 카테고리의 다른 글

Multiple Stack  (0) 2012.10.12
Stack  (0) 2012.10.11