Stack이란?

정의

과자로 생각하면 프링글스로 생각하면 되는데 가장 나중에 넣은 칩 조각을 가장 먼저 먹게 되는 것.

• 스택이란 한쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 후입선출 형식의 자료구조
• 자바에서 Stack은 java.util.Stack을 import 하면 바로 사용할 수 있다.
• 예를 들어 (A, B, C, D) 순서로 입력하면 꺼낼 땐 (D, C, B, A)처럼 역순으로 처리된다.
• 깊이 우선 탐색(DFS)에 이용된다.
• 재귀 함수의 동작 흐름과 같은 구조를 가진다.

가장 많이 사용되는 곳은

1. 웹 브라우저 방문기록(뒤로 가기)
2. 실행 취소

• RootViewController : 내비게이션 스택의 가장 하단 부분에 있는 뷰 컨트롤러.(즉, 가장 먼저 Push 된 뷰 컨트롤러)
• TopViewController : 내비게이션 스택의 가장 상위에 있는 뷰 컨트롤러(가장 마지막에 Push 된 뷰 컨트롤러.)

---

주요 메서드

메서드	설명
stack.push(1);	스택에 값 1 추가 성공시 return data
stack.size();	스택의 크기 출력
stack.empty();	스택이 비어 있으면 true, 비어 있지 않으면 false를 반환 Stack 클래스에만 정의
stack.peek();	스택의 제일 상단에 있는(마지막으로 저장된) 요소를 반환 성공시 return Data 만약 Stack이 비어있을 경우 throw EmptyStackException
stack.pop();	스택의 제일 상단에 있는(마지막으로 저장된) 요소를 반환후, 해당 요소를 스택에서 제거함. (값을 remove 할때 pop 을 사용하면된다.) 비어있을 경우 throw EmptyStackException
stack.search(1);	스택에서 전달된 객체가 존재하는 위치의 인덱스를 반환 이때 인덱스는 제일 상단에 있는(마지막으로 저장된) 요소의 위치부터 0이 아닌 1부터 시작함. 값이 없으면 -1 반환
stack.contains(1);	스택에 1이 있으면 true, 없으면 false 를 반환
stack.add(1)	스택에 값 1 추가 push와 다르게 add는 true/false를 반환
stack.clear()	스택안에 모든 값 제거
stack.isEmpty()	스택이 비어있으면 true, 비어있지 않으면 false를 반환 Collection인터페이스에 정의

---

Stack 사용

선언

Stack<Integer> stackInt = new Stack<>(); // Integer Stack선언, 뒤의 타입 생략 가능
Stack<String> stackStr = new Stack<>(); // String Stack선언  
Stack<Boolean> stackBool = new Stack<>(); // Boolean Stack선언

push()

// 값 추가 push()stackInt.push(1);  
stackInt.push(2);  
stackInt.push(3);  
System.out.println(stackInt);  
// 1 -> 3 순으로 추가

peek()

• 스택의 마지막 요소를 반환하며, 스택에는 변화를 주지 않는다.
• 즉 가장 먼저 사용될 요소를 반환한다.
• 스택이 비어있을 때 사용하면 NoSuchElementException예외 발생

System.out.println(stackInt.peek());

pop()

• 마지막 요소를 제거함과 동시에 해당 값을 반환.

System.out.println(stackInt.pop());  
System.out.println(stackInt);

add()

// 값 추가 add()stackInt.add(1);  
stackInt.add(2);  
stackInt.add(3);  
// 1- > 3 순으로 추가

clear()

stackInt.clear();

empty()

• 스택이 비어있는지 여부를 반환한다.
• 비어있으면 true 아닐 경우 false반환

System.out.println(stackInt.empty());  
stackInt.push(1);  
System.out.println(stackInt.empty());  
stackInt.clear();

search()

• 메서드의 인자를 스택에서 검색하여 해당 위치를 반환한다.
• 여기서 위치는 인덱스가 아니라 빠져나오는 순서를 뜻한다.
• 또한 값이 없을 경우 -1을 반환한다.

stackInt.push(1);  
stackInt.push(2);  
stackInt.push(3);  
stackInt.push(4);  
// [1, 2, 3, 4]  
  
System.out.println(stackInt.search(2));  
System.out.println(stackInt.search(4));  
System.out.println(stackInt.search(1));

---

Stack 예제

코드

Stack<Integer> stk = new Stack<Integer>();  
int tmp = 0;  
  
for (int i = 1 ; i <= 5 ; i++){  
    stk.push(i);  
}  
System.out.println("stk = " + stk);
  
for (int i = 1 ; i <= 5 ; i++){  
    tmp = stk.peek(); 
    System.out.println("stk.pop = " + stk.pop()); // 첫 번째 값 삭제 및 출력
}  

• queue는 첫 번째 값이 입력된 지 가장 오래된 것이라 12345가 출력되지만.
• stack은 마지막에 들어온 데이터부터 출력되기에 55555가 출력된다.

for (int i = 1 ; i <= 5 ; i++){  
    stk.push(i);  
}  
System.out.println("stk = " + stk);  
 
stk.push(stk.pop());  
System.out.println("stk = " + stk);

• 바로 위 반복문은 삭제를 했지만 그보다 위 반복문은 삭제를 진행하지 않아
• [1, 2, 3, 4, 5, 1, 2, 3, 4, 5] 출력
• 스택은 후입선출이기 때문에 최근에 추가된 값이 가장 먼저 삭제된다.
• 그렇기에 Queue에서 실행했던 첫 번째 값을 삭제하며 동시에 값 추가 (= 앞의 값을 가장 뒤로)와는 동작방식에 맞지 않는다
• 스택의 크기는 변하지 않고, 순서도 변경되지 않는다.
• 그래서 결과가 [1, 2, 3, 4, 5, 1, 2, 3, 4, 5]와 같이 동일한 값이 반복되는 것.

결과

stk = [1, 2, 3, 4, 5]
stk.pop = 5
stk.pop = 5
stk.pop = 5
stk.pop = 5
stk.pop = 5
---------------------------------------
stk = [1, 2, 3, 4, 5, 1, 2, 3, 4, 5]
stk = [1, 2, 3, 4, 5, 1, 2, 3, 4, 5]

참고 : https://yunamom.tistory.com/232