[백준] 10828 스택

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

10828번: 스택

 

사실 학교 수업시간에 자료구조 시간말고는 직접적으로 이렇게 스택을 구현한 적은 거의없다. 하지만 어쨌든 스택이나 큐 모두 굉장히 많이 사용하고 중요한 자료구조임은 분명하기 때문에 복습하는 차원에서 문제를 풀어봤다. 나중에 따로 포스팅할 생각이다.

큐 구조였으면 prev 포인터 변수까지는 필요없을 것 같은데, 어쨌든 stack을 pop하면 이전 노드로 top을 옮겨줘야 하기 때문에 추가해서 구현했다.

 

---

문제 및 입출력

---

예제

---

코드

package prac;

import java.util.Scanner;

public class Main
{
     // stack 클래스
     static class stack
     {
         // stack에 사용하는 노드 클래스
          static class node
         {
               // 앞, 뒤 노드를 가리키는 포인터 변수와 value 변수
               node prev;
               node next;
               int value;

               node(int v)
               {
                    this.value = v;
               }
               node(node p, node n, int v)
               {
                    this.prev = p;
                    this.next = n;
                    this.value = v;
               }
         }

         private node top;  // stack의 꼭대기
         private int size = 0; // stack의 크기

         // stack에 새로운 노드를 삽입
         public void push(int x)
         {
              node newnode = new node(x);

              if(empty()==1)
              {
                   top = newnode;
              }
              else
              {
                   top.next = newnode;
                   newnode.prev = top;
                   top = newnode;
              }

              size++;
         }
         // stack의 맨 위에 있는 노드를 삭제하고 삭제한 노드의 값을 리턴
         public int pop()
         {
              if(empty()==1) 
              {
                   return -1;
              }
              else
              {
                   int temp = this.top.value;
                   size--;

                   if(size==0)
                   {
                        top = null;
                   }
                   else
                   {
                        top = top.prev;
                        top.next = null;
                   }

                   return temp;
              }
         }
         // stack의 top이 가리키는 노드의 값을 출력(비어있으면 -1 출력)
         public int top()
         {
              return this.empty()==1?-1:this.top.value;
         }
         // 현재 stack의 크기를 리턴
         public int size()
         {
                 return size;
         }
         // stack이 비어있으면 1, 값이 있으면 0을 출력
         public int empty()
         {
                 return this.size==0?1:0;
         }
    }
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        stack s = new stack();
        StringBuilder sb = new StringBuilder();
    
        int n = sc.nextInt();
    
        for(int i=0; i<n; i++)
        {
                String input = sc.next();
    
                // 입력받는 명령어에 따라 구현
                if(input.equals("top"))
                {
                     sb.append(s.top());
                     sb.append("\n");
                }
                else if(input.equals("size"))
                {
                     sb.append(s.size());
                     sb.append("\n");
                }
                else if(input.equals("empty"))
                {
                     sb.append(s.empty());
                     sb.append("\n");
                }
                else if(input.equals("pop"))
                {
                     sb.append(s.pop());
                     sb.append("\n");
                }
                else // stack에 push할 경우에는 출력 X
                {
                     String temp = sc.next();
                     s.push(Integer.parseInt(temp + ""));
                }    
        }
    
        System.out.println(sb.toString());
        sc.close();
    }
}