Object
-
Stack을 구현하기
-
Java에서 제공하는 Stack Class를 이용하기
-
백준에서 시간초과 오류를 해결하는 StringBuilder Class
-
Stack Class Function
Build
스택의 기능 중에 해당 기능들만 구현
- Push
- Pop
- Empty
Full (배열이기 때문에 필요)
여기선 생략
필요한 멤버 변수
class Stack{
private int top; // 가장 마지막에 들어온 data index
private int[] stackData; // stack data의 배열Stack은 밑에서 부터 차곡차곡 쌓아 올라가는 형태의 자료구조이다.
가장 마지막에 들어온 data의 값이 뭔지 알기 위해 기본적으로 stack에서는 top이라는 것을 이용한다.
stackData들을 담을 장소로 배열을 선택.
Stack 생성자(case. 배열구현)
Stack(){
top = -1; // 아무것도 없는 경우
stackData = new int[10000]; // 임의로 크기 10000설정
}스택의 사이즈가 주어지는 경우 배열로 구현하면 된다.
만약에 사이즈가 안주어는 스택이라면..? => LinkedList를 이용
스택이 비어 있는가?
boolean isEmpty(){
if(top == -1) //비어있는 경우,, top은 -1
return true;
return false;
}해당 부분은 굉장히 중요한 기능이다.
pop을 할 경우, search를 할 경우, peek을 할 경우 등등
스택에 데이터가 들어가 있지도 않고 스택이 비어있는데 해당 기능들을 사용하면
오류가 일어난다.
그렇기 때문에 꼭 스택이 비어있는지 안비어있는지 확인하는 isEmpty 기능은 필수인것.
isFull 또한 해당 스택에서는 크기가 정해 졌으니 필요하다.
상황에 따라 다른것.
Push와 Pop
void push(int data){
stackData[++top] = data;
}Push는 data값을 인자로 받고 top을 갱신한 뒤에
top이 가리키는 위치에 data를 삽입해주는 기능을 한다.
int pop(){
if(isEmpty())
return -1;
return stackData[top--];
}Pop은 현재 top이 가리키는 위치의 값을 반환하고
top이 가리키는 위치는 비어있으니 그 아래에 있는 data값을 가리키는 기능을 한다.
Conclusion
솔직히 자료구조는 별 거 없다.
해당 자료구조가 어떠한 형태로 데이터들을 집합화 시키는지 파악 한 뒤에
기능들을 차근차근 구현해주기만 하면 되는 것.
해당 자료구조(여기선 스택)이 중요한 Concept만 잃지 않는다면 어떠한 형태로 코드를 짜도 상관은 없다.
스택의 중요한 Concept은 선입후출(FiLO) 구조 인 것.
Use Stack Class
백준의 스택 문제를 가지고 Stack Class를 이용해 보겠다.
💡Important
import java.util.Stack;
Stack<데이터 타입> stack = new Stack<>();
//제네릭<데이터 타입>은 Stack 배열안에 들어가는 데이터의 타입을 지정하는 것이다. 정수를 넣고싶으면 로 지정하면 되고 실수를 넣고 싶다면 로 지정하면 된다.
🖋️Build
while(N > 0){
command = input.next();
switch(command){
case "push":
data = input.nextInt();
stack.push(data);
break;
case "top":
if(stack.isEmpty())
System.out.println(-1);
else
System.out.println(stack.peek());
break;
case "size":
System.out.println(stack.size());
break;
case "pop":
if(stack.isEmpty())
System.out.println(-1);
else
System.out.println(stack.pop());
break;
case "empty":
if(stack.isEmpty())
System.out.println(1);
else
System.out.println(0);
break;
default:
break;
}
N--;
}📢ERROR
그런데 시간초과 라는 오류가 나온다
왜??
지금 거의 Case 절반에서 System.out.println()을 사용 하고 있는데
System.out.println()은 호출부터 굉장히 느리다.
만약 N이 10000이라고 가정 하면 엄청나게 느려지는 현상이 있기 때문에 맞는 코드를 제출해도 시간 초과가 나온다는 것이다.
📚System.out.println()
-
표준 입출력 기능
-
내부적으로 동기화 처리가 되어있다. 즉, 작업 중인 스레드가 있을 때, 다른 스레드는 대기 시간이 발생한다.
-
이로 인해 오버 헤드가 발생 할 수 있다. -> 오버헤드가 쌓여 성능 저하 발생
그래서, StringBuilder를 사용해주도록 한다.
📚StringBuilder
-
출력 할 데이터를 모아서 한번에 출력
-
출력 시 system.out.println을 사용하거나 사용 횟수를 줄인다.
-
String 보다 쉽게 문자열 처리 가능
public class Main {
public static void main(String[] args){
StringBuilder sb = new StringBuilder();
for(~~~)
sb.append(i + "\n");
System.out.println(sb);
}
}🖋️Solution
(...)
case "top":
if(stack.isEmpty())
sb.append(-1 + "\n");
else
sb.append(stack.peek() + "\n");
break;
(...)
(while 문 탈출)
System.out.println(sb);뭔가 중요한 사실을 습득 한 것 같다.
가급적이면 한번에 출력하는 StringBuilder을 이용해보도록 하자
Stack Class Function
- push
data 입력 - pop
가장 상단의 원소 값 제거 및 반환 - clear
전부 제거 - peek
가장 상단의 값 반환 - empty
스택이 비었는지 확인 - contains
data 값이 스택에 있는지 확인
