스택
- 맨 마지막에 데이터를 쌓고 빼는 자료구조
스택의 원리
- 맨 위 원소를 스택 탑 원소라고 함
- push를 통해 새로운 원소를 집어넣어 새로운 스택 탑 원소가 되며
pop을 통해 스택 탑 원소를 삭제시킴
가상 메모리 구조
정적 영역
- 프로그램 수행 코드와 끝날 때까지 존재하는 데이터가 존재
동적 영역
- 프로그램 수행 중 할당 받는 힙과 완료되지 않은 함수가 다른 함수를 호출할 때
정보를 저장하는 스택 영역이 존재
배열 스택 객체 구조
stack[] : 스택의 원소들이 저장되는 배열
topIndex : 스택 탑 원소 자리의 인덱스
push() : 스택의 맨 위에 특정 원소 삽입
pop() : 스택의 맨 위에 있는 원소를 알려주고 삭제
top() : 스택의 맨 위에 있는 원소를 알려줌
isEmpty() : 스택이 비었는지 알려줌
popAll() : 스택을 청소
연결 리스트 스택 객체 구조
- 맨 끝 노드를 topNode로 지정
원소 삽입
스택 탑 원소가 있는 노드가 topNode였으나 새로운 원소를 추가함으로써 newNode가 topNode가 됨
원소 삭제
topNode에 있던 원소를 무조건 적으로 먼저 삭제시키므로 prevNode에 있던 원소가 있는 노드가 스택 탑이
됨가 동시 topNode가 됨
스택 응용
문자열 뒤집기
package stack;
public class ReverseString {
public static void main(String[] args) {
String input = "Test Seq 12345";
String t = reverse(input);
System.out.println("Input string: " + input);
System.out.println("Reversed string: " + t);
}
private static String reverse(String s) {
ArrayStack<Character> st = new ArrayStack<>(s.length());
for(int i = 0; i < s.length(); i++)
st.push(s.cahrAt(i));
String output = "";
while(!st.isEmpty())
output = output + st.pop();
return output;
}
}
입력 문자열이 끝날 때까지 push()를 통해서 스택을 차례로 저장한 후
스택이 빌때까지 pop()을 통해 하나씩 원소를 빼면서 출력 스트링 뒤에 붙여주는 원리
Postfix 계산
postfix는 후위 표현법인데
입력된 값이 숫자라면 push()를 통해 삽입
입력된 값이 연산자라면 맨 위에 있는 수 2개를 pop시킨 후 계산을 한 후 push로 삽입한다
예시
입력: 340 2 5 * 33 * - 2 /
2와 5를 *로 인해 곱하면 10
스택 [340, 10]
다음 33 입력
스택 [340, 10 ,33]
연산자 *삽입하면
위에있는 숫자 두개인 10과 33를 뺀후 곱해서 다시 삽입
스택 [340, 330]
연산자 -
스택 [10]
숫자 2 삽입
스택 [10 ,2]
연산자 / 삽입 하면
결과값 [5]