<computer_science>/자료구조 Data Structure
[자료구조] 스택 Stack, Last In First Out (with Java, BaekJoon No.10828)
Rizingblare
2024. 1. 5. 16:39
0. Intro
컴퓨터에서 굉장히 많이 쓰이는 자료구조이며 대부분 프로그래밍 언어에서 기본으로 내장되어 있는 배열이나 리스트와 같은 자료구조를 제외하면 자료구조에서 가장 먼저 소개되곤 하는 자료구조인 스택은
스택이라는 말은 평소 일상 생활에서도 가끔 사용하는데 내 또래 같은 경우에는 League of Legend라는 게임의 나서스 캐라는 캐릭터가 모티브가 되어, 차근차근 쌓아나간다. 아니면 참고 버틴다. 등의 의미로 사용되곤한다. 예를 들면 분노 1스택 적립, 이라던가 업보 1스택 적립 등등 ㅋㅋ
사전적 정의 또한 마찬가지 스택은 쌓다
나서스 스택 분노 1스택 적립
사전적 정의
실제 활용 사례 ( 실행취소, 웹 뒤로가기
1. MyStack 직접 구현
import java.util.Scanner;
public class Main {
private static final Scanner scanner = new Scanner(System.in);
private static final StringBuffer sb = new StringBuffer();
public static void main(String[] args) {
int n = scanner.nextInt();
MyStack stack = new MyStack(n);
requestCommand(n, stack);
System.out.println(sb);
}
private static void requestCommand(int n, MyStack stack) {
for (int i = 0; i < n; i++) {
String cmd = scanner.next();
switch (cmd) {
case "push":
int pushItem = scanner.nextInt();
stack.push(pushItem);
break;
case "pop":
int popItem = stack.pop();
sb.append(popItem).append("\n");
break;
case "size":
int size = stack.size();
sb.append(size).append("\n");
break;
case "empty":
int empty = stack.empty();
sb.append(empty).append("\n");
break;
case "top":
int topItem = stack.top();
sb.append(topItem).append("\n");
break;
}
}
}
private static class MyStack {
private final int[] stack;
private int len;
public MyStack(int n) {
this.stack = new int[n];
this.len = 0;
}
public void push(int newItem) {
stack[len++] = newItem;
}
public int pop() {
if (len == 0) return -1;
len--;
return stack[len];
}
public int size() {
return len;
}
public int empty() {
if (len == 0) return 1;
return 0;
}
public int top() {
if (len == 0) return -1;
return stack[len-1];
}
}
}
2. Stack 라이브러리 활용
import java.util.Scanner;
import java.util.Stack;
public class Main {
private static final Scanner scanner = new Scanner(System.in);
private static final StringBuffer sb = new StringBuffer();
public static void main(String[] args) {
int n = scanner.nextInt();
Stack<Integer> stack = new Stack<>();
requestCommand(n, stack);
System.out.println(sb);
}
private static void requestCommand(int n, Stack<Integer> stack) {
for (int i = 0; i < n; i++) {
String cmd = scanner.next();
switch (cmd) {
case "push":
int pushItem = scanner.nextInt();
stack.push(pushItem);
break;
case "pop":
if (stack.isEmpty()){
sb.append(-1).append("\n");
break;
}
int popItem = stack.pop();
sb.append(popItem).append("\n");
break;
case "size":
int size = stack.size();
sb.append(size).append("\n");
break;
case "empty":
if (stack.isEmpty()){
sb.append(1).append("\n");
break;
}
sb.append(0).append("\n");
break;
case "top":
if (stack.isEmpty()){
sb.append(-1).append("\n");
break;
}
int topItem = stack.peek();
sb.append(topItem).append("\n");
break;
}
}
}
}
3. 하드 코딩
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
StringBuffer sb = new StringBuffer();
int n = scanner.nextInt();
int[] stack = new int[10001];
int len = 0;
for (int i = 0; i < n; i++) {
String cmd = scanner.next();
if (cmd.equals("push")) {
int a = scanner.nextInt();
stack[len] = a;
len++;
}
if (cmd.equals("pop")) {
if (len == 0) sb.append(-1).append("\n");
else {
sb.append(stack[len-1]).append("\n");
len--;
}
}
if (cmd.equals("top")) {
if (len == 0) sb.append(-1).append("\n");
else sb.append(stack[len-1]).append("\n");
}
if (cmd.equals("size")) {
sb.append(len).append("\n");
}
if (cmd.equals("empty")) {
if (len == 0) sb.append(1).append("\n");
else sb.append(0).append("\n");
}
}
System.out.println(sb);
}
}4. Trouble Shooting
출력 부분을 매번 `System.out.println()`의 표준 입출력으로 처리했더니 시간 초과가 계속 발생했다.
StringBuffer을 사용하여 출력을 처리했더니 시간 초과를 해결할 수 있었다.
5. 참고
YouTube [바킹독의 실전 알고리즘] 0x05강 - 스택
개발자 Miro - [자료구조] 스택(Stack)과 큐(Queue)에 대해서 알아보자!
데이터 드리븐 마케팅 Blog - [자료구조] 4. 스택(Stack)이란? / 연산, 구현방법
문제 링크:
https://www.acmicpc.net/problem/10828
10828번: 스택
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지
www.acmicpc.net