Stack 왜 쓰는걸까?

브라우저에서 뒤로가기, 타자 백스페이스와 같은 기능도 모두 stack개념이라고 한다.

이미 일상에 많은 부분이 접목된 자료구조인 만큼 중요한 개념으로 오늘은 stack 기강을 확실히 잡고 가자.

이유	설명
간단한 규칙	LIFO 구조는 제어하기 쉬워서 프로그램 설계가 단순해짐
시간 효율성	push(), pop() 연산이 O(1) (상수 시간)으로 빠름
재귀, 백트래킹 구현	함수 호출 구조와 맞물려 적절한 데이터 흐름을 유지 가능
메모리 제어	함수 호출/복귀 등에서 자동으로 스택을 사용해 자원을 관리함

... 그렇다고 한다.

LIFO

LIFO는 후입선출(마지막에 들어온 녀석이 가장 먼저 나간다) 개념이다.

개념자체는 어려운 편이 아니므로 코드로 넘어가 보자.
사실 파이썬에서 직접 구조를 구현할 필요 없이,
append()와 pop()이용하여 할 수 있지만,
스텍이란 자료구조와 좀더 친해져보기 위해 시간 좀 써봤다.

from typing import Any
import sys



class my_stack:
    
    def __init__(self,capacity)-> None:
        self.stk = [None]* capacity
        self.capacity = capacity
        self.ptr = 0
    
    
    def top(self):
        if self.ptr == 0:
            print(-1)
        else:
            print(self.stk[self.ptr - 1])
        
        
    def push(self, value):
        if self.ptr < self.capacity:
            self.stk[self.ptr] = value
            self.ptr += 1
    
    def pop(self):
        if self.ptr == 0:
            print(-1)
        else:
            self.ptr -= 1
            print(self.stk[self.ptr])
    
    def size(self):
        print(self.ptr)
    
    def empty(self):
        print(1 if self.ptr == 0 else 0)
    
n = int(sys.stdin.readline())

stk= my_stack(n)

for _ in range(n):
    cmd = sys.stdin.readline().strip()
    
    if cmd.startswith("push"):
        _, x =  cmd.split()
        stk.push(int(x))
    elif cmd =="pop":
        stk.pop()   
    elif cmd =="size":
        stk.size()
    elif cmd =="empty":
        stk.empty()
    elif cmd =="top":
        stk.top()
    
    else:
        break

어려웠던 부분

대부분 스택이란 자료구조는 유명하고 개념자체는 어렵지 않기에 더 설명할 부분이 없을 것 같다.

설명은 매우 주관적이며, 내가 어려웠던 부분만 내가 보기위해 작성 한다.

내가구현한 코드는 stack에 공간을 채우면 다음 공간에서 대기 하는 방법으로 구현했다.
하지만 인덱스를 이용한 움직임을 미리 정의 하지 않고 구현을 하니 top과 pop부분이 어려웠다.

이렇게 구현할 경우 먼저 ptr을 -1로 이동 후 print 해야하는데 이 과정에서 어처구니 없는 실수를 한 것이다.

    def pop(self):
        if self.ptr == 0:
            print(-1)
        else:
            self.ptr -= 1
            print(self.stk[self.ptr])

    def top(self):
        if self.ptr == 0:
            print(-1)
        else:
            print(self.stk[self.ptr - 1])

이와 같이 아무리 개념적으로 쉬운 자료구조를 구현한다고 해도

천재가 아닌 이상.

내가 만들고자하는 함수의 명확한 이유를 알아야 하고 그러기 위해 다이어그램,수도 코드와 같은 도식화를 거쳐야 한다는 것을 한번 더 짚어 볼 수 있었다.