스택 (stack)

 

오늘은 스택을 알아볼꺼다..

엄청나게 많이 쓰고..

엄청나게 많이 알고..

 

ㅇ...

ㅇ..

엄...

 

굉장해 엄청나..!

 

바로 알아보자 let's get it!

 

 

스택이란...?

스택은 데이터를 임시 저장할 때 사용하는 자료구조로 데이터의 입력과 출력 순서는 후입선출(LIFO) 방식이다. 

LIPO(Last in Frist out) : 가장 나중에 넣은 데이터를 가장 먼저 꺼낸다

 

용어 몇가지를 알아보자 

1. 푸시 : 데이터를 넣는 작업 
2. 팝 : 데이터를 꺼내는 작업 
3. 탑 : 데이터의 꼭대기 
4. bottom : 데이터의 마지막  

이정도면 훌륭하다. ( 스압주의..)

 

 

 

푸시와 팝을 하는 예제 이다 설멍 할 필요없이 그림으로 종결

 

 

용어정리는 끝나고 군말없이 바로 구현에 들어가보자 

 

이젠 좀 가자..

 

 

 

일단 스택의 기본 개념을 이해 해야 하니 스택을 생성할 때 크기가 결정되는 고정 크기 스택을 만들어보자 

1. 스택 배열 : stk
   1. 푸시한 데이터를 저장하는 스택 본체 list형 배열을 만들꺼임 가장 먼저 푸시하여 데이터를 저장하는 곳은 stk[0] 임 
2. 스택 크기 : capacity
   1. 스택의 최대 크기를 나타내는 int형 정수임 이 값은 배열 stk의 원소 수인 len(stk)와 일치함 왜그런지 알꺼임 모르면 문법 다시 공부 해야함 
    

책에서 가져와떠염 뿌우 >.< [자료 1-1]

 

• 스택 포인터: ptr
  • 스택에 쌓여 있는 데이터의 개수를 나타내는 정숫값을 스택 포인터(stack pointer) 이라고함 물론 스택이 비어 있으면 ptr의 값은 0이 되고 가득차있으면 capacity와 같은 값이 됨  지금 보고 있는 자료[1-1] 같은 경우 크기가 8인 스택에서 4개가 쌓여 있다 라고 보면 됨 가장 먼저 푸시한 데이터는 stk[0] 인 19 마지막 데이터는 stk[ptr-1]인 53임

 하나 차근차근 설명이 필요할것이다.. 

 

예외 처리 클래스 Empty

pop 또는 peek 함수를 호출할 때 스택이 비어 있으면 내보내는 예외처리 

 

예외 처리 클래스 Full

push 함수를 호출할 때 스택이 가득 차 있으면 내보내는 예외처리 

 

초기화 하는 __init__ 함수

__init__ 함수는 스택 배열을 생성하는 등의 준비 작업을 수행함. 매개변수 capacity로 전달받은 값을 스택의 크기를 나타내는 필드인 

self.capacity로 넘겨 원소 수가 capacity이고 모든 원소가 None인 리스트 stk를 생성함 이때 스택이 비어있으면 self.ptr 은 0일테고 

0인상태에서 빼낼려고 하면 Empty 예외 클래스가 호출된다는것 

 

len, is_full, is_empty는 눈치껏 알테니 그냥 넘어가겠음 

# 고정 길이 스택 클래스 FixedStack 구현하기 

from typing import Any


class FixedStack:
    """고정 길이 스택 클래스"""
    
    class Empty(Exception):
        """비어 있는 FixedStack에 팝 또는 피크할 때 내보내는 예외 처리"""
        pass 
    
    class Full(Exception):
        """가득 찬 FixedStack에 푸시할 때 내보내는 예외 처리"""
        pass
    
    def __init__(self, capacity: int = 256) -> None:
        """스택 초기화"""
        self.stk = [None] * capacity   # 스택 본체
        self.capacity = capacity       # 스택의 크기 
        self.ptr = 0                   # 스택 포인터 
        
    def __len__(self) -> int:
        """스택에 쌓여 있는 데이터 개수를 반환"""
        return self.ptr
    
    def is_empty(self) -> bool:
        """스택이 비어 있는지 판단"""
        return self.ptr <= 0 
    
    def is_full(self) -> bool:
        """스택이 꽉찻는지 판단"""
        return self.ptr >= self.capacity

 

 

데이터를 푸시하는 push( ) 함수 

push( ) 함수는 스택에 데이터를 추가함. 그러나 스택이 가득차서 더 이상 푸시할 수 없으면 예외처리 호출 

푸시 작업을 수행한다 라고 할때 그림으로 표현하면 다음과 같음

이 이상으로 더 간단하게 설명해달라고 하면 선물 줄꺼임

데이터를 팝하는 pop( ) 함수 

이건 위엣꺼에 반대임 따로 설명은 하지 않겠음 구지 설명하면 

1. 아무것도 없는데 뺄려고 하면 예외처리 호출 

2. 비어있지 않으면 스택 포인터 1 감소 하고 저장된값 반환 

 

데이터를 들여다보는 peek( ) 함수

peek( ) 함수는 스택의 꼭대기 데이터를 들어다봄 데이터의 입출력이 없으니깐 스택 포인터는 변화없음 

 

스택의 모든 데이터를 삭제하는 clear( ) 함수

clear 함수는 스택에 쌓여 있는 데이터를 모두 삭제함 그냥 스택 포인터를 0으로 맞추면 됨 

  def push(self, value: Any) -> None:
        """stack 에 value를 푸시(데이터를넣음)"""
        if self.is_full():            # 스택이 비어 있으면 
            raise FixedStack.Full     # 예외 처리 발생
        
        self.stk[self.ptr] = value
        self.ptr += 1
        
    def pop(self) -> Any:
        """스택에서 데이터를 팝(꼭대기 데이터를 꺼냄)"""
        if self.is_empty:
            raise FixedStack.Empty
        
        self.ptr -= 1 
        return self.stk[self.ptr]
    
    def peek(self) -> Any:
        """스택에서 데이터를 피크(꼭대기 데이터를 들여다봄)"""
        if self.is_empty:
            raise FixedStack.Empty
        return self.stk[self.ptr - 1]
    
    def clear(self) -> None:
        """스택을 비움"""
        self.ptr = 0

 

데이터를 검색하는 find( ) 함수 

find( ) 함수는 스택 본체의 배열 stk 안에 value와 값이 같은 데이터가 포함되어 있는지 확인하고, 포함되어 있다면 배열 어디에 들어있는지 검색 선형 검색으로 위해서 바닥쪽으로 검색을 진행 즉 배열의 인덱스가 큰쪽에서 작은 쪽으로 스캔을한다 이말임 검색에 성공하면 인덱스 반환 실패면 -1 반환

데이터 개수를 세는 count( ) 함수 

count( ) 함수는 스택에 쌓여 있는 데이터의 개수를 구하여 반환함 

 

데이터가 포함되어 있는지 판단하는 __contains__( ) 함수 

__cotains__는 스택에 데이터가 있는지 판단함 있으면 True 없으면 False 

ex) 스택 s에 데이터 x가 포함되어 있는지 판단은 s.__contains__(x) 뿐만 아니라 x in s 으로 수행 가능 

 def find(self, value: Any) -> Any:
        """스택에서 데이터찾기"""
        for i in range(self.ptr-1, -1, -1): # 꼭대기 부터 진행
            if self.stk[i] == value:  
                return i                    # 검색 성공 
        return -1                           # 검색 실패 
    
    def count(self, value: Any) -> bool:
        """스택 데이터 개수 반환 """
        c = 0
        for i in range(self.ptr):
            if self.stk[i] == value:
                c += 1 
        return c 
    
    def __contains__(self, value: Any) -> bool:
        """스택에 value가 있는지 판단"""
        return self.count(value)
    
    def dump(self) -> None:
        """모든 데이터 출력"""
        if self.is_empty():
            print("스택 비어있음")
        else:
            print(self.stk[:self.ptr])

 

 

 

특별 메서드 __len__ , __contains__ 

__len__ 

클래스에 __len__ 함수를 정의하면 클래스형 인스턴스를 __len__ 함수에 전달할 수 있다. 

예를 들어 클래스형 인스턴스 obj에 대한 __len()__ 함수를 호출하는 obj.__len__를 간단하게 __len__으로 작성할  수 있음 

 

__contains__

클래스에 contains를 적용하면 python의 in을 적용할 수 있음 in 이랑 비슷 

 

 

 

파이썬에는 collection 라이브러리에 deque 가 존재하는데 성능이 좋음 우리가 방금 만든것보다 간단하고 성능도 좋음..

하지만 원론적인걸 이해 해야 좋은걸 활용할 수 있으니 쉬운것만 찾지말기..

 

from typing import Any 
from collections import deque


class Stack:
    def __init__(self, maxlen: int = 256) -> None:
        self.capacity = maxlen
        self.__stk = deque([], maxlen)
    
    def __len__(self) -> int:
        return len(self.__stk)
    
    def is_empty(self) -> bool:
        return not self.__stk
    
    def is_full(self) -> bool:
        return len(self.__stk) == self.__stk.maxlen
    
    def push(self, value: Any) -> None:
        self.__stk.append(value)
        
    def pop(self) -> Any:
        return self.__stk.pop()
    
    def peek(self) -> Any:
        return self.__stk[-1]
    
    def clear(self) -> None:
        return self.__stk.clear()
    
    def find(self, value: Any) -> Any:
        try:
            return self.__stk.index(value)
        except ValueError:
            return -1 
    
    def count(self, value: Any) -> int:
        return self.__stk.count(value)
    
    def __contains__(self, value: Any) -> bool:
        return self.count(value=value)
    
    def dump(self) -> int:
        print(list(self.__stk))
        
        
        

test = Stack()

test.push(13)
print(test.count(13))
test.dump()