2020-04-14 TIL 자료구조(Data Structure)-Stack & Queue

seo_kk·2020년 4월 20일
0

Stack

Stack 이란?

  • 마지막으로 저장한 데이터가 처음으로 읽힌다.
  • 영어로 하면 LIFO이다. (Last In First Out)
  • Stack에서 데이터 저장은 push 라고 한다.
  • 데이터를 읽어들이는 건 pop라고 한다. 다만 pop는 읽어들임과 동시에 stack에서 삭제한다.

Stack 예시

class MyStack:
    def __init__(self):
        self.plate = []

    def push(self, value):
        self.plate.append(value)

    def pop(self):
        if len(self.plate) == 0:
            return "다 먹었슈";
        else:
            return self.plate.pop()

    def is_empty(self):
        return len(self.plate) == 0

    def peak(self):
        return self.plate[-1]

    def print_stack(self):
        print("접시 위에 팬케이크 {0} 장이 쌓여 있습니다.".format(len(self.plate)) )


my_stack = MyStack()

print(my_stack.push("바닐라맛"))
print(my_stack.push("초코맛"))
print(my_stack.push("딸기맛"))
print(my_stack.peak() )
print(my_stack.push("녹차맛"))
print(my_stack.push("커피맛"))
print(my_stack.plate)

print(my_stack.pop())
print(my_stack.pop())
print(my_stack.pop())
print(my_stack.pop())
print(my_stack.pop())
print(my_stack.plate)

my_stack.print_stack()

Stack의 활용

  • 웹 브라우저 방문 기록(뒤로가기) 및 실행취소
  • 미로찾기 알고리즘. = 방문한 곳을 좌표로 표기하고, 다음 방문할 곳을 탐색한 후 Stack에 가능한 곳 전부를 push하고, 다시 pop 하면서 현재 경로로 변경하는 것을 반복하면 된다.
  • 프로그램에서 함수 호출 기록을 stack으로 저장.

Queue

Queue란?

  • 데이터가 들어온 순서대로 처리된다.(먼저 push된게 먼저 pop된다.)
  • 새치기는 안된다. 새로운 데이터는 가장 마지막줄에 삽입된다.
  • 영어로 하면 FIFO이다. (First In First Out)

Queue 예시

class Queue:
    def __init__(self):
        self.waiting = []

    def enqueue(self, person):
        self.waiting.append(person)
        return "{0}이(가)  대기줄에 추가 되었습니다.".format(person)

    def dequeue(self):
        if self.is_empty():
            return "대기자 없음! 아무나 튀어오슈"
        else:
            return self.waiting.pop(0)

    def front(self):
        if self.is_empty():
            return "대기자 없음! 아무나 튀어오슈"
        else:
            person = self.waiting.pop(0)
            return person

    def is_empty(self):
        return len(self.waiting) == 0

    def print_queue(self):
        return "저희 카페 대기 손님은 {0}으로 총{1}명이 대기 중입니다.".format(self.waiting, len(self.waiting) )


queue = Queue()

print( queue.is_empty() )
print( queue.enqueue("예리") )
print( queue.enqueue("두리") )
print( queue.enqueue("준식") )
print( queue.enqueue("승현") )
print( queue.waiting )

print( queue.front() )
print( queue.waiting )

print( queue.dequeue() )
print( queue.dequeue() )

print( queue.print_queue() )

print( queue.waiting )
print( queue.dequeue() )
print( queue.dequeue() )
print( queue.front() )

Queue의 활용

  • CPU의 프로세스 스케줄링
  • 프린터의 인쇄 대기목록
  • 맛집 예약, 티켓카운터 등의 예약 시스템
profile
BackEnd-Developer

0개의 댓글