[자료 구조] Python으로 알아보기 : Array & Stack

Array란?

동일한 타입의 데이터를 연속된 메모리 공간에 순차적으로 저장 ( C언어의 경우)

C언어의 배열은 메모리칸에 실제데이터 값을 넣는 방식

• 메모리 한칸이 4바이트(int)라면, 배열은 [4바이트값][4바이트값][4바이트값]... 처럼 데이터만 이어짐
• 그래서 중간에 다른 타입이 들어가면 크기가 맞지 않음.
• 따라서 동일타입, 연속공간

현대 언어의 배열

파이썬이나 자바의 ArrayList는 메모리칸에 실제 값이 아닌 주소 값(Reference)을 저장

• 메모리 칸엔 값이 담기지 않음
• 각 값들의 주소(포인터)들만 연속적으로 담김
• 주소값의 크기는 시스템마다 일정(ex: 8바이트)하기 때문에, 어떤 타입이 오든 배열의 칸의 크기는 균일하게 유지됨
• 따라서, 동일한 타입은 아닐 수 있음

연속된 공간은 맞으나, 데이터가 연속된 것이 아닌 주소값들이 연속된 공간에 모여 있음

 

주소값의 크기

• 32비트
  • 주소값의 크기 : 4바이트
  • 최대 메모리 : 약 4GB (주소의 갯수 = 2³²)
• 64비트
  • 주소값의 크기 : 8바이트
  • 최대 메모리 : 약 16EB (주소의 갯수 =  2⁶⁴ )

인덱스 접근 속도

• O(1)

탐색속도

• O(n)

삽입, 삭제

• O(n)
  • 상황의 따라 다름
  • 마지막에 삽입, 삭제는 빠름
  • 임의의 위치는 삭제 후 빈 공간에 뒤에 값을 복사하거나 삽입을 위해 한 칸뒤로 복사후 공간에 넣는 작업

배열의 구현 예

class Array:
    def __init__(self):
        self.length = 0
        self.capacity = 2
        self.data = [None] * self.capacity

    def get(self, index):
        if index < 0 or index >= self.length : return None
        return self.data[index];

    def push(self, item):
        if self.length == self.capacity:
            self.resize(self.capacity * 2)
        self.data[self.length] = item
        self.length += 1

    def pop(self):
        if self.length == 0: return None
        lastItem = self.data[self.length - 1]
        self.data[self.length - 1] = None
        self.length -= 1
        return lastItem

    def insert(self, index, item):
        if self.length == self.capacity:
            self.resize(self.capacity * 2)
        for i in range(self.length, index, -1):
            self.data[i] = self.data[i - 1]
        self.data[index] = item
        self.length += 1

    def delete(self, index):
        if index < 0 or index >= self.length : return None
        for i in range(index, self.length):
            self.data[i] = self.data[i + 1]
        self.data[self.length - 1] = None
        self.length -= 1

    def resize(self, new_capacity):
        new_data = [None] * new_capacity
        for i in range(self.length):
            new_data[i] = self.data[i]
        self.data = new_data
        self.capacity = new_capacity

여기서 중요한 점은 배열의 reszie와 capacity인데

capacity는 해당 배열이 가질 수 있는 여유분을 나타냄.

 

동적 배열에서는 인덱스가 고정된 값이 아닌 늘어 날 수 있기 때문에 값을 추가 하기 전에 해당 배열의 크기가 괜찮은지 확인을 한 후에 값을 추가하고 배열의 크기가 꽉 찬 상태라면 새로운 길이의 배열을 할당한 후 기존 값을 복사하고 배열에 추가하는 방식으로 항상 마지막에 넣는 작업이 O(1)이 될 순 없다. 

---

Stack

스택이란 후입선출(LIFO : Last In First Out)을 해주는 자료구조로 파이썬에선 다른 import 없이 list(Array)를 통해 구현이 가능하다.

쉽게 프링글스를 떠올리면 가장 마지막에 넣은것이 위에 있어서 바로 꺼내오는 방식

 

시간복잡도

• push : O(1) / 배열에 남는 자리가 없다면 새로운 배열을 할당하고 복사 후 삽입이 일어나 O(n)
• pop : O(1)
• peek : O(1)

주요 사용처

• 웹 브라우저 뒤로 가기
• 실행 취소 ( Ctrl + Z )

 

구현예시

class Stack:
    def __init__(self):
        self.length = 0
        self.capacity = 2
        self.data = [None] * self.capacity

    def push(self, item): #append에 해당하는 로직
        if self.length == self.capacity:
            self.resize(self.capacity * 2)
        self.data[self.length] = item
        self.length += 1

    def pop(self):
        if self.length == 0: return None
        lastItem = self.data[self.length - 1]
        self.data[self.length - 1] = None
        self.length -= 1
        return lastItem

    def resize(self, new_capacity):
        new_data = [None] * new_capacity
        for i in range(self.length):
            new_data[i] = self.data[i]
        self.data = new_data
        self.capacity = new_capacity

    def peek(self):
        if self.length == 0: return None
        lastItem = self.data[self.length - 1]
        return lastItem

---

파이썬에서 사용할땐

배열을 사용해서 사용

 

사용 예시

st = [5, 6, 3, 7, 2]
#빈 배열을 만들땐 st = []

my_stack.append(6)
my_stack.append(7)

popped_element = st.pop()

peek_element = st[-1]

is_empty = len(st) == 0