아래 포스트는 Data Structure and Algorithmic Thinking with Python을 참고하여 작성되었습니다.
Stack
1. What is a Stack?
스택은 원소를 넣는 순서와 빼는 순서가 동일한 자료구조입니다.
스택의 연산으로는 pop(원소를 제거하고 가져옴)와 push(원소를 맨 위에 추가함)가 있습니다.
에러로는 underflow(없는데 제거하려고함)과, overflow(스택이 꽉 찼는데 추가하려고함)이 있습니다.
2. Stack의 기능
- push
- pop
- top : 제일 위에 있는 원소를 보는 기능
- size
- IsEmptyStack
- IsFullStack
-> pop이랑 top기능은 스택이 없을 때는 에러를 반환해야함(throw Exceptions)
3. 스택의 Application
- Page-visited history in a Web browser
- Undo sequence in a text editor
- Matching Tags in HTML and XML
상식적으로 이해가 가는 어플리케이션들입니다.
그 외에도
- Implementing function calls
- Auxiliary data structure for other algorithms (ex : Tree traversal algorithms)
처럼 보조적으로 다른 자료구조나 알고리즘을 위해 사용되기도 합니다.
4. 스택의 구현
스택은 simple array, dynamic array, linked list로 구현이 가능합니다.
파이썬에는 일반 리스트가 pop, append기능을 가지고 있기 때문에 사실상 리스트가 스택을 대체한다고 봐도 됩니다.
게다가 파이썬의 리스트는 resizing을 동적으로 하기 때문에 dynamic array도 대체할 수 있습니다.
번외 : list의 resizing
- 일반적으로 resize를 size 1씩 올라갈 때마다 하게 되면 큰 시간적인 낭비가 되기 때문에, 그러지는 않고 특별한 growth pattern을 둬서 list를 재할당합니다.
- growth pattern : 0, 4, 8, 16, 25, 35, 46, 58, 72, 88….
- 예를 들어서, length 8의 list에 append메서드를 사용하면, 16 size로 메모리를 재할당하고 아이템을 채워줍니다. (물론 나머지 7개가 우리한테 보이는 것은 아닙니다.)
만약 극단적으로 array의 size가 초과할 때 마다 두배씩 size를 늘려서 동적할당하게 되면,
n개의 원소를 push하기 위한 시간복잡도는 O(n)이 됩니다.
그러면 원소 하나 push의 시간복잡도를 O(1)로 줄일 수 있겠습니다.
어찌됬건 Linked List로 Stack을 구현해 볼 수 있겠는데,
Push랑 Pop을 제한을 둬서 시작위치에만 시행하게 만들면 그게 바로 stack이 됩니다.
class Stack:
def __init__(self, limit = 2e10):
self.head = None
self.size = 0
self.limit = limit
def push(self,data):
if self.IsFullStack():
raise OverflowError
NewNode = Node()
NewNode.setData(data)
if self.size == 0:
self.head = NewNode
else:
NewNode.setNext(self.head)
self.head = NewNode
self.size += 1
def pop(self):
res = self.head.getdata()
self.head = self.head.getNext()
self.size -= 1
return res
def top(self):
if self.IsEmptyStack():
raise IndexError
return self.head.getdata()
def IsEmptyStack(self):
return self.size == 0
def IsFullStack(self):
return self.size == self.limit
이러한 방식들 모두 성능면에서 큰 차이는 없습니다.
Queue
1. What is a Queue?
원소의 추가를 뒤에서(rear), 원소의 삭제를 앞에서(front)만 진행하는 ordered list입니다.
원소를 추가하는 작업을 EnQueue 라고 하며, 삭제하는 작업을 Dequeue라고 합니다.
기능
- Enqueue
- Dequeue
- Front
2. Applications
-
들어오는 순서대로 일을 진행하는 운영시스템(ex: 음식점 주문)
-
- Multiprogramming
-
단일 프로세서 상에서 여러 개의 프로그램이 동시에 실행되는것.
(Multiprocessing이랑은 다른 말이다!)
그런데 프로세서는 한번에 한 작업만 수행할 수 있기 때문에 엄밀히 말하면 동시는 아니다.
그래서 한 프로그램이 일부 수행되고 나서, 다른 프로그램이 수행되는 식으로 구성됩니다.
이 멀티프로그래밍을 위해서는 Process scheduling이 필요한데,
하나의 Task를 여러개의 프로세스를 번갈아가면서 수행하는 절차라고 생각하시면 됩니다.
링크에는 이러한 내용이 첨부되어 있습니다.
[Process Scheduling Queues
The OS maintains all PCB(process control block, 프로세스 제어 블록)s in Process Scheduling Queues. The OS maintains a separate queue for each of the process states and PCBs of all processes in the same execution state are placed in the same queue. When the state of a process is changed, its PCB is unlinked from its current queue and moved to its new state queue.
The Operating System maintains the following important process scheduling queues
- Job queue − This queue keeps all the processes in the system.
- Ready queue − This queue keeps a set of all processes residing in main memory, ready and waiting to execute. A new process is always put in this queue.
- Device queues − The processes which are blocked due to unavailability of an I/O device constitute this queue.]
운영체제는 PCB들을 Process Scheduling Queue들에 저장하며, 프로세스의 상태(execution state)에 따라서 그 queue들을 분할합니다.
그러한 queue들은 3가지로 나눌 수 있으며, Ready queue는 실행직전인 프로세스들을 메인메모리에 남겨놓는 역할을 하며, Device queue는 임시로 차단된 프로세스들을 저장하는 역할을 하는듯합니다.
-
Asynchronous data transfer(비동기적 데이터 전송)
-
동기적 : 다음 행동을 위해서는 이전의 행동이 반드시 완료가되어야한다!
-
비동기적 : 하나가 끝나기 전임에도 불구하고 다음 전송이 일어나는 상황(이전 행동이 끝날 때까지 기다리지 않음.)
이런 비동기적 데이터 전송에 큐를 사용하는 이유는 두 가지가 있습니다.
- 아직 끝마치지 못한 이전 전송을 큐에 넣어서 관리함으로써 더 우선적인 작업에 우선순위를 둘 수 있음.
- 아직 끝마치지 못한 작업들의 개수를 쉽게 확인할 수 있음.
-
그 외에도 다른 알고리즘이나 자료구조를 위해서도 사용됩니다.
3. 큐를 구현하기
큐를 구현하는 방식은 Circular array, Dynamic circular array, Linked list로 구현할 수 있습니다.
큐를 구현할 때 Simple array를 쓰지 않는 이유가 있는데, 이는 Simple array의 rear(입구)과 front(출구) 지점의 포인터가 고정되어있기 때문입니다.
예를 들어봅시다.
이런 Simple array에 1이라는 원소를 넣었다고 생각해봅시다.
| 출구 | 입구 | ||||
|---|---|---|---|---|---|
| 1 |
그러면 우리가 다음 원소인 2를 를 넣기 위해서는 입구쪽에 있는 원소를 이동시켜야하는 번거로움이 존재합니다.
| 출구 | 입구 | ||||
|---|---|---|---|---|---|
| 1 | 2 |
그러한 비효율성을 방지하기 위해서 혹자는 입구포인터를 계속해서 이동시키면 어떻지 않냐고 말할 수 있습니다.
| 출구=입구 | |||||
|---|---|---|---|---|---|
| 1 |
| 출구 | 입구 | ||||
|---|---|---|---|---|---|
| 1 | 2 |
| 출구 | 입구 | ||||
|---|---|---|---|---|---|
| 1 | 2 | 3 |
실제로 이렇게 포인터를 변경하는 것은 합리적입니다. 앞서 배웠다시피 array의 인덱스에 대한 주소를 계산하는 것은 매우 쉽기 때문입니다.
하지만 원소를 빼야하는 상황이 온다면 어떨까요?
| 출구 | 입구 | ||||
|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 |
그렇습니다. 기존의 원소들을 전부 한 칸씩 이동해야합니다.
| 출구 | 입구 | ||||
|---|---|---|---|---|---|
| 2 | 3 | 4 | 5 | 6 |
단순히 원소를 넣었을 뿐인데 시간복잡도가 O(n)이 걸리는 기적을 볼 수 있습니다.
결론적으로 rear point와 front point를 둘 다 움직일 수 있어야하며, 이러한 기능을 가능케 하는 자료구조는 Circular array와 linked list 뿐입니다.
-
Circular buffer라고도 불리며, 이 자료구조는 두 개의 포인터(read pointer, write pointer)를 가지고 있습니다.
이 두 포인터는 자료의 추가와 삭제를 반복할 때 마다 주기성을 가지며 이동합니다.
자세한 설명은 위의 링크에 잘 표현되어있는데
write pointer는 원소를 추가(write)할 때마다 증가하는 포인터이며,
read pointer는 원소를 삭제(read)할 때마다 증가하는 포인터입니다.
처음에는 두 포인터의 위치가 똑같다가, circular array에 원소들을 전부 채웠을 때도 두 포인터가 서로 만나게 됩니다.
이러한 이유 때문에 두 포인터의 위치관계만으로는 큐가 가득찬 상태를 구분할 수 없기 때문에 size 멤버변수를 두거나, 한 칸을 비워두고 원형 배열을 설계할 수 있습니다.
-
- 원형 배열로 큐를 구현하기
-
포인터의 이동을 실감하기 위해서 리스트가 가진 pop연산을 사용하지 않고 주어진 인덱스의 원소를 None으로 바꾸는 것으로 대체하였습니다.
class CircularQueue: def __init__(self,limit=20): self.read = 0 self.write = 0 self.limit = limit # limit-1개만 채우는걸로 합시다. self.queue = [None for _ in range(self.limit)] def enQueue(self,data): if self.read == (self.write+1) % self.limit: raise OverflowError else: self.queue[self.write] = data self.write = (self.write+1) % self.limit def deQueue(self): data = self.getread() self.queue[self.read] = None self.read = (self.read+1) % self.limit return data def getread(self): if self.read == self.write: raise IndexError else: return self.queue[self.read]출력예시
q = CircularQueue(10) for x in range(9): print(q.queue) q.enQueue(x) for x in range(5): print(q.queue) q.deQueue() for x in range(5): print(q.queue) q.enQueue(x)[None, None, None, None, None, None, None, None, None, None] [0, None, None, None, None, None, None, None, None, None] [0, 1, None, None, None, None, None, None, None, None] [0, 1, 2, None, None, None, None, None, None, None] [0, 1, 2, 3, None, None, None, None, None, None] [0, 1, 2, 3, 4, None, None, None, None, None] [0, 1, 2, 3, 4, 5, None, None, None, None] [0, 1, 2, 3, 4, 5, 6, None, None, None] [0, 1, 2, 3, 4, 5, 6, 7, None, None] [0, 1, 2, 3, 4, 5, 6, 7, 8, None] [None, 1, 2, 3, 4, 5, 6, 7, 8, None] [None, None, 2, 3, 4, 5, 6, 7, 8, None] [None, None, None, 3, 4, 5, 6, 7, 8, None] [None, None, None, None, 4, 5, 6, 7, 8, None] [None, None, None, None, None, 5, 6, 7, 8, None] [None, None, None, None, None, 5, 6, 7, 8, 0] [1, None, None, None, None, 5, 6, 7, 8, 0] [1, 2, None, None, None, 5, 6, 7, 8, 0] [1, 2, 3, None, None, 5, 6, 7, 8, 0]마치 리스트를 원처럼 돌면서 원소가 추가되고 삭제되는 모습을 볼 수 있습니다.
Dynamic circular array도 원리는 위와 비슷합니다. 다만 큐의 원소가 가득 찼을 때 Overflowerror를 반환하지 않고 rear pointer과 front pointer의 간격을 벌려서 array를 재할당하면 됩니다.
-
Linked List로 구현하기
큐를 Linked List로 구현할 때는 무조건 Doubly Linked List를 이용해야 합니다. 왜냐하면 Singly Linked List는 각 Node가 한방향으로만 주소를 참조하기 때문에 원소를 삭제하고 Tail Node의 주소를 재설정하는것이 매우 힘듭니다.
class Node: def __init__(self): self.last = None self.next = None self.data = None def getData(self): return self.data def getNext(self): return self.next def getLast(self): return self.last def setNext(self,next): self.next = next def setData(self,data): self.data = data def setLast(self,last): self.last = last class LinkQueue: def __init__(self): self.front = None self.rear = None self.size = 0 def enQueue(self,data): newNode = Node() newNode.setData(data) if self.front == None: self.front = newNode self.rear = self.front else: self.front.setLast(newNode) newNode.setNext(self.front) self.front = newNode self.size += 1 def deQueue(self): data = self.rear.getData() if self.rear == None: raise IndexError else: self.rear = self.rear.getLast() self.rear.setNext(None) return data def print_queue(self): curr = self.front while(curr.getNext() != None): print(curr.getData(), end=" ") curr = curr.getNext() print()출력 예시
LQ = LinkQueue() for x in range(10): LQ.enQueue(x) LQ.print_queue() for x in range(5): LQ.deQueue() LQ.print_queue()1 2 1 3 2 1 4 3 2 1 5 4 3 2 1 6 5 4 3 2 1 7 6 5 4 3 2 1 8 7 6 5 4 3 2 1 9 8 7 6 5 4 3 2 1 9 8 7 6 5 4 3 2 9 8 7 6 5 4 3 9 8 7 6 5 4 9 8 7 6 5 9 8 7 6Linked List를 이용해서 큐를 구현하면 Search를 할 필요가 없기 때문에 Linked list와 큐는 궁합이 맞다고 생각합니다.