[알고리즘] 1. 스택

 Stack이란,

 

• 한쪽끝에서만자료를넣고뺄수있는자료구조

• 마지막으로넣은것이가장먼저나오기때문에 Last In Frist Out(LIFO)라고도한다.

• push : 스택에 자료를 넣는 연산

• pop : 스택에서 자료를 빼는 연산

• top : 스택의 가장 위에 있는 자료를 보는 연산

• empty : 스택이 비어있는지 아닌지를 알아보는 연산

• size : 스택에 저장되어있는 자료의 개수를 알아보는 연산

 

Stack을 이용하여 풀기 좋은 문제들,

 - 단어 뒤집기

 - 괄호 VPS(Valid Parenthesis String) 확인

 - 수열 (어떤 규칙에 따라 차례로 나열된 수의 열)

 - 에디터 (커서이동)

 

1. 단어 뒤집기 예제 (9093번)

import java.util.*;
import java.io.*;

public class Main {
	
    public static void main( String[] args ) throws IOException {
    	
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        
        int t = Integer.parseInt(bf.readLine());
        
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        while (t-- > 0) {
        	
            String str = bf.readLine() + "\n";
            
            Stack<Character> s = new Stack<>();
            
            for (char ch : str.toCharArray()) {
            	
                if (ch == '\n' || ch == ' ') {
                	
                    while (!s.isEmpty()) {
                    	
                        bw.write(s.pop());
                    }
                    
                    bw.write(ch);
                } else {
                	
                    s.push(ch);
                }
            }
        }
        
        bw.flush();
    }
}

 

2. 괄호 VPS 예제 (9012번)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
	
    public static void main( String[] args ) throws Exception {
    	
    	BufferedReader bf = new BufferedReader( new InputStreamReader( System.in ) );
    	
    	int loop = bf.readLine().charAt(0) -'0';
    	StringBuilder builder = new StringBuilder();
    	
    	while( loop-- > 0 ) {
    		
    		String result = check( bf.readLine().toCharArray());
    		
    		builder.append( result );
    		builder.append( "\n" );
    	}
    	
    	bf.close();
    	
    	System.out.print( builder.toString() ) ;
    }
    
    private static String check( char [] ps ) {
    	
    	Stack< Character > stack = new Stack<>();
		
		for( char p : ps ) {
			
			if( p == '(' ) {
			
				stack.push( p );
				
			} else {
				
				if( stack.isEmpty() ) {
					
					return "NO";
				}else {
					
					stack.pop();
				}
			}
		}
		
		if( stack.isEmpty() ) return "YES";
		
		return "NO";
    }
}

 

3. 수열 예제 (1874번)

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

public class Main {
	
	 public static void solve( int[] a ) {
		 
		 Stack< Integer > stack = new Stack<>();
		 
		 int m = 0;
		 
		 StringBuilder sb = new StringBuilder();
		 
		 // 4 3 6 8 7 5 2 1
		 
		 for( int x : a ) {
			 
			 if( x > m ) {
				 
				 while( x > m ) {
					 stack.push(++m);
					 sb.append( "+\n" );
				 }
				 
				 stack.pop();
				 sb.append( "-\n" );
			 } else {
				 
				 if( stack.peek() != x ) {
					 
					 System.out.println( "NO" );
					 return;
				 }
				 stack.pop();
				 sb.append( "-\n" );
			 }
		 }
		 
		 System.out.println(sb);
	 }

	public static void main(String[] args) {
		
		Scanner sc = new Scanner( System.in );
		
		int n = sc.nextInt();
		
		int [] a = new int[n];
		
		for( int i=0; i<n; i++) {
			
			a[i] = sc.nextInt();
		}
		
		solve(a);
		
	}
}

* 전위 증감 연산자 : 증감을 한 뒤 x 값을 평가한다.

 - int x = 5;

 - int y = ++x;     // x는 6이고, 6은 y에 할당된다.

 

* 후위 증감 연산자 : 컴파일러가 x의 임시본을 만든 뒤 원본 x를 증가시킨뒤 x의 임시 복사본을 평가한다.

 - int x = 5;

 - int y = x++;     // 5는 y에 할당 되고, x는 6이 된다.

 

4. 에디터 (1406번)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {

	public static void main( String[] args ) throws IOException {

		BufferedReader io = new BufferedReader( new InputStreamReader( System.in ) );
		
		String text = io.readLine();
		
		Stack< Character > left = new Stack<>();
		Stack< Character > right = new Stack<>();
		
		for( Character t : text.toCharArray() ) {
			
			left.push(t);
		}
		
		// abcd
		
		int loop = Integer.parseInt( io.readLine() );
		
		while( loop-- > 0 ) {
			
			String command = io.readLine();
			
			switch ( command.charAt(0) ) {
			
			case 'L':
				if (!left.empty()) right.push(left.pop());
				break;
			case 'D':
				if (!right.empty()) left.push(right.pop());
				break;
			case 'B':
				if (!left.empty()) left.pop();
				break;
			case 'P':
				left.push( command.charAt(2) );
				break;
				
			}
		}

		 while ( !left.empty( )) {
			 
			 right.push(left.pop());
	    }
		 
		 StringBuilder sb = new StringBuilder();
		
		
		while (!right.empty()) {
			
		    sb.append(right.pop());
		}
		
		System.out.println( sb );
		
	}
}