SEB_BE 23일차 - 자료구조 (Stack,Queue)

Daily coding

//2 거듭제곱 여부
long result = 2;
while (num > result) { // 결과변수에 2 할당 후 num이 result보다 큰 경우에 2곱하기
	result *= 2;
}
return result == num;

💡 오늘의 학습목표

• 자료구조
• Stack
• Queue

📔 자료구조

• 여러 데이터의 묶음을 저장하고, 사용하는 방법을 정의한 것
• 자주 쓰이는 자료구조 Stack Queue Tree Graph

📔 Stack

• 쌓다. 쌓이다 / 데이터를 순서대로 쌓는 자료구조
• 입력과 출력이 하나의 방향으로 이루어지는 제한적 접근
• LIFO(Last In First Out) 후입선출 / FILO (First In Last OUT) 선입후출
• 데이터를 넣는 것을 PUSH 꺼내는 것을 POP
• 데이터는 하나씩 넣고 뺄 수 있다.

// 스택에 차례대로 숫자 넣기
Stack<Integer> stack = new Stack<>(); //Integer형 스택 선언하기
stack.push(1); // 데이터 넣기
stack.push(2);
stack.push(3);
stack.push(4);
-------------------
1 <- 2 <- 3 <- 4
// 스택에서 데이터를 전부 빼내기
stack.pop();
stack.pop();
stack.pop();
stack.pop();
--------------------
4, 3, 2, 1 마지막 데이터부터 차례대로 나오게 된다.

• 브라우저의 뒤로 가기, 앞으로 가기 기능

  1. 새로운 페이지 접속 시, 현재 페이지를 Prev Stack에 보관
  2. 뒤로 가기 시 현재 페이지를 Next Stack에 보관하고 Prev Stack에 가장 나중에 보관된 페이지를 현재페이지로 가져오기
  3. 앞으로 가기 시 Next Stack의 가장 마지막으로 보관된 페이지 가져오기
  4. 현재 페이지를 Prev Stack에 보관

• ArrayList로 자료구조 Stack 구현하기

//미리 정의된 ArrayStack 객체 사용
ArrayListStack stack = new ArrayListStack();

stack.push(1);
stack.push(2);
stack.push(3); // [1, 2, 3]

System.out.println(stack.show()); // [1, 2, 3]

stack pop(); // [1, 2]
stack pop(); // [1]

System.out.println(stack.show()); // [1]

---

📔 Queue

• 줄을 서서 기다리다 / 대기 행렬
• FIFO(First In First Out) 선입선출 / LILO(Last In Last Out) 후입후출
• 입력과 출력의 방향 고정/ 두 곳으로 접근 가능
• 데이터를 넣는 것을 enqueue 데이터를 꺼내는 것을 dequeue
• 데이터가 입력된 순서대로 처리할 때 주로 사용
• 데이터는 하나씩 넣고 뺄 수 있다.

// 데이터를 차례대로 큐에 넣기
Queue<Integer> queue = new LinkedList<>(); // int형 queue 선언

queue.add(1); // queue에 데이터 1 추가
queue.add(2);
queue.add(3);
queue.add(4);
                                 add(데이터)
출력 방향<--------------------------<입력방향
              1 <- 2 <- 3 <- 4
// 큐가 빌 때까지 데이터 전부 빼내기
queue.poll(); // queue에 첫번째 값을 반환하고 제거
queue.poll();
queue.poll();
queue.poll();
                                  poll()
출력방향<----------------------------<입력방향

// 1, 2, 3, 4 제일 첫번째 데이터부터 차례대로 나온다.

• 프린터 인쇄

  1. 문서 출력을 누르면 해당 문서는 인쇄 작업 queue에 들어간다.
  2. 프린터는 인쇄 작업 queue에 들어온 문서를 순서대로 인쇄

• 속도의 차이나 시간차이를 극복하기 위해 임시기억장치의 자료구조로 Queue 사용
  버퍼(buffer)

• CPU는 빠른 속도로 인쇄에 필요한 데이터를 만든 다음 Queue에 저장하고 다른 작업 수행

• ArrayList로 자료구조 Queue 구현하기

  // 미리 정의된 ArrayQueue 객체 사용
  ArrayQueue queue = new ArrayQueue(5);
  
  queue.add(1);
  queue.add(2);
  queue.add(3); // [1, 2, 3]
  
  System.out.println(queue.show()); // [1, 2, 3]
  
  queue.pull(); // [2, 3]
  queue.pull(); // [3]
  
  System.out.println(queue.show()); // [3]

  ---

• 페이지 앞 뒤 이동 (Stack)
  

• 프린터 (Queue)