Stack -1

Stack

• 물건을 쌓아 올리듯, 자료를 쌓아 올리는 형태의 자료구조이다.
• 스택에 저장된 자료는 선형 구조를 갖는다.
  • 선형 구조 : 자료 간의 관계가 1대 1의 관계를 갖는다.
  • 비선형 구조 : 자료 간의 관계가 1대 N의 관계를 갖는다. (예: 트리)
• 자료를 삽입하거나 꺼내는 용도로 사용한다. (LIFO)
• 담아 놓을 수 있는 저장 장소를 스택이라 부르기도 한다.
• 들어간 순서에 반대, 즉 마지막 원소가 가장 중요하다.
• 이는 추상화가 잘 되어서 필요한 데이터에만 접근 가능하게 할 수 있다. 또한, 마지막 원소 외에는 접근할 수 없게 캡슐화한 것이라 볼 수 있다.

• 삽입 : push
• 삭제 : pop
• 공백 여부 : isEmpty
• 반환(내용을 확인만) : peek

public class Stack_스택의구현 {
	public static void main(String[] args) {
		Stack<String> stack = new Stack<>();
		
		stack.push("A");
		stack.push("B");
		stack.push("C");
		
		
		int size = stack.size();
		
		
		// 변수가 아닌 .size()로 하게 되는 경우, 
		// pop이 될 때마다 사이즈가 변경되어서 결과값이 잘못 나올 수도 있다. 
		for(int i = 0; i < size; i++) {
			System.out.println(stack.pop());
		}

	}
}

• 구현은 용이하지만, 스택의 크기를 변경하기가 어렵다는 단점이 있다.
• 동적 구현도 가능하다.

• 스택 응용 문제1 : 괄호 검사
  조건
  1. 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야 한다.
  2. 같은 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 한다.
  3. 괄호 사이에는 포함 관계만 존재한다. (하나의 괄호 사이에는 완전한 괄호만 있어야 한다.)

Function call

• 가장 마지막에 호출된 함수가 가장 먼저 실행을 완료하고 복귀하는 후입 선출 구조이므로, 후입 선출 구조의 스택을 이용하여 수행순서 관리
• 함수 호출이 발생하면, 호출한 함수 수행에 필요한 지역변수, 매개변수 및 수행 후 복귀한 주소 등의 정보를 스택 프레임에 저장하여 시스템 스택에 삽입
• 함수의 실행이 끝나면 시스템 스택의 top원소를 삭제(pop) 하면서 프레임에 저장되어 있던 복귀 주소를 확인하고 복귀
• 함수 호출과 복귀에 따라 이 과정을 반복하여, 전체 프로그램 수행이 종료되면 시스템 스택은 공백 스택이 된다.

public class function_call {
	public static void main(String[] args) {
		System.out.println("main 호출");
		func1();
		System.out.println("main 종료");
	}

	public static void func1() {
		System.out.println("func1 호출");
		func2();
		System.out.println("func1 종료");
	}
	public static void func2() {
		System.out.println("func2 호출");
		func3();
		System.out.println("func2 종료");
	}
	public static void func3() {
		System.out.println("func3 호출");
		System.out.println("func3 종료");
	}
}

main 호출
func1 호출
func2 호출
func3 호출
func3 종료
func2 종료
func1 종료
main 종료