[자료구조] 연결 리스트를 이용하여 스택(Stack) 구현

순차 자료구조를 이용한 스택은 배열을 사용하여 구현하기 쉽지만, 물리적으로 크기가 고정된 배열을 사용하기 때문에 스택의 크기를 변경하기가 어렵고 메모리의 낭비가 생길 수 있다는 문제점이 있습니다. 이러한 순차 자료구조 방식의 문제는 연결 자료구조 방식을 이용함으로써 해결할 수 있습니다.

 

스택에 대한 단순 연결 리스트 표현

1. 연결 리스트로 구현하는 스택 알고리즘

· 삽입 연산(push)

push(lS, x)
    new ← getNode();
    new.data ← x;
    new.link ← top;		// ①
    top ← new;			// ②
end push()

① 새로 삽입할 new 노드의 link에 top을 저장하여 이전 노드를 참조하게 합니다.

 

② top은 새로 삽입된 new 노드를 참조하게 합니다.

· 삭제 연산(pop)

pop(S)
    if(top = null) then empty();
    else{
        item ← top.data;
        top ← top.link;
        return item;
    }
end pop()

top이 이전 노드를 가리키도록 top에 top.link를 대입한 뒤 값을 반환합니다.

2. 스택 구현

· Stack

public interface Stack {
	boolean isEmpty();
	void push(char item);
	char pop();
	char peek();
	void delete();
}

 

· StackNode

public class StackNode {
	private char data;
	public StackNode link;

	public StackNode(char data) {
		this.data = data;
		this.link = null;
	}

	public char getData() {
		return this.data;
	}
}

 

· LinkedStack

public class LinkedStack implements Stack {
	private StackNode top;

	// 스택 초기화
	public LinkedStack() {
		top = null;
	}

	@Override
	public boolean isEmpty() {
		return (top == null); // top이 null이면 공백상태
	}

	@Override
	public void push(char data) {
		StackNode newNode = new StackNode(data);
		newNode.link = top; // 새로 삽입된 노드가 이전 노드를 참조
		top = newNode;
	}

	@Override
	public char pop() {
		if (isEmpty()) {
			System.out.println("스택이 공백상태입니다.\n");
			return 0;
		} else {
			char data = top.getData();
			top = top.link; // top이 이전 노드를 참조
			return data;
		}
	}

	@Override
	public char peek() {
		if (isEmpty()) {
			System.out.println("스택이 공백상태입니다.\n");
			return 0;
		} else {
			return top.getData(); // top이 가리키는 데이터 반환
		}
	}

	@Override
	public void delete() {
		if (isEmpty()) {
			System.out.println("스택이 공백상태입니다.\n");
		} else {
			top = top.link; // top이 이전 노드를 참조
		}
	}

	// 스택 출력
	public void printStack() {
		if (isEmpty()) {
			System.out.println("스택이 공백상태입니다.\n");
		} else {
			StackNode temp = top;
			while (temp != null) {
				System.out.printf("\t%c\t\n", temp.getData());
				temp = temp.link;
			}
			System.out.println();
		}
	}
}

 

· MainForLinkedStack

public class MainForLinkedStack {
	public static void main(String[] args) {
		LinkedStack s = new LinkedStack();
		char data = 0;

		System.out.println("1. 스택에 원소 3개 삽입");
		for (char c = 'A'; c <= 'C'; c++) {
			s.push(c);
		}
		s.printStack();

		System.out.println("2. top이 가리키고 있는 원소 알아내기");
		data = s.peek();
		System.out.printf("\t%c\n\n", data);

		System.out.println("3. 스택의 원소 2개 팝");
		for (int i = 0; i < 2; i++) {
			data = s.pop();
			System.out.printf("삭제된 원소 : %c\n", data);
			s.printStack();
		}

		System.out.println("4. 스택의 원소 삭제");
		s.delete();
		s.printStack();
	}
}

 

· 실행 결과