Stack

• 선형구조를 갖는다.
  • 선형 구조 : 자료 간의 관계가 1대1의 관계를 갖는다.
  • 비선형 구조 : 자료 간의 관계가 1대N의 관계를 갖는다.(예 : 트리)
• 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조이다.
• 스택에 자료를 삽입하거나 스택에 자료를 꺼낼 수 있다.(위에서만 삽입하고 꺼낸다.)
• 마지막에 삽입한 자료를 가장 먼저 꺼낸다. 후입선출이라고 부른다.
  • ex) 스택에 1,2,3 순으로 자료를 삽입한 후 꺼내면 역순으로 즉 3,2,1순으로 꺼낼 수 있다.
• 스택에서 마지막 삽입된 원소의 위치를 top이라고 부른다.
• 처음 top은 -1로 초기화
• top=-1 ->스택이 비어있음
• top=0~n-1 ->스택이 차 있음
• top=n-1->스택이 꽉 참

연산

• 삽입 : 저장소에 자료를 저장한다. 보통 push라고 부른다. push->top++
• 삭제 : 저장소에서 자료를 꺼낸다. 꺼낸 자료는 삽입한 자료의 역순으로 꺼낸다. 보통 pop이라고 부른다. pop->top--
• 스택의 top에 있는 item(원소)를 반환하는 연산 peek
• 스택이 공백인지 아닌지를 확인하는 연산 .inEmpty

배열을 이용한 스택 구현

package test01;

public class Test1 {
	static int[] arr=new int[10];
	static int top=-1;
	
	public static void main(String[] args) {
		push(1);
		push(2);
		push(3);
		print();
        System.out.println();
		while (!isEmpty()) {
			System.out.println(pop());
			
		}
	}
	
	//스택(배열)이 비어있는지
	static boolean isEmpty() {
		return top==-1;
	}
	
	//스택이 가득 차있는지
	static boolean isFull() {
		return top==arr.length-1;
	}
	
	static void push(int x) {
		if (top==arr.length-1) {//스택이 가득 차있다면
			System.out.println("stack overflow");
		}
		else {
			top++;
			arr[top]=x;//먼저 top을 증가시킨 후 인덱스를 사용
		}
	}
	
	static int pop() {
		if (top==-1) {//스택이 비어있다면
			System.out.println("stack is empty");
			return -1;
		}
		else {
			return arr[top--];//먼저 인덱스를 사용한 다음 top을 감소시킴
		}			
	}
	
	static void print() {
		for (int i = top; i>=0; i--) {
			System.out.println(arr[i]);
		}
	}
}
//
3 
2 
1 

3
2
1

Stack을 이용한 스택 구현

package test01;

import java.util.Stack;

public class test2 {
	public static void main(String[] args) {
		//Stack은 클래스로 구현이 되어있다.
		Stack<Integer> stack=new Stack<>();
		
		stack.push(1);
		stack.push(2);
		stack.push(3);
		
		while (!stack.isEmpty()) {
			System.out.println(stack.pop());			
		}
	}
}
//
3
2
1

• push : Stack 값 추가
• pop : Stack 값 삭제
• Peek : Stack의 가장 상단의 값 출력
• size() : Stack의 크기 출력
• empty : stack이 비어있는지 확인(비어있다면 true)
• contains(1) : stack에 1이 있는지 check(있다면 true)

프로그램에서의 함수 호출과 복귀에 따른 수행 순서

package test02;

public class Test2_FunctionCall {
	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 작업 끝");
	}
}
//
메인 작업 수행
함수 1 작업 수행
함수 2 작업 수행
함수 2 작업 끝
함수 1 작업 끝
메인 작업 끝

현재 작업에 대해 실행 취소 / 실행 취소의 취소 같은 작업

package test02;
import java.util.Scanner;
import java.util.Stack;

public class Test3_실행취소 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		Stack<String> ctrlZ = new Stack<String>();
		Stack<String> ctrlY = new Stack<String>();

		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) {
				ctrlZ.add(work); // 이전 작업 스택에 현재 작업 넣기
				work = sc.next(); // 새로운 작업 입력받고
				ctrlY.clear(); // 이후 작업 스택 비우기
				System.out.println(work); // 현재 작업 출력
			} else if (N == 2) {
				if (ctrlZ.isEmpty()) {
					System.out.println("가장 첫 작업이다.");
				} else {
					ctrlY.add(work); // 현재작업을 Y에 추가
					work = ctrlZ.pop(); // 현재작업을 이전 작업스택에서 꺼내서 넣기
					System.out.println(work); // 바뀐작업 추가
				}

			} else if (N == 3) {
				if (ctrlY.isEmpty()) {
					System.out.println("가장 마지막 작업이다.");
				} else {
					ctrlZ.add(work); // 현재작업 이전 스택에 넣기
					work = ctrlY.pop(); // 이후 작업스택에서 꺼내서 넣기
					System.out.println(work); // 작업출력
				}

			} else {
				System.out.println("종료합니다.");
				break;
			}
		}
	}
}