자료구조 알고리즘 Stack 스택이란?

Stack  스택이란 무엇인가?

스택이란

한쪽 끝으로만 자료를 넣고 뺄 수 있는 자료 구조.(후입선출/LIFO(Last in First out))

스택은 일상생활과 비교해 보면 너무나도 쉽게 이해가 가능합니다

프링글스를 먹으면 저희는 가장 위에 있는 감자칩부터 눈에 보이고 가장 위에부터 꺼내 먹을 수 있게 됩니다

다시 새로운 감자칩을 넣게 되더라도 아래부터가 아닌 위에서부터 쌓게 됩니다

이해가 힘들다면 그림을 보고 이해해 봅시다

그림으로 보는 Stack

LinkedList 의 Stack 

[4] -> [3] -> [2] -> [1] 

새로운 Stack을 추가하면

[5] -> [4] -> [3] -> [2] -> [1] 

마지막에 들어온 것이 self.head 가 됩니다

 

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


class Stack:
    def __init__(self):
        self.head = None
    # push 기능 구현
    def push(self, value):
        new_node = Node(value)
        new_node.next = self.head
        self.head = new_node
        return

    # pop 기능 구현
    def pop(self):
        pop_node = self.head
        self.head = pop_node.next
        return pop_node
    # peek 기능 구현
    def peek(self):
        if self.is_empty():
            return "0스택이야~"
        return self.head.data

    # isEmpty 기능 구현
    def is_empty(self):
        return self.head is None


stack =  Stack()

print(stack.is_empty()) ## True // 스택이 아직 없기 때문에
stack.push(1) ## 1 스택
print(stack.peek()) ## 1
stack.push(2) ## 2스택
print(stack.peek()) ## 2
stack.push(3) ## 3스택
print(stack.peek()) ## 3
print(stack.pop().data) ## 3스택 제거
print(stack.peek()) ## 2 // 3스택이 제거 되었기 때문에 2가 출력됨
print(stack.is_empty()) ## False // 2스택이 남아있기 때문에

Array의 Stack

stack = []            # 빈 스택
stack.append(4)       # 스택 push(4) 1스택
stack.append(3)       # 스택 push(3) 2스택
top = stack.pop()     # 스택 마지막 스택 제거
print(top)            # 3
print(stack)          #[4] 3 이란 값을 가진 2스택을 제거했기 때문에 4라는 값을 가진 1스택이 남아있음