1.스택
# 스택은 데이터를 여러개 저장하는 자료구조
# firts in last out 형태로 데이터를 저장 및 삭제
#
# 주 사용처 컴퓨터 메모리(?)
# 메모리 구조가 스택구조로 되어있음
# 뒤로가기 버튼
# 데이터를 여러개 저장할 수 있는 리스트
# 데이터를 저장하는 기능
# 가장 마지막에 데이터를 저장
# 데이터를 삭제하는 기능
# 가장 마지막에 저장된 데이터를 삭제
# 리스트의 기능으로 스택구현
# stack = []
#
#
# def push(data) :
# stack.append(data)
#
#
# def pop():
# stack.pop()
#
#
# push(11)
# print(stack)
# push(22)
# print(stack)
# pop()
# print(stack)
# 리스트의 기능없이 구현
stack = [0,0,0,0,0,0,0,0,0,0]
# 10개만 저장할 수 있는 리스트
top = -1
def push(data):
global top
top = top +1
stack[top] = data
def pop():
global top
stack[top] = 0
top = top -1
2. 큐
# queue = []
# # 데이터를 저장하는 기능 (enqueue)
# # 숫자하나를 전달 받아서 가장 마지막에 데이터를 저장
# # 데이터를 삭제하는 기능(dequeue)
# # 가장 먼저 저장된 데이터를 삭제
# def enqueue(data) :
# queue.append(data)
#
#
#
# def dequeue():
# queue.pop(0)
# 다른 방법으로는 del queue[0]
# 리스트 기능없이 구현
queue = [0,0,0,0,0,0,0,0,0,0]
# 10개만 저장할 수 있는 리스트
rear = 0 #현재위치를 기억할 수 있는 변수
front = 0 #처음 위치를 기억할 변수
def enqueue(data):
global rear
if rear < 10 :
queue[rear] = data
rear = rear + 1
else :
rear = 0
queue[rear] = data
rear = rear + 1
# 선생님의 방법
global rear
rear = (rear+1) % 10 #저장소의 크기만큼 나머지값을 하면 됨
def dequeue():
global front
queue[front] = 0
front = (front + 1) % 10
# 배열에서 구현하면 한칸씩 밀려나는 문제가 발생
# 삭제할때 쉬프트를 이용하거나 원형저장소(다시 앞에서 부터 저장)를 사용
# 쉬프트는 효율적이지 않음
3. 리스트
1) 연결리스트
데이터를 하나 저장할때 데이터와 다음 데이터의 주소를 같이 저장
클래스는 설계도
node 클래스
데이터를 저장할 수 있는 변수
다음 저장소를 저장해 둘 변수
2개만 있으면 됨
데이터 삭제 기능(특정 index에 위치한 데이터 삭제)
처음 값 삭제는 처음값의 헤드를 헤드의 next 값으로 변경
마지막 값 삭제는 마지막 -1 번째 next를 none으로 변경
중간 값 삭제는 중간삭제값 -1번째의 next를 삭제하려는 노드의 next로 변경
2) 원형연결리스트
마지막 노드의 next는 맨처음 노드
데이터 추가기능
처음ㅇ추가하는 경우이면
새로운 노드를 생성
새로운 노드에 데이터 저장
새로운 노드의 next를 head로 지정
처음추가하는 경우가 아니면
헤드에서부터 next가 헤드일때까지 다음노드로 이동후
새로운 노드를 추가
새로운 노드에 데이터 저장
이동한 노드의 next에 새로운 노드를 저장
새로운 노드의 next를 head로 지정
4. 트리
데이터를 계층 형태로 저장
노드클래스
데이터 저장할 변수
왼쪽노드를 저장할 변수
오른쪽 노드를 저장할 변수
bst
데이터 추가기능
현재위치에 데이터가 없으면 바로 추가
첫번째 노드를 저장할 변수에 none이 저장되어 있으면
새로운도르르 생성
새로운 노드의 data를 전달받은 data를 저장
첫번째 노드를 저장할 변수에 새로운 노드를 저잦ㅇ
그렇지 않다면
root에서 부터 노드가 비어있을 때까지
만약 전달받은 data가 현재 노드의 data보다 크면
오른쪽이 비어 있으면
새로운 도르를 생성 새로운 노드의 data에 전달바은 data값 저장
현재 노드의 오른쪽에 새로운 노드를 저장
미버있지 않으면 현재 노드를 오른쪽 노들 변경
만약 전달받은 data가 현재 노드의 data보다 작으면 왼쪽이 비어있다면
새오눈 노드를 생성
새로운 노드의 data에 전달받은 data 저장
현재 노드의 왼쪽에 새로운 노드를 저장
데이터 정렬 기능(순회(전위,중위,후위)
1) 전위 순회 가운데 -> 왼쪽 -> 오른쪽
2) 중위 순회 왼쪽 -> 가운데 -> 오른쪽 (작은수부터 차례대로됨)
재귀안쓰면 효율적이지 못함
탐색을 시작할 노드를 입력받고
만약에 현재 노드가 비어있으면 넘어감(pass: 무한반복문이 안끝남)
그렇지 않으면
데이터 중위 순회(현재노드의 왼쪽)
데이터 출력
데이터 중위순회(현재노드의 오른쪽부터 시작)
(재귀함수쓰면 다음과 같음)
def middle(self,data):
current = data
if current == None :
pass
else:
self.middle(current.left)
print(current.data)
self.middle(current.right)재귀를 안썼을때
비어있는 스택 준비
스택에 탐색을 시작할 노드를 push
스택이 비어있지 않으면 반복
현재노드의 왼쪽이 비어있지 않으면 반복
현재 노드를 현재노드의 왼쪽노드로 변경
스택에 현재 노드 추가
스택에서 pop
꺼낸 노드를 출력
만약에 꺼낸 노드의왼쪽이 None이 아니고 왼쪽을 방문한 적이 없으면 꺼낸 노드부터 왼쪽 끝까지 저장스택에 왼쪽 노드 추가
만약에 꺼낸 노드의 오른쪽이 None이 아니면 스택에 오른쪽 노드 추가
3) 후위 순회 왼쪽 -> 오른쪽 -> 가운데
데이터 삭제기능
삭제할 노드의 왼쪽과 오른쪽이 없을 때(자식이 없을때)
-현재 노드를 삭제
삭제할 노드의 왼쪽 또는 오른쪽 하나만 있을때
-현재노드의 위치에 자식 노드를 지정
삭제할 노드의 왼쪽과 오른쪽 모두 있을때
-왼쪽으로 하고 싶으면 왼쪽 자식중에서 가장 큰 값을 삭제될 곳에 지정
-오른쪽으로 하고 싶으면 오른쪽 자식중에서 가장 작은 값을 삭제될 곳에 지정
데이터 탐색
루트에서 시작
현재노드의 데어토와 찾으려는 데이터를 비교
일치하면 종료
찾으려는 데이터가 현재 노드의 데이
