스택, 큐

스택
LIFO(Last In First Out)
나중에 들어온 녀석이 먼저 나가는 구조
OS에서 함수내에 잠깐 쓰이는 변수(휘발성)는 스택으로 처리됨

 

source : https://sa1341.github.io/2019/02/17/Stack-Queue/

파이썬으로 stack 구현

 

class Stack:
    def __init__(self):
        self.stack = []

    def pop(self):
        pop_value = self.stack[-1]
        self.stack = self.stack[:-1]
        return pop_value    

    def push(self,value):
        self.stack.append(value)
        
    def is_empty(self):
        if len(self.stack) ==0:
            return True
        else :
            return False
        
    def check(self):
        return self.stack

 

 

큐
FIFO(First In First Out)
먼저 들어간 녀석이 먼저 나오는 것으로 일반적으로 줄을 서는 것과 같다고 생각하면 됨

 

source : https://sa1341.github.io/2019/02/17/Stack-Queue/

 

 

스택 2개로 큐를 구현하라!!! 예전에 카카오 면접을 보았을때 물어봤던 내용이다...

이건 뭐... 스택을 두번 연속으로 사용하면 큐의 형태가 된다는 것을 기억하면 되겠다.

class Queue:
    def __init__(self):
        self.s1 = Stack()
        self.s2 = Stack()
        
    def pop(self):
        if self.s2.is_empty():
            while not self.s1.is_empty():
                self.s2.push(self.s1.pop())
        return self.s2.pop()
    
    def push(self,n):
        self.s1.push(n)