Stack

본 문서는 2021년 12월 31일 에 작성되었습니다.

이론적인 부분을 보완하여 재작성하게 되었습니다.
Dev 알고리즘 시리즈 중 자료구조 Doc 을 읽고 와주시면 감사하겠습니다.

---

Stack 이란?

Stack 은 다음과 같은 특징을 가지고 있는 자료구조입니다.

1. LIFO (last in first out)
   1.1. 샌드위치처럼 데이터가 쌓이는 구조이며, 가장 마지막에 넣은 원소부터 꺼내야 한다.
2. DELETE 연산에서 삭제되는 원소가 정해져 있다.
3. INSERT 연산을 PUSH 라고 한다.
4. DELETE 연산을 POP 이라고 부른다.

이러한 Stack 의 핵심 프로시저는 다음과 같습니다.
단 실제로 자료구조 라이브러리에 만들어져있는 메서드의 수는 이보다 훨씬 많습니다.

1. STACK EMPTY | 원소가 없는지 확인한다
2. PUSH | 새 원소를 마지막 자리에 넣는다
3. POP | 마지막 원소를 꺼낸다

아래의 프로시저에서 S 는 Stack(스택형 배열)을 의미한다.

# STACK EMPTY (S)

Stack 의 맨 위(마지막 원소)가 0인지를 확인합니다.
0이라면 TRUE(비어있음)을 반환하며,
0이 아니마련 FALSE(꽉차있음)을 반환합니다.

STACK EMPTY (S)

   if S.top==0
      return TRUE
   else
      return FALSE

# PUSH (S,x)

Stack 의 길이를 하나 늘리고
Stack 의 맨위에 x를 넣습니다.

O(1) 의 시간복잡도를 가집니다.

PUSH (S, x)

   S.top=S.top +1
   S[S.top]=x

# POP (S)

STACK EMPTY 를 실행하여
TRUE 라면 에러를 던지고
FALSE 라면 꺼낸 값을 리턴 하고 길이를 1줄인다.

O(1) 의 시간복잡도를 가집니다.

POP (S)

   if STACK EMPTY (S)
      error "Stack 비어있음"
   else
      S.top=S.top-1
      return S[S.top+1]

---

Java 에서 Stack 은?

Java(jdk 1.8 이후) 에서는 Collection Framework 를 통해서,
Stack 을 구현해두었다.

이를 참고하여 사용하여도 괜찮지만,
Primitive Type 이 아닌 Wrapper Class 와 Generics 를 사용하기 때문에,
퍼포먼스가 신경쓰이고 Primitive 를 다룬다면 별도의 Stack 클래스를 만들어보는 것도 좋을 것 같다.

---

본 문서는 2021년 11월 24일 에 작성되었습니다.

스택(구버전)

스택이란?
스택은 한쪽 끝에서만 자료를 넣고 뺼 수 있는 자료구조이다.

사용 사례

• 재귀 알고리즘
• 웹 브라우저의 방문기록(뒤로가기)
• 실행취소
• 역순 문자열 만들기
• 수식의 괄호 검사
• 후위 표기법 계산

출처 : 티스토리 블로그

---

기본 구현

public class Main(){
  public static void main(Strinng[] args){
    int stack[10000];
    int size=0;
  }
  void push(int data){
    stack[size]=data;
    size+=1;
  }
  void pop(int data){
    stack[size-1]=0;
    size-=1;
  }
}

---

문제리스트

https://www.acmicpc.net/problem/10828
https://www.acmicpc.net/problem/9093
https://www.acmicpc.net/problem/9012
https://www.acmicpc.net/problem/1874
https://www.acmicpc.net/problem/1406

깃 저장소

https://github.com/unchaptered/21-11-algorithm-codeup/tree/main/src/acmicpc_stack

---

풀이방법

10828 번 (stack 을 이용한 풀이)

import java.io.*;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader scan=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter pen = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer spliter;
        
        String inputText="";
        String inputArr[]=new String[2];
        int length=Integer.parseInt(scan.readLine()); // 버리기.
        
        int stack[]=new int[length];
        int size=0;
        while(length!=0) {
        	inputText=scan.readLine();
        	spliter=new StringTokenizer(inputText," ");
        	inputArr[0]=spliter.nextToken();
        	if(inputArr[0].equals("push")) {
        		inputArr[1]=spliter.nextToken();
        	}
        	switch(inputArr[0]) {
        	case "push":
        		stack[size]=Integer.parseInt(inputArr[1]);
        		size++;
        		break;
        	case "top":
        		if(size>0) {
            		pen.write(stack[size-1]!=0 ? stack[size-1]+"\n" : -1+"\n");
        		}else {
        			pen.write("-1\n");
        		}
        		break;
        	case "size":
        		pen.write(size+"\n");
        		break;
        	case "pop":
        		if(size>0 && stack[size-1]!=0) {
        			pen.write(stack[size-1]+"\n");
        			stack[size-1]=0;
        			size--;
        		}else {
        			pen.write(-1+"\n");
        		}
        		break;
        	case "empty":
        		pen.write(size==0 ? 1+"\n" : 0+"\n");
        		break;
        	}
        	length--;
        }
        pen.flush();
	}
}

9093 번 (stack 을 이용한 풀이)

import java.util.Stack;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader scan=new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter pen=new BufferedWriter(new OutputStreamWriter(System.out));
		
		int length=Integer.parseInt(scan.readLine());
		Stack<Character> stack=new Stack<Character>();
		
		while(length-- > 0) {
			String input=scan.readLine()+"\n";
				for(char ch : input.toCharArray()) {
					if(ch==' '||ch=='\n') {
						while(!stack.empty()) {
							pen.write(stack.pop());
						}
						pen.write(ch);
					}else
						stack.push(ch);
				}
		}
		pen.flush();
	}
}

9012 번 (math, stack 을 이용한 풀이)

1. math 를 이용한 풀이

import java.io.*;

public class No9012 {
	public static void main(String[] args) throws IOException {
		BufferedReader scan=new BufferedReader(new InputStreamReader(System.in));
		
		int length=Integer.parseInt(scan.readLine());
		int count=0;
		boolean deadFlag=false;
		boolean vps=false;
		for(int i=0; i<length; i++) {
			count=0;
			deadFlag=false;
			vps=false;
			char inputText[]=scan.readLine().toCharArray();
			for(int j=0;j<inputText.length;j++) {
				if(count<0) {
					deadFlag=true;
				}
				switch(inputText[j]) {
				case '(':
					count++;
					break;
				case ')':
					count--;
					break;
				default:
					vps=false;
				}
			}
			vps=(deadFlag) ? false : (count==0) ? true : false;
			System.out.println(vps==true ? "YES" : "NO");
		}
	}
}

2. stack 을 이용한 풀이 이건 다른사람코드임...

import java.util.*;
public class Main {
    public static String isValid(String s) {
        int n = s.length();
        int cnt = 0;
        for (int i=0; i<n; i++) {
            if (s.charAt(i) == '(') {
                cnt += 1;
            } else {
                cnt -= 1;
            }
            if (cnt < 0) {
                return "NO";
            }
        }
        if (cnt == 0) {
            return "YES";
        } else {
            return "NO";
        }
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        while (n-- > 0) {
            System.out.println(isValid(sc.next()));
        }
    }
}

1874 번 (stack 을 이용한 문제풀이)

1. stack 을 이용한 문제풀이

import java.util.*;
import java.io.*;

// https://www.acmicpc.net/problem/1874

public class No1874 {
	public static void main(String[] args) throws IOException {
		Scanner scan=new Scanner(System.in);
		
		int length=scan.nextInt();
		int arr[]=new int[length];
		for (int i=0; i<length; i++)
			arr[i]=scan.nextInt();
		
		scan.close();
		stackCalculator(arr);
	}
	public static void stackCalculator(int arr[]) throws IOException {
		StringBuilder pen= new StringBuilder();
		
		int length=arr.length;
		int nowNumber=0;
		Stack<Integer> stack=new Stack<Integer>();
		for(int i=0; i<length; i++) {
			if(arr[i]>nowNumber) {
				/* 4라고 하면 4의 값을 출력해야함...
				 * 4와 nowNumber 가 동일해질때까지 push 하고 동일해지면 pop
				*/
				while(arr[i]>nowNumber) {
					stack.push(++nowNumber);
					pen.append("+\n");
				}
				stack.pop();
				pen.append("-\n");
			} else {
				/* 이 문제의 유일한 반례가 여기에 있다.
				 * 오름차순으로 stack 에 넣고 있기 때문에 단절된 호출이 불가능하다.
				 * 5 를 호출하고 3을 호출하려면 "반드시" 중간값인 4를 호출해야한다.
				 * idea 1
				 * 출력을 시작할 값(더 큼) arr[i]과 그 다음 출력값 arr[i+1]의
				 * 차이가 2 이상이면 NO 를 출력한다.
				 * failed
				 * 1. arr[i] 와 arr[i+1] 이 아니라, stack.top() 과 비교해야함.
				 * 2. 그리고 stack.top() 이 나오는 시점에 출력되니까.. arr[i+1] 이 아니라,
				 * 	arr[i] 와 비교해야하고 두 값이 동일해야함...
				 */
				if(stack.peek()!=arr[i]) {
					System.out.println("NO");
					return;
				}
				stack.pop();
				pen.append("-\n");
			}
		}
		System.out.println(pen);
	}
}