[TIL] 20230607 - 알고리즘 스택(stack)자료구조

스택(Stack) 자료구조 LIFO(Last In First Out)

스택은 흔히 프링글스에 비유가 된다. 프링글스 통 안에 감자칩이 쌓여있지만 우리는 가장 위에 있는 감자칩부터 꺼내는 수 밖에 없다. 즉, 마지막으로 넣은 것이 (맨위에 있으므로) 가장 먼저 나오는 Last In First Out(LIFO) 구조이다.

스택은 한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조이다.

스택으로 할 수 있는 가장 기본적인 연산은 스택 맨 위에 값을 넣고(PUSH), 스택 맨 위의 값을 꺼내고(POP), 스택 맨위의 값을 확인하는(PEEK) 것이다.

큐(Queue) 자료구조 FIFO(First In First Out)

음으로 들어간 친구가 처음으로 빠져나오는 FIFO(First In First Out)의 성격을 가진 자료구조다. 어떻게 보면 당연하고 합리적인 자료구조다.

 

 버블 정렬  

• 첫번째와 두번째를 비교해서 큰숫자를 뒤로.
• 두번째와 세번째비교해서 큰숫자를 뒤로 ... 반복
• 제일 큰숫자를 맨뒤에 fix 
• 다시 첫번째랑 두번째 숫자 비교부터 반복
• 배열 끝날때까지 반복

 삽입정렬 

• 삽입 정렬은 두 번째 자료부터 시작하여 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬(손안의 카드를 정렬하는 방법과 유사)
• 두 번째 자료는 첫 번째 자료, 세 번째 자료는 두 번째와 첫 번째 자료, 네 번째 자료는 세 번째, 두 번째, 첫 번째 자료와 비교한 후 자료가 삽입될 올바른 자리를 찾아 삽입
• 자료가 삽입될 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동
• 새로 삽입될 카드의 수만큼 반복하게 되면 전체 카드가 정렬됨
• 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교 하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘
• 처음 Key 값은 두 번째 자료부터 시작한다.

 

참고

https://over-stack.tistory.com/35

https://velog.io/@devjade/%EB%B2%84%EB%B8%94%EC%A0%95%EB%A0%ACbubbleSort

https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html