[JAVA] 스택 Stack

 

스택이란

1. 선입후출(FILO)
2. 먼저 들어온게 나중에 나온다.
3. 들어오는 입구와 나가는 입구가 같은 구조
4. 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)로 구현하였을 때

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

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

​

---

[예시]

[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;
				}