자료구조 TIL - 3. Stack, Queue

Stack

• 기본적이고 잘 알려진 자료구조
• 순서를 가진 데이터를 저장하는데에 사용할 수 있다.
• Stack의 가장 대표적인 특성인 LIFO(Last In First Out)
  • 가장 마지막에 입력된 값이 가장 먼저 출력된다.
  • 이 특성으로 인해서 특정한 목적에 따라서 사용하는 편.
• Stack에 데이터를 입력하는 동작을 Push, 데이터를 출력하는 동작을 Pop라고 부른다.
  • 읽은 데이터는 Stack에서 삭제한다.

Stack의 동작

• 파이썬에서는 List라는 Stack를 사용하기에 아주 적당한 자료형이 존재한다.
• 예전에 C를 쓸때에는 Stack의 특성을 구현한 함수들을 꼭 써야 했는데, 파이썬에서는 pop(), append()라는 내장 메소드를 통해서 간단하게 Stack를 구현해서 사용할 수 있다.

#####################################################
#	Stack_prack.py

class my_Stack:
    def __init__(self):
        self.storage = []

    def push(self, data):
        self.storage.append(data)
        return data

    def pop(self):
        if len(self.storage) == 0:
            return 'Empty Storage'
        else:
            return self.storage.pop()

    def is_empty(self):
        return len(self.storage)

    def peak(self):
        print('Peak of Stack is {}'.format(self.storage[-1]))
        return self.storage[-1]

    def print_stack(self):
        print('Data Storage Count : {}EA'.format(len(self.storage)))

mystack = my_Stack()

print(mystack.push("start"))
print(mystack.storage)
print(mystack.push("sprint"))
print(mystack.storage)
print(mystack.push("sprite"))
print(mystack.storage)
mystack.peak()
print(mystack.push("super"))
print(mystack.storage)
print(mystack.push("skill"))
print(mystack.storage)
mystack.print_stack()

print(mystack.pop())
print(mystack.storage)
print(mystack.pop())
print(mystack.storage)
print(mystack.pop())
print(mystack.storage)
print(mystack.pop())
print(mystack.storage)
print(mystack.pop())
print(mystack.storage)
mystack.print_stack()

#######################################################
#	실행 결과
start
['start']
sprint
['start', 'sprint']
sprite
['start', 'sprint', 'sprite']
Peak of Stack is sprite
super
['start', 'sprint', 'sprite', 'super']
skill
['start', 'sprint', 'sprite', 'super', 'skill']
Data Storage Count : 5EA
skill
['start', 'sprint', 'sprite', 'super']
super
['start', 'sprint', 'sprite']
sprite
['start', 'sprint']
sprint
['start']
start
[]

• Stack은 보통 함수의 호출 기록이나 웹 브라우저의 방문 페이지등을 저장하는데에 사용한다.
  • 함수 호출의 경우는 재귀함수와 연관지어서 쉽게 이해할 수 있다.
  • 웹 브라우저의 경우는 가장 최근에 접속한 기록이 제일 위에 보이니까 Stack의 특성과 정확하게 일치한다.
• Stack Overflow?
  • 이름 그대로 Stack이 흘러 넘친다는 뜻으로 평범한 Stack의 경우 고정된 범위의 저장공간을 가지고 있는데 꽉 차있는 Stack에 추가적으로 데이터를 Push할 때 발생하는 문제이다.
  • 일반적으로 컴퓨터쪽에서 Overflow라는 단어가 붙은 문제는 대부분 지정된 크기의 저장공간을 초과하는 데이터를 입력할 때 생기는 문제에 붙는다.

 

Queue

• Queue 또한 잘 알려진 자료구조
• 순서를 가진 데이터를 저장하는데에 사용할 수 있다.
• Queue의 가장 대표적인 특성은 FIFO(First In First Out)
  • 처음 입력된 데이터가 가장 먼저 출력된다.
• Queue에 데이터를 입력하는 동작을 Enqueue, 데이터를 출력하는 동작을 Dequeue라고 한다.
  • 출력한 데이터는 당연히 Queue에서 삭제한다.
  • 상식적인 동작으로서 일반적인 순서와 연관된 데이터를 사용할 때 사용한다.

Queue의 동작

• Stack의 경우와 비슷하게 파이썬에서는 List자료형을 사용해서 Queue를 간단하게 구현할 수 있다.
• enqueue 동작의 경우 Stack의 경우와 동일하게 append() 메소드를 사용하면 된다.
• dequeue 동작의 경우는 로직을 조금 만들어야 하는데 나는 0번 인덱스를 통해서 가장 앞부분의 데이터에 접근하고 슬라이싱을 통해서 읽어낸 데이터를 지우는 방법을 사용했다.
  • pop()메소드에서 인덱스를 지정하는 방법을 사용해도 좋다.

######################################################
#	queue_prac.py
class my_Queue:
    def __init__(self):
        self.storage = []

    def enqueue(self, data):
        self.storage.append(data)
        return data

    def dequeue(self):
        if len(self.storage) > 0:
            res = self.storage[0]
            self.storage = self.storage[1:]
            return res
        else:
            return 'Empty Queue'

    def peak(self):
        return self.storage[0]

    def is_empty(self):
        return len(self.storage)

    def print_queue(self):
        print('Data Storage Count : {}EA'.format(len(self.storage)))

myqueue = my_Queue()

print(myqueue.enqueue('timer'))
print(myqueue.storage)
print(myqueue.enqueue('tea'))
print(myqueue.storage)
print(myqueue.enqueue('tiger'))
print(myqueue.storage)
print(myqueue.peak())
print(myqueue.enqueue('tire'))
print(myqueue.storage)
print(myqueue.enqueue('table'))
print(myqueue.storage)
myqueue.print_queue()

print(myqueue.dequeue())
print(myqueue.storage)
print(myqueue.dequeue())
print(myqueue.storage)
print(myqueue.dequeue())
print(myqueue.storage)
print(myqueue.dequeue())
print(myqueue.storage)
print(myqueue.dequeue())
print(myqueue.storage)
myqueue.print_queue()

#######################################################
#	실행 결과
timer
['timer']
tea
['timer', 'tea']
tiger
['timer', 'tea', 'tiger']
timer
tire
['timer', 'tea', 'tiger', 'tire']
table
['timer', 'tea', 'tiger', 'tire', 'table']
Data Storage Count : 5EA
timer
['tea', 'tiger', 'tire', 'table']
tea
['tiger', 'tire', 'table']
tiger
['tire', 'table']
tire
['table']
table
[]

• Queue의 경우는 예약 시스템이나 CPU의 프로세스 스케줄링, 프린터의 인쇄 목록등에 사용한다.
  • 상식적인 처리 방법인 가장 먼저 받은 요청 또는 데이터를 가장 먼저 처리해야 할 때 사용하면 된다.
• Queue의 경우 Circular Queue, Priority Queue, Deque-double enede Queue등 심화된 기능을 가진 Queue도 여럿 존재한다.
  • 이 부분은 나중에 추가로 정리해볼만하다.