Stack

stack?

• 마지막으로 저장한 데이터가 처음으로 읽힘(LIFO = Last In First Out) - 먼저 들어간 것이 나중에 나옴
• 스택은 크게 삽입(push), 삭제(pop), 읽기(peek), 스택크기(size)로 구성되어 있다.
• 원하는 데이터의 접근 속도가 빠르다.
• 배열을 사용하나 로직을 붙여줌
• 예시 : 브라우저 뒤로가기

stack 구조

스택은 크게 삽입(push), 삭제(pop), 읽기(peek), 스택크기(size)로 구성되어 있다.
파이썬에는 내장 자료형 중에 하나인 리스트형이 스택을 표현하는데 사용된다. 즉, 파이썬에는 스택을 따로 구현할 필요가 없다.

• 삽입(push) : 맨 상단에 데이터를 추가한다.
• 삭제(pop) : 맨 상단에 있는 데이터를 삭제한다.
• 읽기(peek) : 맨 상단(top)의 데이터를 읽는다. 이 때 데이터 변화는 없다.
• 스택크기(size) : 스택의 크기를 알고 싶을 때는 보통 size 변수를 만들어놓거나

구현 - list

class Stack(list):
    def __init__(self):
        self.stack = []
    
    def push(self, data):
        self.stack.append(data)
        
    def pop(self):
        if self.is_empty():
            return -1
        return self.stack.pop()
    
    def peek(self):
        return self.stack[-1]
    
    def is_empty(self):
        if len(self.stack) == 0:
            return True
        return False

if __name__=="__main__":
    s = Stack()
    s.push(1)
    s.push(2)
    s.push(3)
    print('s : ', s.stack)   # s : [1, 2, 3]
    print(s.pop())           # 3
    print('s : ', s.stack)   # s : [1, 2]
    print(s.pop())           # 2
    print('s : ', s.stack)   # s : [1]
    print(s.pop())           # 1
    print('s : ', s.stack)   # s : []
    print(s.pop())           # -1
    print('s : ', s.stack)   # s : []

구현 - 연결리스트(linked list)

연결리스트란 데이터를 노드의 형태로 저장하는 것을 말한다. 노드는 데이터와 다음 데이터의 주소값을 가진다. 연결리스트의 head는 stack의 top을 가르킨다.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        
class Stack:
    def __init__(self):
        self.head = None
        
    def is_empty(self):
        if self.head:
            return False
        return True
    
    def push(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
        
    def pop(self):
        if self.is_empty():
            return None
        ret_data = self.head.data
        self.head = self.head.next
        return ret_data
    
    def peek(self):
        if self.is_empty():
            return None
        return self.head.data
    
if __name__ == "__main__":
    s = Stack()
    print(s.is_empty()) #True
    s.push(1)
    s.push(2)
    s.push(3)
    s.push(4)
    s.push(5)
    print("peek of data : {}".format(s.peek())) # 5

    while not s.is_empty():
        print(s.pop()) # 5, 4, 3, 2, 1

참고 사이트
https://wayhome25.github.io/cs/2017/04/18/cs-20/