스택(Stack)
후입선출(LIFO:Last In First Out) 자료구조
데이터가 입력된 순서의 역순으로 처리되어야 할때 사용
-> ex) 함수 콜 스택, 수식 계산, 인터럽트(예상 치 못한 일) 처리 등
기본적으로 데이터 추가, 데이터 꺼내기, 스택 공간 확인 동작으로 이루어짐
데이터 추가(Push) : 스택의 가장 마지막 위치에 데이터 추가
데이터 꺼내기(Pop) : 스택의 가장 마지막 위치에서 데이터 꺼냄
스택 기능들 활용 예시
package org.example;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Stack stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
System.out.println(stack);
stack.pop(); // 5가 pop 됨
System.out.println(stack);
System.out.println(stack.peek()); // peek은 가장 위에 있는 값 보여줌 -> 스택에 변화 X
System.out.println(stack);
System.out.println(stack.contains(1)); // true
System.out.println(stack.size()); // 4
System.out.println(stack.empty()); // false;
stack.clear();
System.out.println(stack); // 모두 지워짐, 이상태에서 팝 하면 에러 발생
}
}ArrayList를 활용하여 Stack 구현
class MyStack1{
ArrayList list;
MyStack1(){
this.list = new ArrayList();
}
public boolean isEmpty(){
return this.list.size() == 0;
}
public void push(int data){
this.list.add(data);
}
public Integer pop(){
if(this.isEmpty()){
System.out.println("Stack is empty!");
return null;
}
// ArrayList가 Generic하게 되어있지 않아서 int로 형변환을 하지 않으면 Object 타입임!
int data = (int)this.list.get(this.list.size()-1);
this.list.remove(this.list.size() - 1);
return data;
}
public Integer peek(){
if(this.isEmpty()){
System.out.println("Stack is empty!");
return null;
}
return (int)this.list.get(this.list.size()-1);
}
public void printStack(){
System.out.println(this.list);
}
}배열을 이용한 스택 구현
class MyStack2{
int[] arr;
int top = -1;
MyStack2(int size){
arr = new int[size];
}
public boolean isEmpty(){
return this.top == -1? true: false;
}
public boolean isFull(){
return this.top == this.arr.length - 1? true: false;
}
public void push(int data){
if(this.isFull()){
System.out.println("스택이 가득찼습니다!");
return;
}
this.top += 1; this.arr[this.top] = data;
}
public Integer pop(){
if(this.isEmpty()){
System.out.println("Stack is Empty");
return null;
}
int data = this.arr[top];
this.top -= 1; // 이때 데이터 남아 있다는 점은 유의
return data;
}
public Integer peek(){
if(this.isEmpty()){
System.out.println("Stack is Empty");
return null;
}
return this.arr[top];
}
public void printStack(){
for(int i : arr){
System.out.print(i + " ");
}
System.out.println();
}
}연습문제 풀이
문제 1.문자열 뒤집기
import java.util.Stack;
// 문자열 뒤집기
// 입출력 예시 -> 입력 :"Hello" 출력 : "olleH"
// 1 3 5 7 9 -> 9 7 5 3 1
public class Practice5 {
public static String reverseString(String str){
Stack stack = new Stack();
String result = "";
for(String s : str.split("")){
stack.push(s);
}
while(!stack.isEmpty()){
result += stack.pop();
}
return result;
}
public static void main(String[] args) {
String result = reverseString("Hello");
System.out.println("result = " + result);
result = reverseString("1 3 5 7 9");
System.out.println("result = " + result);
}
}문제2. 괄호 짝 검사
public class Practice6 {
// 괄호짝 검사
private static void checkParenthesis(String str) {
Stack stack = new Stack();
boolean checkFlag = true;
for(String s : str.split("")){
if(s.equals("(")){
stack.push(s);
}else{
if(stack.isEmpty()){
checkFlag = false;
break;
}else{
stack.pop();
}
}
}
if(checkFlag && stack.isEmpty()){
System.out.println("PASS!");
}else{
System.out.println("FAIL!");
}
}
public static void main(String[] args){
// Test code
checkParenthesis("("); //FAIL
checkParenthesis(")"); //FAIL
checkParenthesis("()"); //PASS
checkParenthesis("()()()"); //PASS
checkParenthesis("(())()"); //PASS
checkParenthesis("(((()))"); //FAIL
}
}문제3. 후위표기법 연산
public class Practice7 {
public static double calculate(String str) {
Stack<Double> stack = new Stack();
for(String s : str.split(" ")) {
if(s.equals("+")){
stack.push(stack.pop() + stack.pop());
}else if(s.equals("-")){
stack.push(-stack.pop() + stack.pop());
}else if(s.equals("*")){
stack.push(stack.pop() * stack.pop());
}else if(s.equals("/")){
stack.push(1/stack.pop() * stack.pop());
}else{
stack.push(Double.parseDouble(s));
}
}
return stack.pop();
}
public static void main(String[] args) {
//Test code
System.out.println(calculate("2 2 +")); // 4
System.out.println(calculate("2 2 -")); // 0
System.out.println(calculate("2 2 *")); // 4
System.out.println(calculate("2 2 /")); // 1
System.out.println(calculate("1 1 + 2 * 3 * 2 / 5 -")); // 1
System.out.println(calculate("5 2 * 3 - 8 * 4 /")); // 14
}
}마이너스 부분과 나누기 부분 유의해서 보자!
문제4. 문자열 비교
// 두 문자열 비교 -> 단 #는 바로 이전에 문자를 삭제하는 기능이라 가정
// 입출력 예시 -> 입력 s1:"tree", s2:"th#ree" -> true
// 입력 s1 = "ab#a", s2 = "aab#" -> true
// 입력 s1 = "wo#w", s2 = "ww#o" -> false
public class Practice8 {
public static boolean stringCompare(String s1, String s2){
String s1After = doBackSpace(s1);
String s2After = doBackSpace(s2);
return s1After.equals(s2After);
}
public static String doBackSpace(String s){
Stack stack = new Stack();
for(char c : s.toCharArray()){
if(c == '#' && !stack.isEmpty()){
stack.pop();
}else{
stack.push(c);
}
}
return String.valueOf(stack);
}
public static void main(String[] args) {
//Test code
System.out.println(stringCompare("tree", "th#ree"));
System.out.println(stringCompare("ab#a", "aab#"));
System.out.println(stringCompare("wo#w", "ww#o"));
}
}추가 정리
스택은 맨 위에다가 뭘 쌓고 빼거나, 맨 위에 뭐가 있는지에만 관심을 가질 때 주로 사용
스택이라면, 자료구조 시간에 반드시 등장하는! 올바른 괄호 문자열 판단
괄호 문자열은 다음과 같은 규칙으로 재귀적으로 생성됨
- 빈 문자열, (), []은 괄호 문자열
- S,T가 괄호 문자열이면 ST도 괄호 문자열
- S과 괄호 문자열이면 (S), [S]도 괄호 문자열
올바른 괄호 문자열 판단 방법
- 여는 괄호를 볼때마다 스택에 push를 함
- 닫는 괄호를 볼때마다 스택의 top과 비교하고, 종류가 맞으면 스택을 pop. 종류가 맞지 않다면, 올바르지 못한 괄호 문자열
- 1~2번을 문자열 왼쪽부터 오른쪽으로 훑으면서 반복하고, 마지막 문자까지 처리했는데 스택이 비어있지 않다면 올바르지 못한 괄호 문자열
2번 예시 : ( ], (()], ), ())
3번 예시 : (( )
위와 같은 조건이 통하는 이유는 괄호식이 바깥쪽으로 이어 붙어져 확장되어 나가는 구조이기 떄문
-> 즉 지금 닫는 괄호를 보았다면, 그것은 반드시 최근에 연 괄호를 닫기 위한 것
-> 최근에 연 괄호와 종류가 맞다면 정상적인 것이고, 아니라면 잘못된 문법
Journey for Backend Developer