[패스트캠퍼스 수강 후기] {코딩테스트인강} 100% 환급 챌린지 5 회차 미션

10. 스택

-> 데이터를 제한적으로 접근할 수 있는 구조

= 한쪽 끝에서만 자료를 넣어거나 뺄 수 있는 구조

-> 가장 나중에 쌓은 데이터를 가장 먼저 뺄 수 있는 데이터 구조

= 큐 : FIFO 정책

= 스택은 LIFO 정책

A. 스택구조

-> 스택은 LIFO 또는 FILO 데이터 관리 방식을 따른다

     LIFO = Last In, First Out = 마지막에 넣은 데이터를 가장 먼저 추출하는 데이터 관리

     FILO = First In, Last Out = 처음에 넣은 데이터를 가장 마지막에 추출하는 데이터 관리

-> 대표적인 스텍 활용

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

-> 주요 기능

     push( )  : 데이터를 스택에 넣기

     pop( ) :  데이터를 스택에서 꺼내기

B. 스택 구조와 프로세스 스택

-> 스택 구조는 프로세스 실행 구조의 가장 기본

     -함수 호출시 프로세스 실행 구조를 스택과 비교해서 이해 필요

-> 재귀 함수

  def recursive(data) :  //data의 값을 받아서

     if data < 0:  //만약 data가 0보다 작으면

             print(“ended”)  // “ended”를 출력

              else:  // 아닐경우

                print(data)  // data 출력

                recursive(data -1)  // recursive함수에 data에서 1 뺀것을 넣어

                print(“returned”, data)

C. 자료구조 스택 장단점

   장점

-> 구조가 단순해서 구현이 쉽다

-> 데이터 저장과 읽기 속도가 빠르다

   단점 ( 일반적인 스택 구현 시)

-> 데이터 최대 개수를 미리 정해야 한다

    - 파이썬의 경우 재귀 함수는 1000번까지만 호출이 가능합니다

-> 저장 공간의 낭비가 발생할 수 있다

    - 미리 최대 개수만큼 저장 공간을 확보해야 한다

== 스택은 단순하고 빠른 성능을 위해 사용되어 보통 배열 구조를 활용해서 구현하는 것이 일반적이다.

      이 경우 위에서 열거한 단점이 있을 수 있다

D. 파이썬 리스트 기능에서 제공하는 메서드로 스택 사용

-> append ( push) , pop 메서드 제공

  data_stack = list( )

  data_stack.append(1)

  data_stack.append(2)

  data_stack // data_stack에 있는 1,2를 리스트로 출력

  data-stack.pop ( ) // LIFO 정책에 따라 data_stack 마지막에 넣은 값을 출력

E. EXAMPLE

->  리스트 변수로 스택을 다루는 POP, PUSH 기능 구현하기

-> POP PUSH 함수 사용하지 않고 직접 구현

     stack_list = list( ) //stack_list라는 변수로 list로 생성

     def push(data) :  // push 함수 선언

             stack_list.append(data)

    def pop():  //pop 함수 선언

    data = stack_list [-1]

    del stack_list[-1]

     return data

  for index in range(10):

              push(index)

      pop( )  // 출력 : 9  

 

11.1 Linked List

   A. Linked List 구조

  -> 연결 리스트

  -> 배열은 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조

  -> 링크트 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해 관리하는 데이터 구조

  -> 본래 C언어에서는 주요한 데이터 구조이지만, 파이썬은 리스트 타입이 링크드 리스트의 기능 모두 지원

  -> 링크드 리스트 기본 구조와 용어

       -노드: 데이터 저장 단위 (데이터 값, 포인터) 로 구성

       -포인터: 각 노드 안에서 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간

  -> 일반적인 링크드 리스트 형태

   B. 간단한 링크드 리스트 예

     ->Node 구현

    -보통 파이썬에서 링크드 리스트 구현시 파이썬 클래스 활요

    

class Node:

       def_init__(self, data) :

                self.data = data

                self.next = None

class Node:

        def__init__(self, data, next =None):

                self.data = data

                self.next = next

Node와 Node 연결하기 ( 포인터 활용 )

  node 1  = Node  (1)

 node 2   = Node  (2)

 node1.next = node 2

head = node1

 

링크드 리스트로 데이터 추가하기

class Node:

def__init__(self, data, next = None) :

        self.data = data

        self.next = next

           def add(data):

                      node =head

                      while node.next:

                                 node = node.next

                      node.next = Node(data)

  node1 = Node(1)

 head = node1

 for index in range(2,10):

             add(index)

 

링크드 리스트 데이터 출력하기( 검색하기)

node = head

while node.next :

             print(node.data)

             node  = node. next

print ( node.data)

 

--> 이번 강의를 통해 스택의 정의와 스택이 쓰이는 구조와 스택의 장단점에 대해 학습할 수 있었습니다.

--> 또한 Linked List의 구조와 간단한 기본 구조와 링크드 리스트에 사용되는 용어를 배울 수 있었습니다.

 

강의에 대해 정확하게 알고 싶다면 

https://bit.ly/2FgOONG