[JAVA] 스택

스택이란

• 선입후출
• 먼저 들어온게 나중에 나온다.
• 들어오는 입구와 나가는 입구가 같은 구조
• Stack은 데이터를 쌓는 형식으로 저장하는데 따라서 조회, 추가, 삭제 모두 가장 위에 있는 즉 가장 최근의 값에서 이루어 진다. 스택 구조에서 가장 상단에 있는 데이터를 Top이라고 한다.

JAVA 스택 클래스

1) 스택의 생성

Stack<DataType> Stack_name = new Stack<>();

2) 스택 클래스

public Element push(Element item); // 데이터 추가
public Element pop(); // 최근에 추가된(Top) 데이터 삭제
public Element peek(); // 최근에 추가된(Top) 데이터 조회
public boolean empty(); // stack의 값이 비었는지 확인, 비었으면 true, 아니면 false
public int seach(Object o); // 인자값으로 받은 데이터의 위치 반환

사용자 구현 스택

1) 배열로 구현 하였을 때

장점

• 구현이 쉽고 데이터의 접근 속도(조회)가 빠르다.

단점

• 배열로 구현하기 때문에 항상 최대 개수를 정해놓아야한다.

---

2) 연결리스트(Linked List)로 구현하였을 때

장점

• 데이터의 개수를 동적으로 할당이 가능하다.
• 삽입 삭제가 용이하다.

단점

• 배열과 달리 데이터의 조회가 힘들다
  노드를 따라가며 조회를 해야하기 때문이다.

---

[BOJ 1935] Stack으로 구현하는 후위 표기식

후위 표기식을 스택으로 구현하자면, 아래의 식이 있을때
ex) ABC*+DE/-

1. 스택에 순서대로 push() 시킨다.
2. 연산자를 만났을때 상위 노드 2개를 pop()시킨다.

	if(input_result[i]>=65&&input_result[i]<=90) 
    		{
				st.push(number[input_result[i]-65]);
			}
			else {
				double num1 = st.pop();
				double num2 = st.pop();
				double result_tmp =0 ;                
			switch(input_result[i]) {
				case 42 :
					result_tmp = num2*num1;
					break;
				case 43 :
					result_tmp = num2+num1;
					break;
				case 47:
					result_tmp = num2/num1;
					break;					
				case 45:
					result_tmp = num2-num1;
					break;
				}