Stack 과 Queue

Stack 과 Queue

---

1. Stack

   • LIFO ( Last In First Out ): 후입선출
   • 함수:
     • top
     • push
     • pop
   • 용도:
     • 복귀주소 저장시 (서브 프로그램 호출, 인터럽트 발생 등)
     • 재귀 프로그램의 순서 제어
     • 후위표기법으로 산출된 산술식 연산

2. Queue

   • FIFO ( First In First Out ): 선입선출
   • 함수:
     • put: enqueue
     • get: dequeue
   • 용도:
     • 대기행렬 처리
     • 운영체제의 작업 스케줄링

3. 문제 풀이

   • 크기가 제한된 Stack 구현하기
   • 풀기 전 확인사항
     • 스택의 갯수 제한 여부, 확장성
     • 스택에 쌓이는 접시 무더기의 경우 가중치가 다른지 (차지하는 공간이 일정한가? 아닌가?)
     • ArrayList 의 경우 insert 한 순서를 유지 하기 때문에 LinkedList 에 비해 구현이 용이할 것 같다>> ArrayList 와 LinkedList 는 데이터의 삽입, 검색의 성능 차이가 있을 뿐 ordering 과는 무관하다

   • 풀이

       class Dish{
           // int val; // 가중치가 부여된다고 생각했을 때...
       }
     
       class SimpleStack{
           int maxSize;
           ArrayList<Dish> dishList;
     
           public SimpleStack(int maxSize){
               self.maxSize = maxSize;
           }
     
           public Dish pop(){
               Dish d = dishList.get(dishList.size()-1)
               dishList.remove(dishList.size()-1)
               return d;
           }
     
           public void push(Dish d) throws Exception{
               if(dishList.size() >= maxSize){
                   throw new Exception();
               }else{
                   dishList.add(d);
               }
           }
       }
     
       public SimpleStackTest{
     
           int stackMaxSize;
           ArrayList<SimpleStack> stackList;
     
           public SimpleStackTest(int stackMaxSize){
               stackList = new ArrayList<SimpleStack>();
               stackList.add(new SimpleStack(stackMaxSize))
           }
     
           public Dish pop(){
     
               SimpleStack s = stackList.get(stackList.size()-1);
               Dish d = s.pop()
               if(s.dishList.size()==0){
                   stackList.remove(stackList.size()-1)
               }
               return d;
           }
     
           public void push(Dish d) throws Exception{
     
               SimpleStack s = stackList.get(stackList.size()-1);
               try {
                   s.push(d);
               }catch (Exception e){
                   SimpleStack s1 = new SimpleStack(stackMaxSize);
                   s1.push(d);
                   stackList.add(s1);
               }
           }
       }