[알고리즘, #10] 스택, 큐

권필제·2020년 12월 4일

스택 알고리즘 큐

알고리즘

목록 보기

10/15

1. 스택(stack)

1.1 개념

데이터가 한쪽으로만 넣고 뺄 수 있는 구조
가장 마지막에 저장된 데이터를 가장 먼저 불러올 수 있음(FILO)

1.2 구현

데이터의 삭제, 추가가 잦기에 linked list를 활용함
데이터 추가(push), 데이터 뽑기(pop), 가장 최근 데이터 보기(peek), 데이터 유무 확인(is_empty)

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class Stack:
    def __init__(self):
        self.head = None

    def push(self, value):		# push: 데이터 추가
        new_node = Node(value)		# 새로운 값이 할당된 노드를 생성한다.      
        new_node.next = self.head	# 기존 노드(node)의 헤드(head)를 두 번째 노드로 옮긴다.
        self.head = new_node		# 헤드를 새로운 노드로 지정한다.
        return

    # pop 기능 구현
    def pop(self):			#가장 최근 자료 가져오기(동시에 저장소에서 데이터 빠져나옴)
        if self.is_empty():		#노드에 아무것도 없을 때에 출력될 결과
            return 'Stack is empty'
        pop_head = self.head		#헤드 데이터를 가져온다.
        self.head = self.head.next	#헤드를 두 번째 노드 이후로 교체한다.
        return pop_head

    def peek(self):
        if self.is_empty():		#노드에 아무것도 없을 때에 출력될 결과
            return 'Stack is empty'
        return self.head.data		#헤드 데이터 출력하기

    # isEmpty 기능 구현
    def is_empty(self):
        return self.head is None	#헤드가 None이면 True를 반환. 아니면 False 반환

1.3 사용

가장 마지막 행위로 돌아가고 싶어할 때, 이것을 사용하면 되지 않을까? 마치 ctrl + z를 사용하는 것과 같은 효과를 낼 수 있을 것 같다.

2. 큐(queue)

2.1 개념

데이터를 양쪽으로 넣고 뺄 수 있는 구조
한 쪽은 데이터가 들어오는 입구, 다른 쪽은 데이터가 나가는 출구임
가장 마지막에 저장된 데이터를 더 빨리 불러올 수 있음(FIFO)

2.2 구현

데이터의 삭제, 추가가 잦기에 linked list를 활용함
데이터 추가(enqueue), 데이터 뽑기(dequeue), 가장 최근 데이터 보기(peek), 데이터 유무 확인(is_empty)

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class Queue:
    def __init__(self):
        self.head = None
        self.tail = None

    def enqueue(self, value):		#데이터 추가하기
        new_node = Node(value)		#새로운 데이터를 new_node에 할당
        if self.is_empty():		#만약 노드에 아무것도 없으면
            self.head = new_node	#head는 new_node임
            self.tail = new_node	#tail도 new_node
        self.tail.next = new_node 	#새로운 노드를 tail(가장 나중)의 다음에 붙이기
        self.tail = new_node 		#tail 지정하기
        return

    def dequeue(self):#데이터 빼기
        if self.is_empty(): 		#노드에 아무것도 없을 때에 출력될 결과
            return "queue is empty"
        delete_node = self.head 	#출구 앞에 있는 데이터를 새 변수에 할당하기
        self.head = self.head.next	#head를 두 번째 노드로 변경하기
        return delete_node 		#출구 앞 데이터 출력하기

    def peek(self):
        if self.is_empty():
            return "queue is empty" 	#노드에 아무것도 없을 때에 출력될 결과

        return self.head.data 		#헤드 데이터 출력하기

    def is_empty(self):
        return self.head is None 	#헤드가 None이면 True를 반환. 아니면 False 반환