백준 10828번: 스택

백준 10828번: 스택

 

- 문제명 그대로 자료구조 중 스택을 이용하면 되는 문제입니다.

- Java에서 스택은 java.util.Stack 을 import 하면 쉽게 사용할 수 있는 자료구조입니다. 그래서 이번 문제에서는 util에서 제공해주는 스택을 사용한 코드와 제공해주는 스택을 사용하지 않고 직접 배열로 구현하는 코드 두 가지를 작성해 보았습니다.

 

- 우선 util에서 제공해주는 스택을 사용한 코드입니다.

- Stack 라이브러리 중에는 다음과 같은 기능이 있습니다.

• push() : 스택에 데이터 삽입
• pop() : 스택에사 가장 위에 있는 데이터를 팝(반환하고 삭제)
• peek() : 스택에서 가장 위에 있는 데이터를 읽음(반환)
• isEmpty() : 스택이 비어있는지를 반환
• size() : 스택에 쌓여있는 데이터 수를 반환

	import java.util.Scanner;
	import java.util.Stack;
	public class Main {
	public static void main(String[] args) {
	Stack<Integer> s = new Stack<Integer>();
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	for(int i = 0; i < n; i++) {
	String input = sc.next();
	if(input.contains("push")) {
	int a= sc.nextInt();
	s.push(a);
	}
	else if(input.equals("pop")){
	System.out.println(s.isEmpty() ? -1 : s.pop());
	}
	else if(input.equals("size")) {
	System.out.println(s.size());
	}
	else if(input.equals("empty")) {
	System.out.println(s.isEmpty() ? 1 : 0);
	}
	else if(input.equals("top")) {
	System.out.println(s.isEmpty() ? -1 : s.peek());
	}
	}
	sc.close();
	}
	}

view raw BOJ_10828(1).java hosted with ❤ by GitHub

 

- 이번에는 배열로 직접 구현한 스택을 사용한 코드입니다.

- Stack 라이브러리와 같은 이름의 매소드를 작성했습니다.

- Arraylist를 선언하여 출력해야 될 값을 list에 저장한 후 한 번에 출력하도록 했습니다.

- ptr 은 스택 포인터 역할을 하고 있습니다.

• push() : 입력받은 데이터 값을 ptr 값을 가진 stk 배열의 인덱스에 넣습니다. stk[ptr++] 를 통해 데이터를 배열에 넣은 뒤 ptr 을 증가시켜 다음 인덱스 값을 가르키도록 했습니다.
• pop() : stk[--ptr] 을 통해 먼저 ptr 값을 감소시킨 뒤 stk 배열의 가장 위에 있는 값을 반환합니다. 삭제는 하지 않습니다. 후에 push() 를 하면 자동으로 삭제되고 입력한 값이 넣어지기 때문입니다.
• peek() : stk[ptr-1]의 값을 반환합니다. 배열의 인덱스는 0부터 시작하기 때문에 ptr-1을 입력합니다.
• isEmpty() : ptr 이 0보다 작거나 같으면 true 를 반환합니다.
• size() : ptr의 값이 곧 스택의 크기이므로 ptr 값을 반환합니다.

	import java.util.Scanner;
	import java.util.ArrayList;
	class IntStack{
	int max;
	int ptr;
	int[] stk;
	public IntStack(int capacity){
	ptr = 0;
	max = capacity;
	try {
	stk = new int[max];
	}catch (OutOfMemoryError e){
	max = 0;
	}
	}
	//stack에 push X
	public int push(int x) {
	return stk[ptr++] = x;
	}
	//stack에 pop
	public int pop(){
	return stk[--ptr];
	}
	//stack의 size
	public int size(){
	return ptr;
	}
	//stack의 empty 여부, 비어있으면 true
	public boolean isEmpty(){
	return ptr <= 0;
	}
	//stack의 top peek
	public int peek(){
	return stk[ptr - 1];
	}
	}
	public class Main{
	public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	ArrayList<Integer> list = new ArrayList<>();
	int n = sc.nextInt();
	IntStack s = new IntStack(n);
	boolean tf;
	int i = 0;
	int x;
	while(i < n){
	String input = sc.next();
	if(input.contains("push")){
	int a = sc.nextInt();
	s.push(a);
	}
	else if(input.contains("pop")){
	tf = s.isEmpty();
	if(tf == true)
	list.add(-1);
	else{
	x = s.pop();
	list.add(x);
	}
	}
	else if(input.contains("size")){
	x = s.size();
	list.add(x);
	}
	else if(input.contains("empty")){
	tf = s.isEmpty();
	if(tf == true)
	list.add(1);
	else
	list.add(0);
	}
	else if(input.contains("top")){
	tf = s.isEmpty();
	if(tf == true)
	list.add(-1);
	else{
	x = s.peek();
	list.add(x);
	}
	}
	i++;
	}
	for(int j = 0; j < list.size(); j++)
	System.out.println(list.get(j));
	sc.close();
	}
	}

view raw BOJ_10828(2).java hosted with ❤ by GitHub

 

 

 

 

참조하면 좋은 다른 글

[Programming/Algorithm] - 스택 - 스택과 큐( STACK&QUEUE)