[Section 02] 자료구조 - 스택, 큐

1️⃣ 굿모닝 세션

---

스택이랑 큐를 학습하게 된다. 자바에서는 이미 stack클래스와 queue 인터페이스로 구현되어 있다. 연습문제에서는 자료구조의 특성을 잘 이해하기 위해 직접 구현해본다. 스택이랑 큐를 어디서 많이 사용되는가? 선입선출/후입선출

알고리즘 문제는 많이 풀어보세요.

Deque라는 자료구조를 쓰면 비용이 비싸다. 효율적인 관리를 위해 자료구조를 사용하는 것임을 기억할 것.

 

내 코드에서 잘못된 점 찾기 지금 상황에서 가장 좋은 해결 방법 -> 물어보기

앞으로 개발자가 되려면 좋은 질문을 할 줄 알아야합니다. 

접속했던 링크들도 같이 보내줘야 한다 : 해결법 제안 시 용이하다고 합니다.

 

난 여기 개발자가 되려고 온거다. 학생이 아니다! 열심히 하자 

 

 

2️⃣ 데일리 코딩

---

수를 입력받아 2의 거듭제곱인지 여부를 boolean으로 리턴합니다. 2의 거듭제곱이라는 큰 값을 다루기 때문에 int형 대신 long형을 사용합니다.

 

• long 타입의 정수
  • 변수의 타입은 참조형과 8개의 기본형이 있다. 
  • 정수형은 int와 long만 기억하면 된다(내 뇌피셜)
  • 대게 int를, 20억이 넘을 땐 long을 사용한다. 

8가지 기본형의 타입과 분류

• 산술 연산자
  • 내가 이상한건지 ' / '와 ' % '가 항상 헷갈린다.
  • / 는 몫 %는 나머지
• while문
  • for문에 비해 간단한 구조를 가지고 있다.
  • 조건식을 평가해서 조건식이 거짓이면 문장 전체를 벗어나고, 참이면 블럭 { }내의 문장을 수행하고 다시 조건식으로 돌아간다. 조건식이 거짓이 될 때까지 이 과정을 계속 반복한다. 
  • 초기화나 증감식이 필요하지 않은 경우라면, while문이 더 적합하다.
  • break문은 자신이 포함된 가장 가까운 반복문을 벗어난다.

while(조건식){
	조건식의 연산결과가 '참'인 동안, 반복될 문장들을 작성한다.
}

--------------
for문과 while문의 비교
--------------
for(int i=1;i<=10;i++){
	System.out.println(i);
}
--------------
int i=1;
while(i<=10){
	System.out.println(i)
    i++;
}

    // 2의 거듭제곱인 num은 2를 계속 곱하다보면 언젠간 도달하게 된다.
    // 부호는 <로 표시...중요 계속 생각
    long powered=2;
    while(powered<num){
      powered=powered*2;
    }
    return powered==num;

 

3️⃣ 학습 콘텐츠

---

자료구조란 여러 데이터의 묶음을 저장하고, 사용하는 방법을 정의한 것입니다.
자주 등장하는 네 가지의 자료구조
Stack, Queue, Tree, Graph

데이터 그 자체만으로는 의미가 없다. 데이터를 분석하고 활용해야만 의미를 가질 수 있다. 데이터를 체계적으로 정리하여 저장해두는 게, 데이터를 활용하는 데 있어 훨씬 유리하고 이미 여러 방법을 연구해 자료구조라는 이름을 붙여두었다. 

자료구조의 종류와 구분

Stack, 스택

쌓다. 쌓이다. 포개지다.

데이터를 순차적으로 쌓는 자료구조이다. 후입선출로 가장 나중에 들어간 데이터가 가장 먼저 나온다. 

• 입력과 출력이 하나의 방향으로 이루어지는 제한적 접근이 특징이다. 입출력 방향이 여러개면 Stack이 아니다.
• LIFO(Last In First Out), FILO(First in Last Out)이라고 부르기도 한다.
• Stack에 데이터를 넣는 것을 'PUSH', 꺼내는 것을 'POP'이라고 한다.
• 데이터가 아무리 많이 있어도 하나씩 넣고 뺄 수 있습니다. 한꺼번에 여러개 불가능

// Integer형 스택 선언
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
---------
1 2 3
---------

// 스택이 빌 때까지 데이터 전부 빼내기
stack.pop();
stack.pop();
stack.pop();

---------
3 2 1 
---------

 

✔ 대표적인 예

브라우저의 뒤로 가기, 앞으로 가기 기능을 구현할 때 Stack 사용.

두개의 Stack을 사용한다. Prev, Next

1. 새로운 페이지에 접속할 때, 현재 페이지를 prev Stack에 계속 저장합니다.

2. 뒤로 갈때 현재 페이지는 Next Stack에 저장하고, Prev Stack 에 맨 나중에 저장된 페이지를 불러옵니다.

3.  앞으로 갈때는 현재 페이지는 Prev Stack에 저장하고, Next Stack의 가장 나중에 저장된 페이지를 불러옵니다.

 

현재 페이지, Prev Stack, Next Stack 이렇게 세가지 상황을 중점으로.

 

자료구조는 자료(데이터)를 다루는 구조 그 자체를 뜻합니다. 구현하는 방식에는 제약이 없습니다. 따라서 사용자 정의로 직접 클래스를 구현하든, Java에서 제공하는 Stack을 사용하든 상관 없습니다. 다만, 시간을 절약할 수 있다는 장점이 있습니다.

 

Queue, 큐

줄을 서서 기다리다. 대기행렬.

Stack과 반대되는 개념. 먼저 들어간 데이터가 먼저 나온다. 

• FIFO(First In Last Out), LILO(Last In Last Out)이라고 부르기도 한다.
• 입력과 출력의 방향이 다르다. 두 곳으로 접근이 가능하다. 
• Queue에 데이터를 넣는 것을 'enqueue', 데이터를 꺼내는 것을 'dequeue'라고 한다.
• 입력된 순서대로 처리할 때 주로 사용한다. 아무리 데이터 양이 많아도 한깨씩 넣고 빼기 가능. 

// int형 queue선언하기
Queue<Integer) queue = new LinkedList<>();

queue.add(1);
queue.add(2);
queue.add(3);
----------
1 <- 2 <- 3
----------

// 큐가 빌 때까지 데이터 전부 빼내기
queue.pull();
queue.pull();
queue.pull();

----------
1 2 3 
----------
// 제일 첫 번째에 있는 데이터부터 차례로 나오게 됩니다.

✔ 대표적인 예

컴퓨터에서 광범위한 활용. 컴퓨터와 연결된 프린터에서 여러 문서를 순서대로 인쇄하기

컴퓨터 장치들 사이에서 데이터를 주고받을 때, 각 장치 사이에 존재하는 속도의 차이나 시간 차이를 극복하기 위해 임시 기억 장치의 자료구조로 queue를 사용한다. 이것을 통틀어 buffer라고 한다. 불규칙적으로 발생한 이벤트를 규칙적으로 처리하기 위해 버퍼를 사용한다. 

컴퓨팅에서 버퍼는 데이터를 한 곳에서 다른 한 곳으로 전송하는 동안 일시적으로 그 데이터를 보관하는 메모리의 영역이다. 버퍼링이란 버퍼를 활용하는 방식 또는 버퍼를 채우는 동작을 말한다. 다른 말로 '큐'라고도 표현한다.

 

4️⃣ 문제풀이

---

 

연습문제 1, 2번

ArrayList를 사용하여 직접 스택과 큐를 구현하기. 

// 어레이리스트 선언하기
private ArrayList<Integer> listStack=new ArrayList<>();
private ArrayList<Integer> listQueue= new ArrayList<>();

연습문제 3, 4, 5번

 

앞에서 말했듯이 자료구조는 데이터를 다루는 방식이다. 저장한 데이터를 어떻게 다루는지에 따라 이름이 붙여진 것이다! 어떻게 정의하든 상관없다.  연습문제에서는 ArrayList로 만들어서 사용자 정의 함수로 선입선출, 후입선출을 구현했다.

 

---

ArrayList와 Array

ArrayList는 컬렉션 프레임워크에서 가장 많이 사용되는 컬렉션 클래스이다.ArrayList는 Array인터페이스를 구현하기 때문에 데이터의 저장순서가 유지되고, 중복값 저장이 가능하다. 

	Array	ArrayList
사이즈	초기화 시 고정. int [] arr= new int[3];	초기화 시 사이즈를 표시하지 않음. 크기가 가변적이다. ArrayList<Integer> arrList=new ArrayList<>();
속도	초기화시 메모리에 할당되어 ArrayList보다 속도 빠름.	데이터 추가, 삭제 시에 메모리를 재할당하기 때문에 속도가 Array보다 느림.
크기 변경	사이즈 변경 불가	추가, 삭제 가능 add(), remove()
다차원	int [][][] multiArr=new int[3][3][3];	불가능

toString

모든 클래스의 가장 최상위 클래스인 "Object"클래스.

자바 라이브러리나 유저가 만든 클래스는 모두 "Object"클래스를 부모 클래스로 상속 받아서 사용.

이 Object 클래스가 가진 메소드 중에 "toString"메소드가 있다. 이는 객체가 가지고 있는 정보나 값들을 문자열로 만들어 리턴한다.

var o = new Object();
o.toString(); // [object Object] 반환

Stack

자바에서 스택은 java.util.Stack을 import 하여 사용합니다.

// Stack 선언
Stack<Integer> stack1=new Stack<>(); // int형 스택선언
Stack<String> stack2=new Stack<>(); // String형 스택선언

stack1.push(1); // 값 추가
stack1.pop(); // 마지막 값 제거하여 반환
stack1.clear(); // 초기화
stack1.peek(); // 가장 상단의 값 출력

stack.push(1);     // stack에 값 1 추가
stack.push(2);     // stack에 값 2 추가
stack.size();      // stack의 크기 출력 : 2
stack.empty();     // stack이 비어있는제 check (비어있다면 true)
stack.contains(1) // stack에 1이 있는지 check (있다면 true)

 

push( ) vs add( ) 차이

push()는 stack에서 제공, add()는 List에서 제공하는 메서드이다.

push()의 리턴값은 <E>이고, add()의 리턴값은 boolean이다.

​

잔잔한 차이점이 있지만 stack을 써서 코드를 짜고 있다면 push() 메서드를 사용하자.
나중에 봤을 때 stack을 써서 구현했다는걸 명확하게 알 수 있기 때문이다.

 

 

🆒 느낀 점

---

배고프다... 다이어트를 열심히 해야지. 다이어트를 열심히 해야 공부 의지도 살아나는 느낌이다. 난 정말 요상해 😀

 

Art