스택과 JAVA Stack 클래스

Algorithm : 스택과 JAVA Stack 클래스

: 데이터를 일시적으로 저장하기 위한 자료구조, 가장 마지막에 넣은 데이터를 가장 먼저 꺼낸다.

 

스택의 특징

• LIFO(Last In First Out), 가장 마지막에 넣은 데이터가 가장 먼저 출력된다.
• 스택에 데이터를 넣는 작업은 push, 스택에서 데이터를 꺼내는 작업은 pop이다. 
• push와 pop이 일어나는 위치는 top, 스택의 가장 아래는 bottom이다.

 

스택 만들기

• 스택 본체 배열 : stk - stk[0]이 스택의  bottom
• 스택 용량 : max - 배열 stk의 요솟수와 같다.
• 스택 포인터 : ptr - 스택에 쌓여있는 데이터의 수를 나타낸다.
• 생성자 : Stack - ptr을 0으로 설정하고, max의 값을 설정하고, stk 배열에 max만큼의 공간을 할당한다.
• push 메서드 : push - 전달받은 데이터를 배열 stk[ptr]에 저장하고, ptr의 값을 증가한다.
• pop 메서드 : pop - 스택이 비어있어 pop을 할 수 없는 경우에는 -1을 반환한다. 그 외의 경우에는 먼저 ptr을 감소하고, stk[ptr]의 값을 반환한다.
• size 메서드 : size - ptr의 값을 반환한다.
• empty 메서드 : empty - ptr의 값이 0보다 크면 1을, 0보다 작거나 같으면 1을 반환한다.
• top 메서드 : top - ptr이 0보다 작거나 같으면 -1을, 그 외의 경우에는 stk[ptr-1]의 값을 반환한다.

 

스택 알고리즘 코드

출처 : 10828번: 스택 (acmicpc.net)

10828번: 스택

 

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

class Stack {

    public int ptr;
    public int max;
    public int[] stk;
    
    public Stack() {
        
        ptr = 0;
        max = 10001;
        stk = new int[max];
        
    }
    
    public void push(int x) {
        
        stk[ptr++] = x;
        
    }
    
    public int pop() {
        
        if(ptr <= 0)
            return -1;
	   
	    return stk[--ptr];
        
    }
    
    public int size() {
        
        return ptr;
        
    }
    
    public int empty() {
        
        if(ptr > 0) return 0;
        else return 1;
        
    }
    
    public int top() {
        
        if(ptr <= 0) return -1;
        else return stk[ptr-1];
        
    }
        

}

public class Main {
    
	public static void main(String[] args) throws IOException {
	    
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    
	    int n = Integer.parseInt(br.readLine());
	    Stack stk = new Stack();
	    
	    StringBuilder sb = new StringBuilder();
	    
	    for(int i = 0; i < n; i++) {
	        
	        String full_command = br.readLine();
	        String command = full_command.split(" ")[0];
	        
	        
	        switch(command) {
	            case "push":
	                int x = Integer.parseInt(full_command.split(" ")[1]);
	                stk.push(x);
	                break;
	            case "pop":
	                sb.append(stk.pop()).append("\n");
	                break;
	            case "size":
	                sb.append(stk.size()).append("\n");
	                break;
	            case "empty":
	                sb.append(stk.empty()).append("\n");
	                break;
	            case "top":
	                sb.append(stk.top()).append("\n");
	                break;
	            default:
	                break;
	        }
	        
	    }
	    
	    System.out.println(sb);
	    
	}
}

 

JAVA Stack 클래스

Stack 선언

import java.util.Stack;

Stack<StackType> StackName = new Stack<StackType>();

 

Stack 메서드

Stack<Integer> stk = new Stack<Integer>();

stk.push(1); // 스택에 값 1을 push
stk.push(2);
stk.push(3); 

/********
  | 3 |
  |---|
  | 2 |    stack의 모습
  |---|
  | 1 |
********/

stk.pop(); // 스택의 가장 상단에 있는 값 3을 pop

/********
  | 2 |
  |---|    stack의 모습
  | 1 |
********/

stk.peek(); // 스택의 가장 상단에 있는 값 2 출력
stk.size(); // 스택의 사이즈인 2 출력
stk.empty(); // 스택이 비어있다면 true를 비어있지 않다면 false를 반환
stk.contains(1); // 스택에 값 1이 존재하면 true를, 존재하지 않으면 false를 반환
stk.search(2); // 스택의 상단에서부터 값 2를 찾아서 위치를 반환하는데 스택의 top이 1

 

JAVA Stack 클래스 사용 알고리즘 코드

출처 : 1406번: 에디터 (acmicpc.net)

1406번: 에디터

 

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

public class Main {
    
	public static void main(String[] args) throws IOException {
	    
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    
	    String n = br.readLine(); // 초기 문자열
	    int m = Integer.parseInt(br.readLine()); // 명령어 개수
	    
	    Stack<String> left = new Stack<String>();
	    Stack<String> right = new Stack<String>();
	    
	    StringBuilder sb = new StringBuilder();
	    
        String[] ch = n.split("");
	    for(int i = 0; i < ch.length; i++) 
	        left.push(ch[i]);
	    
	    for(int i = 0; i < m; i++) {
	        
	        String command = br.readLine();
	        String c = command.split(" ")[0];
	        
	        if(c.equals("L") && !left.empty())
	            right.push(left.pop());
            if(c.equals("D") && !right.empty())
	            left.push(right.pop());
	        if(c.equals("B") && !left.empty())
	            left.pop();
	        if(c.equals("P"))
	            left.push(command.split(" ")[1]);
	        
	    }
	    
	    while(!left.empty())
	        right.push(left.pop());
	    
	    while(!right.empty())
	        sb.append(right.pop());
	    
	    System.out.println(sb);
	    
	}
}

[백준 1406] 에디터 (자바)

 

---

 

Stack 클래스 참고 사이트

• [Java] 자바 Stack 클래스 사용법 & 예제 총정리 (tistory.com)