[자료구조|알고리즘] 스택, 큐

1. 스택 

한쪽 끝으로만 자료를 넣고 뺄 수 있는 자료구조.

LIFO ( last in first out)

 

넣은 순서를 쌓아두고 있기 때문에 필요하다.

 

- 구현 : push, pop, is_empty

assert Node(1, None).item == 1

-> Node의 item을 꺼내면, 1이라는 값이 나와야 한다.

 

Class Node:
	def __init__(self, item, next):
    	self.item = item
        self.next = next

-> node의 item 은 item을 의미하고, self.next 나는 다음 노드를 가리킨다.

 

node와 stack의 결합

class Node:
    def __init_(self, item, next):
        self.item = item
        self.next = next

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

    def is_empty(self):
        return self.top is None

    def push(self, val):
        self.top = Node(val, self.top)
        
...

 

2. 큐

FIFO (first in first out) 을 만족한다.

순서대로 처리되어야 하는 일에 유용하다.

 

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

class queue:
    def __init__(self):
        self.front = None

    def is_Empty(self):
        return self.front is None
    
    def push(self, value):
        if self.front is None:
            self.front = Node(value, None)
            return
        
        node = self.front
        while node.next:
            node = node.next
            
        node.next = Node(value, None)
        return 
    
    def pop(self):
        if self.front is None:
            return None
        
        node = self.front
        self.front = self.front.next
        return node.value