[알유] 스택

스택(Stack)

스택은 데이터를 일시적으로 저장하기 위해 사용하는 자료구조로, 데이터의 입력과 출력 순서는 후입선출(LIFO, Last In First Out)이다. 즉, 가장 나중에 넣은 데이터를 가장 먼저 꺼내는 순서를 가지고 있다. 스택에 데이터를 넣는 작업을 푸시(push)라 하고, 스택에서 데이터를 꺼내는 작업을 팝(pop)이라고 한다. 또, 데이터가 들어오는 출입구 쪽(윗쪽)을 Top이라 하고, 스택의 가장 아랫 부분을 Bottom이라 한다.

java에서 제공하는 Stack 클래스

자바에서는 Stack 클래스를 제공한다. Stack 클래스는 List 컬렉션 클래스의 Vector 클래스를 상속받아, 전형적인 스택 메모리 구조의 클래스를 제공한다. 구현하기 전에 사용부터 해보자.

먼저 자바에서 Stack 클래스를 사용하기 위해서는 import 구문을 추가해줘야 한다.

import java.util.Stack;

그리고 다음과 같이 Stack을 선언하면 된다.

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

사용하는 방법은 간단하다. 위에서 말했지만 데이터를 추가할 땐 push(), 데이터를 꺼낼 때는 pop()을 사용하면 된다.

import java.util.Stack;

public class Stack2 {
	public static void main(String[] args) {
		Stack<Integer> stk = new Stack<>();
		stk.push(1); // 데이터 저장
		stk.push(2); // 데이터 저장
		stk.push(3); // 데이터 저장
		stk.push(4); // 데이터 저장
		stk.pop();   // 데이터 꺼내기
		System.out.println("top : " + stk.peek()); // 3
		
		System.out.println("1이 어디 있어요? : " + stk.search(1));

		while(!stk.isEmpty()) System.out.println(stk.pop()); // 데이터를 꺼내면서 출력
		
		if(stk.isEmpty()) System.out.println("비어있습니다.");
	}
}

위의 코드를 실행하면 다음과 같은 결과가 출력된다.

위에서 사용한 메소드 외에도 다른 추가적인 메소드를 지원한다.

• 메소드 종류
  • stk.push() : 값 추가
  • stk.pop() : 값 꺼내기
  • stk.size() : stack 크기
  • stk.empty() : 비어있는지 아닌지 판별하며, 반환 값은 boolean 타입이다.
  • stk.contains() : 값이 존재하는지 판별하며 반환 값은 boolean 타입이다.
  • stk.search() : 해당 스택에서 전달된 객체가 존재하는 위치의 인덱스를 반환한다. 이때 인덱스는 제일 상단에 있는 요소의 위치가 1이며 밑으로 내려갈수록 위치 숫자가 증가한다.

Stack 배열로 구현하기

여러 메소드들이 있지만 간단하게 구현해보기 위해 필수적으로 있어야 할 push, pop, peek 메소드 세 개를 구현해보자.

public class Stack {
	// 필드 
	private int top; // 인덱스
	private int size; // 크기
	private int[] stack; // 본체
	
	// 생성자
	public Stack(int size) {
		this.size = size;
		stack = new int[size];
		top = -1;
	}
	
	public void push(int i){
		stack[++top] = i;
		System.out.println(i + " push 성공!");
	}
	
	public void pop() {
		System.out.println(stack[top] + " pop 성공!");
		int pop = stack[top];
		stack[top--] = 0;
	}
	
	public void peek() {
		System.out.println(stack[top] + " peek 성공");
	}
	
	
	public static void main(String[] args) {
		Stack stk = new Stack(5);
		stk.push(1);
		stk.push(2);
		stk.push(3);
		stk.pop();
		stk.peek();
	}
}

위의 코드를 실행하면 다음과 같이 출력된다.

---

적용하기(백준 : 제로)

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

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int len = sc.nextInt();
		int num = 0;
		int sum = 0;
		Stack<Integer> stk = new Stack<>();
		
		for(int i = 0; i < len; i++) {
			num = sc.nextInt();
			if(num != 0) stk.push(num);
			else stk.pop();
		}
		
		for(int n : stk) sum += n;

		System.out.print(sum);
	}
}

• 참고 : Do it 자료구조와 함께 배우는 알고리즘 입문 자바 편