[Java 기본 알고리즘] (6) 큐&스택

package QueuenStackBasic;

import java.util.Stack;

public class QueuenStack1 {
	public static void main(String[] args) {
		String[] strs = { "5", "-2", "4", "C", "D", "9", "+", "+" };
		System.out.println("결과값 : "+points(strs));
	}
	// 야구 게임
	// 계산기 -> 점수 저장 및 빼기
	// C: 삭제, D : 최상단의 x2 (두배) 더하기, + : 앞의 두 숫자를 이용해 구해서 더한다.

	public static int points(String[] strs) {
		// 1. ds
		Stack<Integer> stack = new Stack<>();

		// 2. for, while
		for (String op : strs) {
			switch (op) {
			// +, C, D : operation로 만든다, 나머지는 스택에 넣으면 된다.
			case "C":
				stack.pop(); // 앞의 숫자 삭제
				break;
			case "D":
				stack.push(stack.peek() * 2);// 앞의 숫자를 빼서 두배로 만들어 더하기
				break;
			case "+": // 앞의 두 숫자를 이용해 구해서 더한다
				int x = stack.pop();// 9 //5
				int y = stack.pop();// -4//9
				// y->x->합 순서대로 다시 넣는 방법
				stack.push(y); // -4//9
				stack.push(x); // 9//5
				stack.push(x + y); // -4+9=5//9+5=14
				break;
			default:
				stack.push(Integer.valueOf(op)); // 문자열을 숫자로 캐스팅

			}
		}
		int sum = 0;
		while (!stack.isEmpty()) {
			sum += stack.pop();
		}
		return sum;
	}

}

 

package QueuenStackBasic;

import java.util.Stack;

public class QueuenStack2 {


	public static void main(String[] args) {
		String str= "()[]{}"  ;//true;
		//String str= "(}"  ;//false;
		//String exp = "([}}])"; //false;
		System.out.println(solve(str));
	}
	
	//유효한 괄호
	//유효한 괄호인지 체크해 boolean 값으로 리턴
	//동일한 유형의 괄호이며, 올바른 순서로 열고 닫는다. -> 즉, 먼저 들어간 순서가 중요함 ->먼저 열린게 나중에 닫힌다.-> 스택 [LIFO]
	
	//문제 해결 -> 몇 가지 예시를 생각하자
	// (( -> true, ([)] -> false, (()) -> true, {[]} -> true
	// -> 가장 먼저 열린게 가장 나중에 닫힌다. 가장 나중에 열린게 가장 먼저 닫힌다.
	// -> 열린 괄호와 닫힌 괄호의 개수 이용
	
	//스택 메서드
	//push() : 삽입, peek() : 최상단 조회, pop() : 삭제
	
	//1. 문자열인 괄호를 문자 하나하나로 쪼개기 -> toCharArray
	//2. 문자를 담는 스택 생성			 -> (이 들어가면 다음에 들어오는 모든 괄호가 )인지 확인작업 -> peek를 이용
	//3. 문자를 열고, 닫았으면 -> 열린 괄호와 닫는 괄호를 뺴고, 다음 열린 괄호를 닫는 괄호를 체크하도록 포인터 이동
	//4. 스택에 남아있는 괄호가 있으면 ->false, 스택에 남아있는 괄호가 없으면 -> true
	
	public static boolean solve(String s) {
		//1. ds
		Stack<Character> stack = new Stack<>();
		
		//2. for while
		for(int i=0; i<s.length(); i++) {
			if(s.charAt(i)=='('||s.charAt(i)=='['||s.charAt(i)=='{') {		//여는 괄호이면 -> push
				stack.push(s.charAt(i));
			}//괄호 마다 맞는 괄호인지 체크 하는 부분
			else if(s.charAt(i)==')' && !stack.empty() && stack.peek()=='(') {	// )이고 스택이 비어있지않고, 최상단 조회시 (이면
				stack.pop();
			}
			else if(s.charAt(i)==']' && !stack.empty() && stack.peek()=='[') {	// ]이고 스택이 비어있지않고, 최상단 조회시 [이면
				stack.pop();
			}
			else if(s.charAt(i)=='}' && !stack.empty() && stack.peek()=='{') {	// }이고 스택이 비어있지않고, 최상단 조회시 {이면
				stack.pop();
			}else {
				return false;
			}
		}
		return stack.empty();
	}
}

 

 

package QueuenStackBasic;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class TreeNode{
	int val;
	TreeNode left, right;
	TreeNode (int x){
		this.val=x;
	}
}

public class QueuenStack3 {
	public static void main(String[] args) {
		TreeNode root = new TreeNode(1);	//root노드인 (1) 생성
		
		//루트 노드에 딸린 노드 생성
		root.left=new TreeNode(2);
		root.right=new TreeNode(3);
		root.left.left=new TreeNode(4);
		root.left.right=new TreeNode(5);
		
		System.out.println("최종 결괏값 : "+solve(root));
		
	}
	//BinaryTree Level Order
	//List안의 List형태로 담아서 레벨에 따른 순서 정렬 -> 큐 이용 -> bfs 기초
	//-> Queue : bfs, Stack : dfs
	
	//문제 해결
	//1. 주어진 트리를 큐에 통째로 넣는다.
	//2. 트리 (1) -> 트리 (2), 트리 (3)
	//3. 트리 (2) -> 트리 (4), 트리 (5)
	//-> List[1] -> List<List[1]>
	//-> List[2,3] -> List<List [1], [2,3]>
	//-> List[4,5] -> List<List [1], [2,3], [4,5]>
	
	public static List<List<Integer>> solve(TreeNode root) {		// -> 목표: 큐에 넣어서 빼낸다.

		//1. ds
		List<List<Integer>> result = new ArrayList<>();
		
		// 트리노드를 담을 그릇[큐] 생성
		Queue<TreeNode> queue = new LinkedList<>(); //Queue<> - LinkedList<>()
		queue.offer(root); //큐에 root를 담는다 -> 큐에 트리노드를 담은 형태
		
		//2. for, while add algo
		//큐에서 빼는 경우 -> 일반적으로 남아있는게 없을때까지 -> null
		while(!queue.isEmpty()) {	//탈출조건 : 비어있을 때 [null]
			//1 -> //2,3 -> //4,5
			
			//사이즈 변수 확인
			int size=queue.size();	//1 -> //2 -> //2
			System.out.println("사이즈 체크 : "+size);
			
			//값을 담을 리스트 생성 -> 큐에서 제거한 후 담아야 하기 때문에 미리 생성
			//[큐가 있는지 체크 한후 담아야 하기 때문에, 그 이전도 그 이후도 아닌 이 때 생성]
			List<Integer> list = new ArrayList<>();
			
			for(int i=0;i<size;i++) {	//1 //2 //3 //4 //5
				TreeNode node = queue.poll();	//제거
				
				//노드값을 리스트에 담는다.
				list.add(node.val);	//1 -> //1,2 -> //1,23 -> 1,23,45
				
				//1을 날리고, 1의 자식들을 큐에 담는다.
				if(node.left !=null) {
					queue.offer(node.left);		//2 //4 //
				}
				if(node.right !=null) {
					queue.offer(node.right);	//3	//5 //
				}
				
				
				
			}
			//List를 List에 넣는다. -> List[1] -> List<List[1]>
			result.add(list);
			System.out.println(result);

		}
		return result;
	}
}