순차&연속 자료구조에서의 삽입&삭제 알고리즘

순차 자료구조에서의 삽입&삭제 알고리즘

• 스택의 크기 : 배열의 크기
• 스택에 저장된 원소의 순서 : 배열 원소의 인덱스
• 인덱스 0번 : 스택의 첫번째 원소 / 인덱스 n-1번 : 스택의 n번째 원소
• 변수 top : 스택에 저장된 마지막 원소에 대한 인덱스 저장
• 공백 상태 : top = -1(초기값) / 포화상태 : top = n-1

순차 자료구조에서의 삽입 연산

1
2
3
4
5
6
7

push(S, x)
	top ← top + 1;
	if(top > stack_SIZE) then
		overflow;
	else
		S(top) ← x;
end push()

1. top←top+1 : 스택 S에서 top이 마지막 자료를 가리키고 있으므로 그 위에 자료를 삽입하기 위해서 top의 위치를 하나 증가시킨다.
2. if(top > stack.SIZE) then overflow; : top의 위치가 스택의 크기(stack_SIZE)보다 크다면 overflow 상태가 되므로 삽입 연산을 수행하지 못하고 연산을 종료(end push())한다.
3. S(top) ← x; : 오버플로우 상태가 아니라면 스택의 top이 가리키는 위치에 x를 삽입한다.

순차 자료구조에서의 삭제 연산

1
2
3
4
5
6
7

pop(S)
	if(top = 0) then underflow;
	else {
			return s(top);
			top ← top - 1;
		 }
end pop()

1. if(top = -1) then error; : 현재 스택이 공백인 경우 삭제할 스택이 없으므로 삭제 연산을 수행하지 못한다.
2. return s(top) : 스택이 공백 스택이 아닌경우 top이 가리키는 원소를 반환한다.
3. top ← top-1 : 스택이 top 원소를 반환하였으므로 top의 위치는 그 아래로 변경하기위해 top의 위치를 하나 감소한다.

연결 자료구조에서의 삽입&삭제 알고리즘

• 순차 자료구조방식의 스택은 구현하기는 쉽다. 하지만 크기가 고정된 배열을 이용하기 때문에 메모리의 낭비가 쉽다. 이 문제점을 연결 자료구조 방식을 이용함으로써 해결할 수 있다.
• 스택의 원소는 단순 연결 리스트의 노드가 된다.
• 스택 원소의 순서는 연결 리스트 노드의 링크를 사용하여 표현한다.
• 스택에 원소를 삽입할 때마다 연결 리스트에 노드를 하나씩 연결한다.
• 스택의 top을 표현하기 위해 참조변수 top을 사용하며 빈 상태의 top은 null로 설정한다.

연결 자료구조에서의 삽입 연산

1
2
3
4
5
6

push(s, item)
	newnode ← getnode();
	newnode.data ← item;
	newnode.link ← top;
	top ← newnode;
end push()

1. newnode.data ← item : newnode가 가리키는 데이터 필드에 item 값을 삽입한다.
2. newnode.link ← top : newnode.link에 top이 갖고있는 내용 값을 전달한다.
3. top ← newnode : 새로운 node의 주소값을 삽입한다.

연결 자료구조에서의 삭제 연산

1
2
3
4
5
6
7
8
9
10

pop(s)
	if(top = null) then
		return null;
	else {
			item ← top.data;
			top = top.link;
			returnnode(oldnode);
			return item;
		 }
end pop()

1. if(top = null) then return null : top이 null 값을 갖고 있다면 null을 반환하고 삭제연산을 수행하지 않는다.
2. Item ← top.data: top이 갖고있는 데이터 값을 item에게 전달한다.
3. oldnode ← top : top의 주소를 oldnode에게 전달한다.
4. top ← top.link : top이 가리키고 있는 링크 값을 top에게 전달한다.
5. returnnode(oldnode) : oldnode를 자유공간으로 노드반환한다.
6. return item : top의 데이터를 가진 item을 반환한다.