[DS] Stack

Stack

한 쪽에서만 자료를 넣고 빼는 LIFO(Last in First Out) 자료구조

• Array 와 달리 i번째 자료에 O(1)(상수시간)으로 접근 할 수 없음
• 하지만 데이터 추가와 삭제는 O(1)(상수시간)으로 수행 할 수 있음
• Array 처럼 원소들을 하나씩 shift해줄 필요없음

스택을 활용하는 것이 좋은 구현인 경우

• 재귀(Recursion) 알고리즘
• 웹 브라우저의 방문 기록 (뒤로가기)
• 실행 취소(undo)
• 역순 문자열
• 후위 표기법(연산자가 문자뒤에 오는 표기법) 계산
• 수식의 괄호 검사

Stack의 Operation (ADT)

public interface ADT_Stack <T> {
	
	public boolean push (T newEntry); //새로운 요소 넣음 
	
	public T pop (); //맨 위에 있는 요소 꺼내고 무엇인지 확인 
	
	public T peek (); //맨 위에 있는 요소가 무엇인지 확인만 
	
	public boolean isEmpty (); //비어있는지 확인
	
	public void clear(); // 안에있는 모든 요소 꺼냄
	
}

LinkedList로 구현한 Stack 예시

public class Stack_Linked <T> {
	
	Node <T> topNode = new Node <T> (null);
	
	public void push(T newEntry) {
		
		Node <T> newNode = new Node <T> (newEntry, topNode);
		topNode = newNode;
		
	}
	
	public T pop() {
		
		T top = peak();
		if (topNode != null) {
			topNode = topNode.next;
		}
		return top;
		
	}
	
	public T peak() {
		
		T top = null;
		if (topNode != null) {
			top = topNode.data;
		}
		return top;
	}
	
}


class Node <T> {
	public T data; //entry
	public Node next; // link to next node
	
	public Node (T dataPortion) {
		this (dataPortion, null);
	}
	public Node (T dataPortion, Node nextNode) {
		data = dataPortion;
		next = nextNode;
	}
}

Reference

Carrano-Data Structures and Abstractions with Java 3rd Edition

https://yoongrammer.tistory.com/45