스택

스택

• 입구와 출구가 하나밖에 없는 자료구조
• LIFO(Last In First Out)

스택 연산

• pop() : 스택의 가장 위에 있는 데이터를 제거하면서 반환한다.
• push(item) : item을 스택의 가장 윗부분에 추가한다.
• isEmpty() : 스택이 비었는지 확인한다.

스택 구현(배열 사용)

public class Stack{

    private int stack[50];
    private int top=-1;
   
   	public int pop() {
    	if(isEmpty()){
        	System.out.println("스택이 비었습니다.");
        	return -1;
        }
        return stack[top--];
    }
    
    public void push(int item){
        stack[top++] = item;
    }
    
    public boolean isEmpty(){
    	if(top==-1)
        	return true;
        else
        	return false;
    }
}

예시

• 백준 10828번 스택

https://www.acmicpc.net/problem/10828

1) 문제
정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 다섯 가지이다.

• push X: 정수 X를 스택에 넣는 연산이다.
• pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 스택에 들어있는 정수의 개수를 출력한다.
• empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
• top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

2) 코드

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

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());
		int stack[] = new int[N];
		int top = -1;
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		for(int i=0;i<N;i++) {
			st=new StringTokenizer(br.readLine());
			String op = st.nextToken();
			if(op.equals("push")) {
				int num = Integer.parseInt(st.nextToken());
				top++;
				stack[top]=num;
			}
			else if(op.equals("top")) {
				if(top==-1) {
					sb.append(-1).append("\n");
				}
				else {
					sb.append(stack[top]).append("\n");
				}
			}
			else if(op.equals("pop")) {
				if(top==-1) {
					sb.append(-1).append("\n");
				}
				else {
					sb.append(stack[top--]).append("\n");
				}
			}
			else if(op.equals("size")) {
				sb.append(top+1).append("\n");
			}
			else if(op.equals("empty")) {
				if(top==-1) {
					sb.append(1).append("\n");
				}
				else {
					sb.append(0).append("\n");
				}
			}
		}
		System.out.print(sb);
	}
}

이미지 출처 : https://ai-rtistic.com/2022/01/15/data-structure-stack/