(Data Structure) 제한된 선형리스트

제한된 선형리스트

선형리스트 중에서도 원소의 삽입과 삭제시 특별한 제한 조건을 가지고 있는 리스트가 있다.

스택, 큐, 데크가 있다.

• 스택(stack)

모든 원소들의 삽입(push) , 삭제(pop)가 리스트의 한쪽 끝에서만 일어나는 형태의 선형리스트.

한쪽 끝이 막혀있는 원통의 구조라 생각하면 된다.

가장 나중에 입력된 원소가 가장 먼저 삭제되는 LIFO(Last in First out) 구조이다.

• 큐(queue)

들어오는 순서대로 처리를 하는 형태의 선형리스트.

한쪽 끝에서는 삽입만이, 다른 끝에서는 삭제만이 일어난다.

양쪽끝이 뚫려있는 원통의 구조라 생각하면 된다.

스택과는 반대로 FIFO(First in First out) 구조이다.

원소의 삽입, 삭제를 위해서는 rear포인터, front포인터의 두 가지 포인터가 필요하다.

큐에 한 원소가 삽입될 때 rear포인터가 하나씩 증가하고 한 원소가 삭제될때 front포인터가 하나씩 증가하게 된다.

• 데크(deque)

양쪽 끝에서 모두 원소의 삽입과 삭제가 가능한 선형리스트이다.

스택과 큐를 복합시킨 특성을 갖는다.

양 끝의 원소를 가리키는 END1, END2 두개의 포인터를 필요로 한다.

특별한 경우에는 삽입과 삭제를 제한할 수 있다.

삽입이 한쪽에서만 가능하도록 제한한 데크를 ‘입력 제한 데크’ 혹은 ‘스크롤’이라 하고

삭제가 한쪽에서만 가능하도록 제한한 데크를 ‘출력 제한 데크’ 혹은 ‘쉘프’라 한다.