-
[자료구조]Stack, Queue 구현CS/Data Structure 2022. 7. 26. 00:10
가장 기본적인 자료구조인 스택과 큐를 python 코드를 이용해 구현해보겠습니다.
Stack
후입선출 특성의 자료구조(Last In First Out)
1. 배열을 이용한 구현
- 스택을 위한 배열 선언(최대 크기 설정) / index = 0
- index가 선언한 배열의 크기 이상이면 stack 꽉 찬 상태 / index = 0 이면 비어있는 상태
- push() : index 자리에 값 추가, index+=1
- pop() : index에 위치한 값 리턴, index-=1
- 모든 연산의 시간 복잡도 : O(1)
class arrayStack: def __init__(self): self.array = [] #maxSize 설정. self.top = -1 def isEmpty(self): if self.top==-1: return True else: return False def push(self, data): self.array.append(data) self.top+=1 def pop(self): if self.isEmpty(): return -1 data = self.array[self.top] self.top-=1 return data def peek(self): if self.isEmpty(): return -1 data = self.array[self.top] return data
2. 연결 리스트를 이용한 구현
- 스택의 크기가 고정되어 있지 않게 됨 (python, java에서 제공하는 stack의 구현 방식)
- 메모리에 값을 위한 공간 할당
- 메모리 상에 순서와 관계 없이 새로운 값이 추가되면 포인터로 연결(포인터를 위한 공간 추가적으로 필요하다.)
- push() : newNode 추가, newNode의 link에 top 저장→ top = newNode
- pop() : top의 data 반환(다른 변수에 저장 후 반환하면 된다.), top = top의 link → top 앞의 메모리 해제
- 모든 연산의 시간 복잡도 : O(1)
class Node: def __init__(self, data=0, link=None): self.data = data self.link = link class Stack: def __init__(self): self.top = None def push(self, data): newNode = Node(data) newNode.link = self.top self.top = newNode def pop(self): if self.isEmpty(): return -1 data = self.top.data self.top = self.top.link return data def isEmpty(self): if self.top != None: return False return True def peek(self): if self.isEmpty(): return -1 return self.top.data
Queue
선입선출 특성의 자료구조 (First in First Out)
1. 배열을 이용한 일반적인 큐 구현
- 오버헤드가 발생한다.
- 데이터의 출구와 입구가 다르기 때문에 push, pop 연산마다 모든 데이터의 위치가 한 칸씩 이동된다.
- 인덱스만 변경하는 방식도 있지만 이 경우에 공간을 낭비하게 된다. 이를 해결하기 위해 원형 큐를 사용할 수 있다.
- front에서 pop, rear에서 push
- 연산 속도 : 모든 데이터를 밀어서 관리하는 경우 시간 복잡도 O(N) / pointer를 이용하여 메모리를 낭비하는 경우 시간 복잡도 O(1)
class arrayQueue: def __init__(self): self.array = [] self.front = 0 self.rear = 0 self.maxSize = 1000 def isEmpty(self): return self.front == self.rear #0 or 1 def isFull(self): return self.rear == self.maxSize def push(self,data): if not self.isFull(): self.array.append(data) self.rear+=1 def pop(self): if not self.isEmpty(): data = self.array[self.front] self.front+=1 return data def peek(self): data = self.array[self.front] return data
2. 배열을 이용한 원형 큐 구현
- 큐를 위한 배열 선언(최대 크기 설정) / front, rear = 0
- front에서 pop, rear에서 push
- maxSize+1로 배열을 만들어 더미 공간을 만든다( empty와 full의 상태를 구분하기 위함이다.)
- 모든 연산의 시간 복잡도 : O(1)
class circleQueue: def __init__(self): maxSize = 10 self.maxSize = maxSize+1 # front의 첫번째 공간부터 데이터를 넣지 않고 더미 공간 -> full / empty 구분 self.front = 0 self.rear = 0 self.array = [None] * maxSize def isEmpty(self): return self.front == self.rear def isFull(self): return self.front == (self.rear+1)%self.maxSize def push(self,data): if not self.isFull(): self.rear = (self.rear+1)%self.maxSize self.array[self.rear] = data def pop(self): if not self.isEmpty(): self.front = (self.front+1)%self.maxSize return self.array[self.front] def peek(self): if not self.isEmpty(): return self.array[self.front+1]
3. 연결 리스트를 이용한 구현
- front에서 pop, rear에서 push
- 연결 리스트를 이용한 stack과 마찬가지로 queue의 크기가 고정되어 있지 않게 됨.
- 모든 연산의 시간 복잡도 : O(1)
class Node: def __init__(self,data=0, link=None): self.data = data self.link = link class Queue: def __init__(self): self.front = 0 self.rear = 0 def isEmpty(self): if self.front == 0 and self.rear==0: return True else: return False def push(self, data): newNode = Node(data) if self.isEmpty(): self.front = newNode self.rear = newNode else: self.rear.link = newNode self.rear = newNode def pop(self): if not self.isEmpty(): data = self.front self.front = self.front.link return data.data def peek(self): if not self.isEmpty(): return self.front.data
'CS > Data Structure' 카테고리의 다른 글
Red-Black Tree에서 Red 노드를 삽입하고 균형을 맞추는 이유? (2) 2023.01.02 [자료구조]정렬 알고리즘 비교 정리 (0) 2022.07.27