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

Stack 자료구조에서 연결리스트를 사용한 삽입&삭제 알고리즘

• 순차 자료구조방식의 스택은 구현하기는 쉽다. 하지만 크기가 고정된 배열을 이용하기 때문에 메모리의 낭비가 쉽다. 이 문제점을 연결 자료구조 방식을 이용함으로써 해결할 수 있다.
• 스택의 원소는 단순 연결 리스트의 노드가 된다.
• 스택 원소의 순서는 연결 리스트 노드의 링크를 사용하여 표현한다.
• 스택에 원소를 삽입할 때마다 연결 리스트에 노드를 하나씩 연결한다.
• 스택의 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을 반환한다.

Stack

• 스택(Stack)은 자료를 한쪽으로 보관하고 꺼내는 후입선출 (Last In First Out) 방식의 자료구조이다. 스택에 자료를 보관하는 연산은 Push라고 하고, 자료를 꺼내는 연산을 Pop이라고 한다. 그리고 가장 최근에 보관한 위 치 정보를 Top 또는 스택 포인터라고 말한다.

Node

• A : 데이터
• B : 다음 노드의 위치 정보(링크)

Push

• 스택에 새로운 데이터를 삽입하는 작업을 Push라고 하며, 리스트의 마지막에 node를 삽입한다.
• 배열에서는 크기가 정해져 있기때문에 크기 이상의 데이터가 push 되면 stack overflow가 발생하지만, 연결리 스트에서는 동적으로 할당되기때문에 메모리가 고갈될 때까지 push를 할 수 있다.

Pop

• 스택의 맨 위에 위치한 값(가장 최근에 들어간 값)을 반환하면서 스택에서 제거한다.