나의 길
Java 스택(Stack)과 큐(Queue) 본문
스택(Stack)이란?
스택은 데이터를 일시적으로 저장하기 위해 사용하는 자료구조로, 밑이 막힌 투명한 실린더에 고체를 쌓고 뺀다라고 생각하면 됩니다. 특징은 마지막에 넣은 데이터를 처음으로 꺼냅니다.
해당 이미지는 스택을 이해하기 위한 예시를 입니다. Java main method가 실행되고, z method를 호출합니다. z method 호출을 종료하고, main method로 돌아와 main method 호출을 종료합니다. 이미지에도 나타나 있듯이 스택에서 데이터를 집어넣는 것을 push, 빼는 것을 pop이라고 합니다.
스택 기본 사용법
Java에서는 Stack을 push, pop 이외에 peek(맨 위의 데이터 출력), search(해당 데이터가 있으면 그 위치 반환, 없으면 -1 반환), empty(해당 스택이 비어있으면 true) 메소드를 제공합니다.
위 이미지의 출력 값은 2 3 1 true입니다.
큐(Queue)란?
큐도 스택과 마찬가지로 데이터를 일시적으로 쌓아 놓는 자료구조입니다. 스택과 차이점은 밑이 뚫린 실린더에 고체를 하나씩 넣고 스택은 마지막 고체를 꺼냈지만 큐는 스택과 달리 처음 넣은 데이터(고체)를 처음으로 꺼냅니다.
해당 이미지는 큐를 이해하기 위한 예시로 404번 번호표를 가진 손님이 먼저 식당에 대기열을 걸어 놓고, 그 후 500번 손님이 대기열을 걸었다. 이후 식당이 오픈하고 404번 번호표 손님이 먼저 식당으로 입장했고, 이후 500번 손님도 입장을 완료했다. 큐에서는 데이터를 넣는 것을 enqueue(인큐), 데이터를 빼는 것을 dequeue(디큐)라고 부릅니다.
큐 기본 사용법
Java의 큐는 인터페이스로 위 이미지의 LinkedList, 그 이외의 PriorityQueue 등으로 구현합니다. offer(데이터 추가), poll(맨 앞의 데이터 제거)로 스택과 쓰는 단어만 다르고 메소드의 역할은 비슷합니다.
스택과 큐 직접 구현
위에서 스택과 큐를 사용한 것처럼 구현된 스택과 큐만 사용하면 이해가 조금 덜 된 느낌을 받아서 간단하게 스택과 큐를 구현해 보았습니다.
1. 스택
public class MyStack<E> {
private int max; // 스택 용량
private int ptr; // 스택 포인터
private E[] stk; // 스택 본체
public static class MyStackEmptyException extends RuntimeException {
MyStackEmptyException(String message){
super(message);
}
}
public static class MyStackOverflowException extends RuntimeException {
MyStackOverflowException(String message){
super(message);
}
}
public MyStack(int capacity) {
ptr = 0;
max = capacity;
try {
stk = (E[]) new Object[max];
}catch (OutOfMemoryError e){
max = 0;
}
}
public E push(E x) {
if (ptr >= max){
throw new MyStackOverflowException("스택이 가득찼습니다!");
}
return stk[ptr++] = x;
}
public E pop(){
if (ptr <= 0){
throw new MyStackEmptyException("스택이 비어있습니다!");
}
return stk[--ptr];
}
public E peek(){
if (ptr <= 0){
throw new MyStackEmptyException("스택이 비어있어 peek를 할 수 없습니다!");
}
return stk[ptr - 1];
}
public int size(){
return ptr;
}
public boolean isEmpty(){
return ptr <= 0;
}
}2. 큐
public class MyQueue<E> {
private int max;
private int num;
private E[] que;
public static class MyQueueEmptyException extends RuntimeException {
MyQueueEmptyException(String message){
super(message);
}
}
public static class MyQueueOverflowException extends RuntimeException {
MyQueueOverflowException(String message){
super(message);
}
}
public MyQueue(int capacity) {
num = 0;
max = capacity;
try {
que = (E[]) new Object[max];
}catch (OutOfMemoryError e){
max = 0;
}
}
public E enque(E x) {
if (num >= max){
throw new MyQueueOverflowException("큐가 가득찼습니다!");
}
que[num++] = x;
return x;
}
public E deque() {
if (num == 0){
throw new MyQueueEmptyException("큐가 비어있습니다!");
}
E result = que[0];
for(int i = 0; i < num - 1; i++){
que[i] = que[i + 1];
}
num--;
return result;
}
public E peek() {
if (num <= 0){
throw new MyQueueEmptyException("큐가 비어있어 peek를 할 수 없습니다!");
}
return que[num - 1];
}
public int size(){
return num;
}
public boolean isEmpty(){
return num <= 0;
}
}
기초 문제 풀이
- 스택 (백준 10773번 제로)
해당 문제를 짧게 살펴보자면 숫자 0이 입력되면 가장 최근에 입력된(해당 부분에서 스택을 사용해서 구현하기로 생각함) 0이 아닌 수를 제거하고 마지막에 남은 수들의 합을 구하는 문제입니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Stack<Integer> numStack = new Stack<>();
try {
int num = Integer.parseInt(br.readLine());
int sum = 0;
for (int i = 0; i < num; i++){
int temp = Integer.parseInt(br.readLine());
if (temp == 0){
numStack.pop();
}else {
numStack.push(temp);
}
}
while (!numStack.empty()){
sum += numStack.pop();
}
System.out.println(sum);
} catch (IOException e) {
throw new RuntimeException(e);
}
}
}- 큐 (백준 2160번 카드2)
해당 문제를 짧게 알아보자면 1~N장의 카드가 있고 제일 위에 있는 카드를 버리고, 그다음 위에 있는 카드를 밑으로 옮기는 행동(해당 부분에서 큐를 사용하여 구현하기로 생각함)을 반복한 후 마지막으로 남은 카드의 수를 출력한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static void main(String[] args) {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Queue<Integer> cardQueue = new LinkedList<>();
try {
int num = Integer.parseInt(br.readLine());
for (int i = 1; i <= num; i++){
cardQueue.add(i);
}
while (cardQueue.size() > 1){
cardQueue.poll();
int temp = cardQueue.poll();
cardQueue.add(temp);
}
System.out.println(cardQueue.peek());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
}
도전 문제
- 스택 (백준 9012번 괄호)
해당 문제를 이해해 보자면 올바른 괄호 문자열( "()" )의 경우 YES를 출력하고 아닐 경우 NO를 출력한다. ("(())(()())") 이와 같은 괄호 문자열도 YES를 출력한다는 걸 유의합니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
try {
int num = Integer.parseInt(br.readLine());
String result = "";
for (int i = 0; i < num; i++){
String[] inputStrArr = br.readLine().split("");
Stack<String> strStack = new Stack<>();
for (int j = 0; j < inputStrArr.length; j++){
String nowStr = inputStrArr[j];
if (strStack.size() == 0){
strStack.push(nowStr);
} else if (strStack.peek().equals("(") && nowStr.equals(")")) {
strStack.pop();
} else {
strStack.push(nowStr);
}
}
if (strStack.empty()){
sb.append("YES\n");
}else {
sb.append("NO\n");
}
}
System.out.print(sb.toString());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
}
입력받은 괄호 문자열을 하나씩 배열에 담고 스택에 사이즈가 0일 경우 push 한다. 다음부터 스택에 담긴 문자를 확인하여 여는 괄호이고 현재 문자가 닫는 괄호일 경우 여는 괄호를 pop 한다. 그리고 이외의 경우는 스택에 push 한다.
- 큐 (백준1158번 요세푸스 문제 0)
해당 문제를 이해해 보자면 1~N의 번호를 부여받은 사람들이 순서대로 원을 이루어 앉아있고, K번째 사람을 제거합니다. 제거된 사람의 번호를 정해진 출력 형식(<1, 2, 3, 4, 5, 6, 7>)으로 출력합니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static void main(String[] args) {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
try {
String[] numArr = br.readLine().split(" ");
int num = Integer.parseInt(numArr[0]);
int removeNum = Integer.parseInt(numArr[1]);
Queue<Integer> roundNum = new LinkedList<>();
for (int i = 1; i <= num; i++){
roundNum.add(i);
}
sb.append("<");
for(int i = 0; i < num - 1; i++){
for (int j = 0; j < removeNum - 1; j++){
roundNum.add(roundNum.remove());
}
sb.append(roundNum.remove()).append(", ");
}
sb.append(roundNum.remove()).append(">");
System.out.println(sb);
} catch (IOException e) {
throw new RuntimeException(e);
}
}
}
큐에 N까지 담고, 해당 큐에 제거한 숫자를 다시 enqueue 해준다. 그리고 해당 출력 형식을 따라 출력해 주면 된다.
마무리
개념과 문제를 연결해서 생각해 보고 풀어보니 감이 조금씩 잡히는 것 같다. 이후에도 해당 개념의 심화 문제를 풀게 된다면 추가로 해당 포스팅을 수정하여 문제를 추가해 보겠습니다.
'알고리즘' 카테고리의 다른 글
| 복잡도(시간 복잡도, 공간 복잡도) (1) | 2024.01.21 |
|---|
