[JAVA] Stack - Linked List로 구현(스택/링크리트리스트)

[전체 코드]

public class LinkedListStack {
	private Node head;
	private Node top;
	
	private class Node{
		private Object data;
		private Node next;
		
		Node(Object data){
			this.data = data;
		}
	}
	
	public void push(Object data) {
		if(head == null) {
			head = new Node(data);
			top = head;
			return;
		}
		
		Node node = new Node(data);
		top.next = node;
		System.out.println("push, top.next "+top.next);
		top = node;
		System.out.println("push, top "+top);
	}
	
	public Object pop() {
		if(top==null) {
			throw new ArrayIndexOutOfBoundsException();
		}
		Node temp = head;
		Object data = this.peek();
		if(temp.next == null) {
			head = null;
			top = null;
			return data;		
		}
		
		while(temp.next!=null) {
			top = temp;
			System.out.println("pop - top(temp): "+top); //설명을 위한 코드
			temp = temp.next;
			System.out.println("pop - temp(temp.next): "+temp); //설명을 위한 코드
		}
		
		top.next = null;
		return data;
	}
	
	public Object peek() {
		return top.data;
	}
	
	public boolean empty() {
		return top == null;
	}
	
	public int size() {
		int count = 1;
		
		Node temp = head;
		
		while(temp.next!=null) {
			++count;
			temp = temp.next;
		}
			
		return count;
	}
}

 

[입력 코드]

public class test1 {
	
	public static void main(String[] args) {
		LinkedListStack stack = new LinkedListStack();
		stack.push("가");
		System.out.println("size"+stack.size());
		stack.push("나");
		System.out.println("size"+stack.size());
		stack.push("다");
		System.out.println("size"+stack.size());
		System.out.println(stack.pop());
		System.out.println(stack.pop());
		System.out.println(stack.pop());
		System.out.println(stack.empty());
	}
}

 

[결과]

size1
push, top.next LinkedListStack$Node@5305068a  //나
push, top LinkedListStack$Node@5305068a  //나
size2
push, top.next LinkedListStack$Node@1f32e575  //다
push, top LinkedListStack$Node@1f32e575  //다
size3
pop - top(temp): LinkedListStack$Node@279f2327  //가
pop - temp(temp.next): LinkedListStack$Node@5305068a  //나
pop - top(temp): LinkedListStack$Node@5305068a  //나
pop - temp(temp.next): LinkedListStack$Node@1f32e575  //다
다
pop - top(temp): LinkedListStack$Node@279f2327  //가
pop - temp(temp.next): LinkedListStack$Node@5305068a  //나
나
가
true

 

<입력 코드와 결과값 설명>

 

1. stack.push("가");

if(head == null) {
	head = new Node(data);
	top = head;
	return;
}

Stack에 push한 것이 없어서 현재 head가 null이기 때문에 Push의 if구문에 해당 “가”가 top, head가 됨.

 

 

2. stack.size()

public int size() {
	int count = 1;
		
	Node temp = head;
		
    while(temp.next!=null) {
		++count;
		temp = temp.next;
	}
			
	return count;
}

head에는 "가"가 있고, temp는 head이기 때문에 temp.next 는 null이 되어 count는 1이 됨.

 

3. stack.push("나"); + stack.size(); ("다"는 동일)

3-1 push

Node node = new Node(data);
top.next = node;
System.out.println("push, top.next "+top.next);
top = node;
System.out.println("push, top "+top);

push의 if구문 (head == null)에 해당 하지 않아서 다음 코드로 넘어옴.

top과 top.next에 "나" (주소) 저장. ( top.next/top == LinkedListStack$Node@5305068a)

 

3-2 stack.size

public int size() {
	int count = 1;
		
	Node temp = head;
		
	while(temp.next!=null) {
		++count;
		temp = temp.next;
    }	
	return count;
}

temp는 "가"(head)에 해당하여 while문의 temp.next가 존재함.

temp.next가 있는 만큼 반복(++count). → "나"의 경우 한 번 반복하여 count == 2가 됨.

 

4. stack.pop()

public Object pop() {
	if(top==null) {
		throw new ArrayIndexOutOfBoundsException();
	}
	Node temp = head;
	Object data = this.peek();
	if(temp.next == null) {
		head = null;
		top = null;
		return data;		
	}
		
	while(temp.next!=null) {
		top = temp;
		System.out.println("pop - top(temp): "+top);
		temp = temp.next;
		System.out.println("pop - temp(temp.next): "+temp);
	}
		
	top.next = null;
	return data;
}
	
public Object peek() {
	return top.data;
}

4-1 첫 번째 pop

pop - top(temp): LinkedListStack$Node@279f2327  //가
pop - temp(temp.next): LinkedListStack$Node@5305068a  //나
pop - top(temp): LinkedListStack$Node@5305068a  //나
pop - temp(temp.next): LinkedListStack$Node@1f32e575  //다
다

temp는 head인 "가"의 값(주소)을 가지고 있고 data는 top.data인 "다"의 값을 가지고 있음.temp.next(head)가 != null로 while 구문에 들어감.

 

4-1-1 첫 번째 결과값 ( pop - top(temp): LinkedListStack$Node@279f2327  //가 )

top("다") = temp(head =="가")

 

4-1-2 두 번째 결과값 (pop - temp(temp.next): LinkedListStack$Node@5305068a  //나)

temp("가") = temp.next(head의 next인 "나")

 

4-1-3 세 번째 결과값 (pop - top(temp): LinkedListStack$Node@5305068a  //나)

top("가") = temp("나"→ 4-1-2)

 

4-1-4 네 번째 결과값 (pop - temp(temp.next): LinkedListStack$Node@1f32e575  //다)

temp("나") = temp.next("다")next가 없기 때문에 while구문 빠져나옴.

 

4-1-5 다섯 번째 결과값 (다)top.next("다") = null return data("다") 

 

 

 

4-2 두 번째 pop

pop - top(temp): LinkedListStack$Node@279f2327  //가
pop - temp(temp.next): LinkedListStack$Node@5305068a  //나
나

temp는 head인 "가"의 값(주소)을 가지고 있고 data는 top.data인 "나"의 값을 가지고 있음.

temp.next(head)가 != null로 while 구문에 들어감.

 

4-2-1 첫 번째  결과값 (pop - top(temp): LinkedListStack$Node@279f2327  //가)

top("나") = temp("가")

 

4-2-2 두 번째 결과값 (pop - temp(temp.next): LinkedListStack$Node@5305068a  //나)

temp("가") = temp.next("나")

"나"의 다음이 없기 때문에  while 구문 빠져나옴.

 

4-2-3 세 번째 결과값 (나)

top.next("나") = null

return data("나")

 

4-3 세 번째 pop

data는 "가"가 됨

if(temp.next == null) {
	head = null;
	top = null;
	return data;		
}

 

"가" 다음이 없기 때문에 if 구문에 해당되어 모두 null 이 됨.

retrun data("가")

 

4-4 empty()

retrun top == null(4-3에서 top이 null이 됨) → true