자료구조 - 큐(queue), 스택(stack), 링크드르시트(linked list)

강의 사이트 : 패스트캠퍼스 온라인강의

 

시작 전 준비

• 간단한 문제를 스스로 코드로 만들수 있어야함(ex 구구단)
• 최소 10줄의 코드는 스스로 작성할 수 있어야 함
• 파이썬 기본 문법에 익숙해져야함
• 파이썬 기초 (문제 풀이) 1~4 (www.fun-coding.org)

자료구조란? → 배열, 스택, 큐, 링크드 리스트, 해쉬 테이블, 힙 등

• 대량의 데이터를 효율적으로 관리할 수 있는 데이터의 구조를 의미
• 코드상에서 효율적으로 데이터를 처리하기 위해, 데이터 특성에 따라, 체계적을 데이터를 구조화해야 함
  → 데이터 구조 사용에 따라, 코드 효율이 달라짐
  ex) 우편번호 - 5자리 중 앞 3자리는 시, 군, 자치구, 뒤 2자리는 일련번호로 구성
        학생관리 - 학년, 반, 번호를 부여, 학생부 관리

알고리즘이란?

• 어떤 문제를 풀기 위한 절차 / 방법
• 어떤 문제에 대해, 특정한 '입력'을 넣으면, 원하는 '출력'을 얻을 수 있도록 만드는 프로그래밍

 

큐(queue) : 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조

                              FIFO(First-In, First-Out) 또는 LILO(Last-In, Last-Out)방식

                              ※ 멀티 태스킹을 위한 프로세스 스케줄링 방식을 구현하기 위해 많이 사용됨

1-1 주요 기능

• Enqueue: 큐에 데이터를 넣는 기능
• Dequeue: 큐에서 데이터를 꺼내는 기능

[Python] 

• Queue(): 가장 일반적인 큐 자료 구조
• LifoQueue(): 나중에 입력된 데이터가 먼저 출력되는 구조 (스택 구조라고 보면 됨)
• PriorityQueue(): 데이터마다 우선순위를 넣어서, 우선순위가 높은 순으로 데이터 출력

 

 

---

 

스택(stack) : 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조

                              LIFO(Last-In, First-Out)

                              ※ 컴퓨터 내부의 프로세스 구조의 함수 동작 방식

1-1 주요 기능

• push(), append(): 데이터를 스택에 넣기
• pop(): 데이터를 스택에서 꺼내기

Last In - First Out 방식

---

링크드 리스트(linked list) : 떨어진 곳에 존재하는 데이터를 화살표로 연결해서

                                                   관리하는 데이터 구조

□ 링크드 리스트의 복잡한 기능1(링크드 리스트 데이터 사이에 데이터 추가)

□ 파이썬 객체지향 프로그래밍으로 링크드 리스트 구현하기

□ 링크드 리스트의 복잡한 기능2(특정 노드 삭제)

1. head 삭제
   
   
2. 마지막 노드 삭제
   
   
3. 중간 노드 삭제
   
   
4. 더블 링크드 리스트 코드에서 노드 데이터가 특정 숫자인 노드 앞에 데이터를 추가하는 함수를 만들고, 테스트해보기