[자료구조] 스택 Stack

스택 (Stack)

: 후입선출의 자료구조 중 하나이다.

• LIFO (Last In First Out) : 마지막에 들어온 데이터가 제일 먼저 나감
• FILO ( First In Last Out) : 첨에 들어온 데이터가 제일 늦게 나감

둘 다 똑같은 말이고 스택의 특징이다.

 

 

스택은 프링글스다!

 

바닥이 막혀있고, 데이터를 하나씩 위로 쌓아가는 구조다.

그래서 처음에 집어넣은 데이터는 가장 아래에 깔려있기 때문에, 데이터를 다시 꺼낼 때 맨 마지막에 나가게 된다.

반대로 젤 마지막에 집어넣은 데이터는 가장 위에 올려져 있기 때문에, 다시 꺼낼 때 맨 먼저 나가게 된다.

 

 

처음에 스택에 데이터가 들어있지 않고 비어있는 상태이면

isEmpty 는 True이고,

스택의 길이는 0이다.

 

 

push() 함수를 통해 스택에 데이터를 넣을 수 있다.

push(1) : stack에 1

push(2) : stack에 1, 2

push(3) : stack에 1, 2, 3

1 → 2 → 3 순서로 push() 하면 위 그림처럼 데이터가 아래부터 순서대로 쌓인다.

현재 비어있지 않은 상태이므로 isEmpty 는 False에 해당하고,

스택의 길이는 0이 아니다.

 

 

pop() 함수를 통해 스택에서 데이터를 꺼내서 삭제할 수 있다.

맨 위에 있는 것부터 꺼낼 수 있기 때문에 가장 마지막에 push된 데이터 3이 꺼내진다.

이렇게 스택 안에 있는 데이터 중 가장 마지막에 push된 데이터를 peek 라고 한다.

peek 였던 데이터 3 이 pop 되면, 이제 데이터 2 가 peek가 된다.

 

 

스택 쓰임

 

브라우저에서 뒤로가기 버튼의 구조와 비슷하다.

데이터 1, 데이터 2, 데이터 3 을 순서대로  검색했을 때 Stack 구조로 쌓이게 되고, 뒤로가기 버튼을 누르면 가장 마지막 기록인 '데이터 3' 화면으로 이동하게 된다.

 

스택 예시문제 '키보드 Backspace 기능 구현하기', '괄호문법 검사기' 처럼, 어떠한 입력이 들어오면 마지막 행동에 대한 변화를 주고싶을 때 쓰이는 것 같다.

 

 

스택을 코드로 구현

내가 구현한건 아니고

Stack 클래스 정의 예시코드 주석 달면서 공부하기

class Stack:                            # Stack이라는 클래스를 만들겠습니다
    def __init__(self):                 # '생성자' 매직메서드. 클래스를 인스턴스화 하여 객체를 생성할 수 있음.
        self.items = []                 # self.items 변수선언. 리스트의 초기값은 비어있음.

    def push(self, item):               # push() 함수정의, item 인자를 받아옴.
        self.items.append(item)         # append()함수 이용해서 self.items 리스트에 item 인자를 추가함.

    def pop(self):                      # pop() 함수정의
        if not self.is_empty():         # is_empty()함수호출, 만약 리스트 길이가 0 이 아니라면(=비어있지 않다면)
            return self.items.pop()     # pop()함수로 리스트의 마지막 요소를 꺼내서 버리는 기능을 하는데, 그 꺼낸값을 반환함.
        else:                           # 리스트 길이가 0 이라면(=비어있다면)
            return None                 # 꺼낼게 없으니 아무것도 반환 안함.

    def peek(self):                     # peek() 함수정의
        if not self.is_empty():         # 마찬가지로 리스트 길이가 0 이 아니라면(=비어있지 않다면) 
            return self.items[-1]       # 인덱스로 리스트 마지막 요소(스택의 맨위에 있는 요소)가 뭔지 반환.
        else:                           # 리스트 길이가 0 이라면(=비어있다면)
            return None                 # 마지막 요소랄게 없으니 아무것도 반환 안함.

    def is_empty(self):                 # is_empty() 함수정의
        return len(self.items) == 0     # self.items 리스트의 길이 = 0 임을 반환.

    def size(self):                     # size() 함수정의
        return len(self.items)          # self.items 리스트의 길이를 반환(요소가 몇개인지)

stack = Stack()                         # Stack 클래스의 속성을 가진 stack 이라는 객체 생성.

stack.push(1)                           # 1이라는 인자가 push함수의 item으로 들어가서 결과적으로 리스트에 추가됨.
stack.push(2)                           # 2도 추가됨.
stack.push(3)                           # 3도.

print(stack.pop())                      # 리스트의 마지막(스택의 맨위)에 있는 3을 꺼내서 버리는 기능 시행, 꺼낸거 보여줌. # 3
print(stack.pop())                      # 3을 버렸으니 이제 마지막(맨위)는 2임. 그거 꺼내서 버리는 기능 시행, 꺼낸거 보여줌. # 2

print(stack.size())                     # stack의 리스트 길이를 반환. 지금 요소가 1 한개밖에 없으니 길이는 1임.

print(stack.peek())                     # 리스트 길이가 0이 아니니 if 문 실행, 인덱스로 리스트 맨 마지막 요소가 뭔지 반환. # 1

 

 

 

 

---