⚡ Stack

📌 Stack이란?

🔷 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조

• 스택에 저장된 자료는 선형 구조를 갖는다.
  • 선형구조: 자료 간의 관계가 1:1
  • 비선형구조: 자료 간의 관계가 1:N
• 스택에 자료를 삽입하거나 스택에서 자료를 꺼낼 수 있다.
• 마지막에 삽입한 자료를 가장 먼저 꺼낸다. 후입선출(LIFO, Last-In-First-Out)

🔷 스택을 프로그램에서 구현하기 위해서 필요한 자료구조와 연산

• 자료구조: 자료를 선형으로 저장할 저장소
  - C언어에서는 배열을 사용 가능
  - 스택에서 마지막 삽입된 원소의 위치를 top이라 부른다.

  💡 저장소 자체를 스택이라 부르기도 한다.

• 연산

  1. 삽입: 저장소에 자료를 저장, push
  2. 삭제: 저장소에서 자료 꺼내기, 꺼낸 자료는 삽입한 자료의 역순이다. pop
  3. 스택이 공백인지 확인하기, isEmpty
  4. 스택의 top에 있는 item을 반환 peek

 public class dailyClass {
	public static int [] stack = new int[5];
	public static int top = -1;
	
	public static void main(String[] args) {
		System.out.println(isEmpty()); // true
		push(2);
		push(3);
		System.out.println(pop()); // 3
		System.out.println(peek()); // 2
		System.out.println(isEmpty()); // false
	}
	
	// 포화상태 체크
	public static boolean isFull() {
		return top == stack.length-1;
	}
	
	// 공백상태 체크
	public static boolean isEmpty() {
		return top == -1;
	}
	
	// 삽입
	public static void push(int value) {
		// 배열로 만든 스택이므로 작업 하나가 추가된다
		if(isFull()) {
			System.out.println("배열이 가득 참");
			return;
		}
		top++;
		stack[top] = value;	
	}
	
	// 삭제, top을 1 낮추기만 해도 상관없다.(어차피 top 변수가 다시 데이터를 덮는다)
	public static int pop() {
		if(isEmpty()) {
			System.out.println("스택이 비어있습니다.");
			return -1; // 자료가 음수일 수도 있기 때문에 -1 반환에 주의한다.
		}
		return stack[top--];
	}
	
	// top의 자료 확인
	public static int peek() {
		if(isEmpty()) {
			System.out.println("스택이 비어있습니다.");
			return -1; // 자료가 음수일 수도 있기 때문에 -1 반환에 주의한다.
		}
		return stack[top];
	}
}

📌 Stack 응용

⭐ Function call

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

public class Main {
	public static void main(String[] args) {
		System.out.println("메인함수 실행");
		func1();
		System.out.println("메인함수 종료");
	}
	
	public static void func1() {
		System.out.println("함수1 실행");
		func2();
		System.out.println("함수1 종료");
	}
	
	public static void func2() {
		System.out.println("함수2 실행");
		System.out.println("함수2 종료");
	}
}

⭐ 실행 취소와 실행 취소의 취소

• Ctrl + Z, Ctrl + Y 구현

import java.util.Scanner;
import java.util.Stack;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		Stack<String> ctrlZ = new Stack<>();
		Stack<String> ctrlY = new Stack<>();
		
		String work= "";
		while(true) {
			System.out.println("1. 새로운 작업");
			System.out.println("2. Ctrl + Z");
			System.out.println("3. Ctrl + Y");
			System.out.println("0. 종료");
			
			int N = sc.nextInt();
			
			if(N==1) {
				// 새 작업 넣기
				// 1. 현재 작업을 Z에 넣는다.
				// 2. 새로운 작업을 입력 받는다.
				// 3. Y를 비운다. (clear() 메서드 사용 혹은 새로운 스택 생성 혹은 pop() 반복)
				// 4. 현재 작업 출력
				ctrlZ.push(work);
				work = sc.next();
				ctrlY.clear();
				System.out.println(work);
			} else if(N==2) {
				// 실행 취소 (과거 작업이 있을 때만)
				// 1. 현재 작업을 Y에 넣는다
				// 2. Z에서 작업을 꺼내어 넣는다. (work에 대입)
				// 3. 현재 작업 출력
				if(ctrlZ.isEmpty()) {
					System.out.println("이전 작업이 없습니다.");
				} else {
					ctrlY.push(work);
					work = ctrlZ.pop();
					System.out.println(work);
				}
				
			} else if(N==3) {
				// 실행 취소를 취소 (선행 작업이 있을 때만)
				// 1. 현재 작업을 Z에 넣는다
				// 2. Y에서 작업을 꺼내어 넣는다. (work에 대입)
				// 3. 현재 작업 출력
				if(ctrlY.isEmpty()) {
					System.out.println("가장 최신 작업입니다.");
				} else {
					ctrlZ.push(work);
					work = ctrlY.pop();
					System.out.println(work);
				}
			} else {
				System.out.println("종료합니다.");
				break;
			}
		}
	}
}