자바_Stack

1. 스택(Stack)이란?

: 스택은 기본 자료구조 중 하나로, 줄을 지어 마지막으로 들어온 데이터가 가장 먼저 나오는 특징을 가지고 있다. 즉 LIFO(Last-In First-Out) 동작으로 이뤄진다.

 

2. 사용 방법

  1) 스택을 사용하는 방법은 간단하다. import를 이용하여 Stack을 불러온 다음 기본 정의에 맞게 코드를 짜면 된다.

 

다음은 해당 방법을 이용한 예제이다.

import java.util.Stack;

public class Main {

	public static void main(String[] args) {
		
		// sample이라는 스택 객체를 생성
		Stack<Integer> sample = new Stack();
		// push를 통해 넣고 싶은 값은 무조건 제일 위쪽에 추가!
		sample.push(10);
		sample.push(20);
		// sample 안에 값들을 출력
		for (Integer val : sample) {
			System.out.println(val.intValue());
		}
		
		System.out.println("--------------------");
		// 빼낼 때는 값을 반환해 주면서 배열에서 제거
		System.out.println("pop : " + sample.pop());
		// pop을 통해 맨 위의 값을 빼냄
		sample.pop();
		for (int val : sample) {
			System.out.println(val);
		}

 

   2) 두 번째로는 스택을 직접 구현하는 방식이다. 여러 방법이 있겠지만 이번 포스팅에서는 노드를 이용하여 만들어 보겠다.

 

[Node.java]

public class Node {
	// 빈번하게 접근하는 변수의 경우 public을 사용!!!
	// Function Call Overhead를 줄이기 위해서임
	// next와 url 변수는 비어있는 상태로 선언
	public Node next = null;
	private String url = "";
	
	public Node(String _url) {
		this.url = _url;
	}
	
	// 입력된 url에 해당하는 Getter 생성 및 반환
	public String getUrl() {return url;}
	
	// 현재 노드가 다음 노드를 가지고 있는지 검사하고 해당 next 변수를 반환
	public boolean hasNext() { return this.next != null; }
	// 노드 추가용 함수
	public void add(Node _node) { this.next = _node; }
	// 노드 제거용 함수
	public void removeNext() { this.next = null; }
	
	
	// 객체를 생성하고, 초기화 과정을 처리한 다음 반환해 주는 메소드
	public static Node create(String _url) {
		return new Node(_url);
	}
}

 

[MyStack.java]

public class MyStack {
	// 헤드가 무조건 있다는 조건 설정
	private Node head = new Node("HEAD");
	
	// 헤드 다음 노드가 비어있는지 확인
	public boolean isEmpty() { return head.next == null;}
	
	// 헤드부터 시작하여 제일 끝에까지 가서 새로운 애를 추가해 주는 기능
	public void push(String _url) {
		// 새로운 노드 생성
		// push 메소드를 재활용
		push(Node.create(_url));
	}
	
	// 새로운 노드를 마지막 노드에 추가
	public void push(Node _newNode) {
		getLastNode().add(_newNode);
	}
	
	// 맨 마지막 노드 빼내기
	public String pop() {
		// 헤드 다음 노드가 비어있다면 "EMPTY" 반환
		if (isEmpty()) return "EMPTY";
		
		// head라는 변수를 그냥 사용하면 나중에 기준점이 사라지므로 iterNode라는 임시 변수를
		// 따로 만들어서 걔가 링크드 리스트 주소를 따라가며 이동함
		Node iterNode = head;
		// 마지막 노드의 이전 노드 찾기
		// 현재 검사하는 노드의 다음 노드가 그 다음 노드를 가지고 있다면 이동
		while (iterNode.next.hasNext()) {
			iterNode = iterNode.next;
		}
		
		// 제거 되어야 할 노드는 현재 찾은 노드의 다음 노드
		Node delNode = iterNode.next;
		// 노드 제거 전에, 제거할 노드의 데이터를 임시 저장
		String returnValue = delNode.getUrl();
		// 노드 제거
		// iterNode.next = null;
		iterNode.removeNext();
		// 데이터 반환
		return returnValue;
	}
	
	// 마지막 노드 찾기
	public Node getLastNode() {
	
		// Iterator
		Node lastNode = head;
		// 내 다음이 null이면 나는 마지막 노드임
		while(lastNode.hasNext()) {
			// 내가 다음에 노드를 가지고 있으면 나를 다음 걸로 갱신시켜줌
			lastNode = lastNode.next;
		}
		return lastNode;
	}
	
	public void printAll() {
		// 데이터가 없다면 종료
		if (isEmpty()) return;
		// 헤드가 포함되면 안 되기 때문에 헤드 다음 노드부터 시작
		Node iterNode = this.head.next;
		int idx = 0;
		while (iterNode != null) {
			System.out.println(idx + ": " + iterNode.getUrl());
			++idx;
			iterNode = iterNode.next;
		}
	}
}

 

[Main.java]

public class Main {

	public static void main(String[] args) {
    
    	System.out.println("--------------------");
		MyStack stack = new MyStack();
		stack.push("naver.com");
		stack.push(Node.create("daum.net"));
		stack.push("Google.com");
		stack.printAll();
		
		System.out.println("--------------------------");
		
		System.out.println("pop: " + stack.pop());
		stack.printAll();
	}

}

결괏값

0: naver.com
1: daum.net
2: Google.com
--------------------------
pop: Google.com
0: naver.com
1: daum.net