[Java] 자바 #32, Stack, Queue 개념 및 기능

Stack, Queue

Stack 스택

- 자료구조 중 하나

- 후입선출

- LIFO( Last In First Out )

0. 객체 생성

Stack<String> stack = new Stack<String>();

1. 요소삽입

stack.push("빨강");

stack.push("파랑");

stack.push("노랑");

2. 요소 제거

- 값 반환과 동시에 요소를 제거

- 반환은 가장 나중에 넣은 "노랑" 부터...

System.out.println(stack.pop()); //노랑

System.out.println(stack.size()); // 2

System.out.println(stack.pop()); // 파랑

System.out.println(stack.size()); // 1

System.out.println(stack.pop()); // 빨강

System.out.println(stack.size()); // 0

if (!stack.isEmpty()) {

System.out.println(stack.pop());

System.out.println("진행");

}

예제 진행을 위해 다시 삽입.

stack.push("하나");

stack.push("둘");

stack.push("셋");

3. 요소 반환

- peek()

- pop을 하면 제거될 값 

- 가장 최근에 넣은 값

- 그냥 반환만.

System.out.println(stack.peek()); //셋

System.out.println(stack.size());

4. 각종 기능들.

System.out.println(stack.contains("둘")); //"둘"이라는 문자열이 있는가.

System.out.println(stack.isEmpty()); //스택이 비어있는가

System.out.println(stack.toString()); //스택안에 들어있는 요소들 출력 => [ 하나, 둘, 셋 ]

stack.trimToSize();  //모든 컬렉션은 trimToSize() 존재

System.out.println(stack.size());

5. 초기화

stack.clear();

System.out.println(stack.size());

Stack을 이용한 브라우저 History 예제

class Browser{
    public Stack<String> back;//이전방문기록
    public Stack<String> forward; //다음 방문기록
    
    public Browser() {
        this.back = new Stack<String>();
        this.forward = new Stack<String>();
    }
    
    //주소를 입력하면 사이트 방문.
    public void goUrl(String url) {
        System.out.println(url+"접속함");
        back.push(url);
    }
    //방문 기록 확인하기
    public void history() {
        if(!back.isEmpty()&&forward.isEmpty()) {
            
        }
        System.out.println("====================");
        System.out.println("back : "+back);
        System.out.println("now : "+back.peek());
        System.out.println("forward : "+forward);
        System.out.println("====================");
    }
    
    //뒤로가기
    public void goBack() {
        if(!back.isEmpty()) {
            //back -> (요소1개) ->forward
            forward.push(back.pop()); //옮기기
        }
        
    }
    
    //앞으로가기
    public void goForward() {
        if(!back.isEmpty()) {
            //back -> (요소1개) ->forward
            back.push(forward.pop());
        }    
    }
}
 

public class ExClass {
    public static void main(String[] args) {
        //Stack
        // - 브라우저 히스토리.
        Browser b = new Browser();
        b.goUrl("구글");
        b.goUrl("네이버");
        b.goUrl("다음");
        
        b.goBack();
        b.goForward();
        
        b.history();
    
    }
}

Queue 큐

- 자료구조 중 하나

- 선입선출

- FIFO( First In First Out )

0. 객체 생성

Queue<String> queue = new LinkedList<String>();

1. 요소 추가

queue.add("빨강");

queue.add("파랑");

queue.add("노랑");

System.out.println(queue.size());

2. 요소 접근 및 반환

String color = queue.poll(); 

System.out.println(color);

System.out.println(queue.size());

System.out.println(queue.poll());

System.out.println(queue.poll());

System.out.println(queue.poll());

queue.add("빨강");

queue.add("주황");

queue.add("노랑");

queue.add("초록");

queue.add("파랑");

queue.add("남색");

queue.add("보라");

4. 루프탐색

- 일반포문 , 향상된 포문(X) , while

for(String str : queue) {

System.out.println(str);

}

System.out.println(queue.size());

while(true) {

System.out.println(queue.poll());

if(queue.size()==0) {

break;

}

}

while(queue.size()>0) {

System.out.println(queue.poll());

}

queue.clear();

queue.contains(o)

System.out.println(queue.isEmpty());;

queue.remove();

System.out.println(queue.peek()); 

System.out.println(queue.size());

System.out.println(queue.peek()); 

int size = queue.size();

for(int i =0; i<size;i++) {

System.out.println(queue.poll());

}

ArrayList<String> list = new ArrayList<String>();

list.add("데이터"); //x100회

for(int i =0; i<list.size();i++) {

System.out.println(list.get(i));

if() {

list.remove(i);

}

}

임의로 Queue 구현 예제 

구현할 것.

1. void add(String value)

2. int size()

3. String poll() //빼는거.

4. peek() // 가져오되 없애지 않고 가져오는것.

5. clear() //초기화.

6. 배열의 길이를 가변으로 구현.(큐 객체 생성 직후는 배열이 없음 -> 첫 add 호출때 4칸짜리 배열 생성.)

7. void trimToSize()

class MyQueue{
    private int index;
    private String[] list;
    private int pollIndex=0;
    
    public MyQueue() {
        this.index=-1;
    }
    public MyQueue(int initialCapacity) {
        this.index=-1;
        this.list = new String[initialCapacity];
    }
    
    public void add(String value) {
        this.index++;
        
        //초기 인덱스가 0 일때.
        if(this.list==null) {
            list=new String[4];
        }
        
        //인덱스가 리스트의 최대값에 도달할 때!!!!!!
        if(this.index==list.length) {    
            String[] temp = new String[list.length*2]; //2배 긴 임시 배열을 생성
            
            for(int i =0; i<list.length;i++) {
                temp[i]=list[i]; //1대1 딥 카피
            }
            
             //리스트의 길이를 다시 초기화.
            list=new String[temp.length];
            
            for(int i =0; i<list.length;i++) {
                list[i]=temp[i]; // 다시 list에 딥카피해준다.
            }
        }
        list[index]=value;
    }
    
    public int size() {
        return this.index+1;
    }
    
    //빼면서 앞으로 한칸씩 이동. 인덱스 감소
    public String poll() { 
        //
        String temp=list[pollIndex];
        for(int i = pollIndex; i<=this.index;i++) {
            list[i]=list[i+1];
        }
        this.index--;
        return temp;
    }
    
    public String peek() {
        return list[pollIndex];
    }
    
    public void clear() {
        
        for(int i =0; i<=this.index;i++) {
            list[i]=null;
        }
        this.index=-1;
    }
    
    public void trimToSize() {
        System.out.println("trimToSize 초기 사이즈 : "+list.length);
        String[] temp = new String[size()];
        for(int i =0; i<temp.length;i++) {
            temp[i]=list[i];
        }// 딥카피 종료
        list=new String[temp.length];
        //다시 딥카피
        for(int i =0; i<temp.length;i++) {
            list[i]=temp[i];
        }//딥카피 종료.
        System.out.println("trimToSize 호출 후 사이즈 : "+list.length);
    }
}