출처
📚 쉽게 배우는 자료구조 with 파이썬
📚 이것이 자료구조+알고리즘이다 with C언어
✏️ 기존에 공부했던 내용
💻 스택 - 상속 구현 참고한 블로그
2주차: 배열, 연결 리스트, 스택, 큐
리스트, 스택, 큐, 트리는 프로그래머가 일상적으로 사용하는 ADT이다.
❗️ ADT(추상 데이터 형식): 자료구조의 동작 방법을 표현하는 데이터 형식. 즉, 자료구조가 갖춰야 하는 일련의 연산 -> C언어로 표현하면 '함수'!
먼저 리스트, 스택, 큐에 대해 알아보자.
배열과 리스트
👉🏻 정처기 공부때 사용했던 이미지: 연속리스트와 연결리스트
| 연속 리스트 | 연결 리스트 |
|---|---|
 |  |
배열은 리스트처럼 데이터 목록을 다루며, C언어에서 기본적으로 제공한다. 그런데 왜 배열이 아닌 리스트를 만들어서 사용하느냐 하면, 배열 생성 시점에 데이터의 크기를 정해줘야 하고 이를 변동할 수 없기 때문이다.
반면 python에서는 보다 추상적 자료구조인 리스트를 오픈소스로 제공하지만, 다른 언어에 있는 '배열'은 기본적으로 제공하지 않는다. 리스트는 크기에 융통성이 있고 추상 레벨이 높다.
Python에서 배열을 엄격하게 사용해야 하는 경우, numpy 패키지에서 배열을 불러와 사용하면 된다.
배열 리스트 (파이썬 기본 제공)
배열 리스트의 ADT: insert(i, x), append(x), pop(i), remove(x), index(x), clear(), count(x), extend(a), copy(), reverse(), sort()
파이썬의 리스트는 기본적으로 배열로 구현되어 있어, 기존 배열이 가지는 문제점을 그대로 가진다. 이는 리스트에 원소를 추가하거나 삭제할 때 기존 원소들이 오른쪽이나 왼쪽으로 시프트된다는 것인데, 할당받은 배열 크기를 넘어가면 삽입을 할 수 없다.
그러나 하부에 이에 대한 처리도 포함되어 있어서 사용하는 입장에서는 편리함. 러프하게 설명하자면 기존 데이터를 복사해 새 공간에 할당하는 방식.
연결 리스트
연결 리스트의 ADT: __head, __numItems, insert(i,x), append(x), pop(i), remove(x), get(i), index(x), isEmpty(), size(), clear(), count(x), extend(a), copy(), reverse(), sort()
배열의 공간낭비를 피할 수 있는 자료구조. 배열처럼 연속된 공간을 할당받는 것이 아니라, 원소가 추가될 때마다 공간 할당받는 동적 할당방식을 따르기 때문이다.
연결리스트는 데이터와 노드(C의 포인터, JAVA의 레퍼런스)로 구성된다. 마지막 노드의 링크는 None값 할당.
노드 클래스 생성
class ListNode:
def __init__(self, newItem, nextNode:'ListNode'):
self.item = newItem
self.next = nextNode연결 리스트 생성
from listNode import ListNode
class LinkedListBasic:
def __init__(self):
self.__head = ListNode('dummy', None)
self.__numItems = 0
def insert(self, i: int, newItem):
if i>=0 and i<= self.numitems:
prev = self.__getnode(i, -1)
newNode = ListNode(newItem, prev.next)
prev.next = newNode
self.__numItems += 1
else:
print(f"index {i}: out of bound in insert()")
def __getnode(self, i:int) -> ListNode:
curr = self.__head
for index in range(i+1):
curr = curr.next
return curr
def append(self, newItem):
prev = self.__getnode(self.__numItems -1)
newNode = ListNode(newItem, prev.next)
prev.next = newNode
self.__numItems += 1
def pop(self,i:int):
...
...스택과 큐
스택
LIFO 구조. 스택을 활용한 예: 백스페이스(←), 실행 취소(ctrl+z) 등.
맨 위 원소만 접근 가능한데, 이 원소를 탑 또는 스택 탑 원소라고 한다.
함수 호출 체인에서 함수를 호출한 함수, 수행중인 함수 등을 효율적으로 관리 가능.
스택의 ADT: __stack[], push(x), pop(), top, isempty(), popAll()
리스트를 이용한 스택
파이썬에서는 리스트를 이용해 스택을 간결하게 구현할 수 있다.
👇🏻 스택 ADT를 파이썬 class로 정의
class ListStack:
def __init__(self):
self.__stack = []
def push(self,x):
self.__stack.append(x)
def pop(self):
return self.__stack.pop()
def top(self):
if self.isEmpty(): return None
else: return self.__stack[-1]
def isEmpty(self) -> bool:
return not bool(self.__stack)
def popAll(self):
print("Stack from top:", end = '')
for i in self.__stack:
print(i, end = '')
print()함수 개념 설명
- 객체 메소드 \_\_init\_\_(): 모든 클래스에 공통적인 이름으로 있는 **생성자 (Constructor)**로, 해당 클래스의 객체가 생성될 때 수행된다. 본 클래스에서 \_\_init\_\_이 하는 일은 빈 리스트 self.__stack[]을 생성, 즉 **초기화**하는 것이다.
- self: 현재 인스턴스를 가리키는 첫 번째 매개변수로, 관례적으로 self를 사용한다. self를 통해 현재 인스턴스 내의 속성이나 메서드에 접근할 수 있음.
- 리스트의 이름 앞에 언더스코어 두개를 빼고 stack[]으로 해도 상관은 없지만, 이를 붙여서 이름을 만들면 외부에서 물리적 접근이 어렵게 만든다.
- -> bool: 주석으로, 반환되는 자료형을 나타냄.사실 파이썬에 내장된 list에는 이 기능들이 거의 구현되어 있다.
다음과 같이 부모 클래스 list에서 기능을 상속받고, 없는 기능만 추가할 수도 있다.
class ListStack(list):
def push(self, x):
self.append(x)
a = [1, 2, 3, 4]
st = ListStack(a)
st.push(5)
print(st)연결 리스트를 이용한 스택
위에서 만든 연결 리스트 클래스를 import 하여 스택 클래스 생성
import linkedListBasic
class LinkedStack:
def __init__(self):
self.__list = linkedListBasic()
def push(self,newItem):
self.__list.insert(0,newItem)
def pop(self):
return self.__list.pop(0)
def top(self):
if self.isEmpty():
return None
else:
return self.__list.get(0)
...큐(queue)
쉽게 말하면 줄세우기 개념. 한쪽으로는 들어가기만 하고, 반대쪽으로는 빠지기만 한다. 스택과 다르게 FIFO형식의 자료구조이다.
front와 tail의 두 가지 포인터가 있고, tail로 들어가면 front에서는 삭제된다.
큐의 ADT: __queue[], enqueue(x), dequeue(), front(), isEmpty(), dequeueAll()
python 리스트로 큐 클래스 생성하기
class ListQueue:
def __init__(self):
self.__queue = []
def enqueue(self, x):
self.__queue.append(x)
def dequeue(self):
return self.__queue.pop(0)
def front(self):
if self.isEmpty():
return None
else:
return self.__queue[0]
def isEmpty(self)->bool:
return(len(self.__queue) == 0)
def dequeueAll(self):
self.__queue.clear()