[자료 구조] 스택(Stack)

스택(Stack)

---

1. 스택(Stack)

• 스택은 자료 구조에 들어있는 요소 중에서 마지막에 삽입한 요소를 꺼
  • push는 요소를 스택에 삽입
  • pop은 요소를 스택에서 마지막에 삽입한 요소를 꺼냄
• 먼저 들어간 것이 마지막에 나오는 규칙을 LIFO(list-in first-out)라고 함

 

2. 스택(Stack) 구현

2.1 스택(Stack) Interface

package com.beyond.palindromes.structure;

public interface Stack<T> {
	
    // 스택에 노드 추가
	void push(T value);
	
    // 스택의 size 반환
	int size();
	
    // 스택이 비어있는지에 대해 true/false 반환
	boolean isEmpty();

	// 스택의 마지막 노드 값 출력 후 제거
	T pop();

	// 스택에 입력받은 값이 존재하는지 true/false 반환
	boolean contains(String string);

	// 스택의 마지막 노드 값 반환
	T peek();

}

 

2.2 스택(Stack)의 메소드 구현

2.2.1 스택의 Node

	// 스택의 Node
    private static class Node<T>{
		private T data;
		private Node<T> next;
		
		public Node(T data) {
			this.data = data;
			this.next = null;
		}
	}

---

2.2.2 push() 메소드

	// 스택에 node를 추가하는 메소드
    @Override
	public void push(T value) {
		Node<T> newNode = new Node<>(value);
		
		newNode.next = top;
		top = newNode;
		
		size++;
	}

---

2.2.3 size() 메소드

	// 스택의 size를 반환하는 메소드
    @Override
	public int size() {
		return this.size;
	}

---

2.2.4 isEmpty() 메소드

	// 스택이 비어있다면 true, 비어있지 않다면 false를 반환하는 메소드
    @Override
	public boolean isEmpty() {
		return top==null;
	}

---

2.2.5 pop() 메소드

	// 스택의 마지막 Node의 값을 반환하고 Node를 삭제하는 메소드
    @Override
	public T pop() {
		if(isEmpty()) {
			throw new RuntimeException("스택이 비어있습니다.");
		}
		
		T value = top.data;
		
		top = top.next;
		
		size --;
		
		return value;
	}

---

2.2.6. contains 메소드

	//입력받은 값이 스택에 존재한다면 true, 존재하지 않는다면 false를 반환하는 메소드
    @Override
	public boolean contains(String string) {
		Node<T> current = top;
		
		while(current != null) {
			if(current.data.equals(string)) {
				return true;
			}
			
			current = current.next;
		}
	
		return false;
	}

---

2.2.7. peek() 메소드

	// 스택의 마지막 노드의 값을 반환하는 메소드
    @Override
	public T peek() {
		if(isEmpty()) {
			throw new RuntimeException("스택이 비어있습니다.");
		}
		return top.data;
	}

---

2.2.8. toString() 메소드

	// 스택에 존재하는 모든 Node의 값을 출력하는 메소드
	@Override
	public String toString() {
		Node<T> current = top;
		StringBuilder sb = new StringBuilder();
		
		sb.append("[");
		
		while(current != null) {
			sb.append(current.data + ", ");
			
			current = current.next;
		}
		
		if (sb.lastIndexOf(",") != -1) {
			sb.replace(sb.lastIndexOf(","), sb.length(), "]");			
		} else {
			sb.append("]");		
		}

		return sb.toString();
	}

 

3. 스택(Stack) 테스트

3.1 size() & isEmpty()  테스트

// 스택 생성 후, size()메소드와 isEmpty()메소드 테스트
Stack<String> stack = new LinkedListStack<>();
		
System.out.println(stack);			// toString()을 재정의 하여 스택의 모든 Node의 값을 출력
System.out.println(stack.size());
System.out.println(stack.isEmpty());

3.2 peek()  테스트

// push() 테스트
stack.push("딸기");
stack.push("포도");
stack.push("바나나");
		
System.out.println(stack);
System.out.println(stack.size());		// 스택에 3개의 Node를 삽입하였으므로 3을 반환
System.out.println(stack.isEmpty());		// 스택에 Node를 삽입하였으므로 false
System.out.println();

3.3 pop()  테스트

// pop() 테스트
System.out.println(stack.pop());	// stack은 LIFO이므로 "바나나"를 반환하고 노드를 삭제
		
System.out.println(stack);
System.out.println(stack.size());
System.out.println(stack.isEmpty());

3.4 contains()  테스트

// contains()메소드 테스트
System.out.println(stack);
System.out.println(stack.contains("딸기"));
System.out.println(stack.contains("바나나"));

3.5 peek() 테스트

// peek() 메소드 테스트
System.out.println(stack.peek());

System.out.println(stack.size());		// peek()는 값만 반환하고 삭제하지 않으므로 size는 그대로
System.out.println(stack.isEmpty());
System.out.println();