Stack 과 Queue
Stack
- LIFO ( Last In First Out ): 후입선출
- 함수:
- top
- push
- pop
- 용도:
- 복귀주소 저장시 (서브 프로그램 호출, 인터럽트 발생 등)
- 재귀 프로그램의 순서 제어
- 후위표기법으로 산출된 산술식 연산
Queue
- FIFO ( First In First Out ): 선입선출
- 함수:
- put: enqueue
- get: dequeue
- 용도:
- 대기행렬 처리
- 운영체제의 작업 스케줄링
문제 풀이
- 크기가 제한된 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); } } }
