🖇️알고리즘 스터디 3주차

jiwon·2023년 8월 6일

스택 알고리즘 자료구조 큐

알고리즘

목록 보기

4/7

스택

: 데이터를 임시 저장할 때 사용하는 자료구조, 데이터는 후입선출 방식.
푸시 / 팝 / 꼭대기 / 바닥 /

스택 배열 stk : 푸시한 데이터를 저장하는 스택 본체, list형 배열.
=> 인덱스가 0 인 원소= 스택의 바닥
스택 크기 capacity : int형, =len(stk)
스택 포인터 ptr : 현재 쌓인 데이터 개수

push() / pop() / peek() / clear() / find() / count() / __contains__() / dump()

# 고정길이 스택 클래스(FixedStack) 사용하기

form enum import Enum		#enumerate() 함수는 인자로 넘어온 목록을 기준으로 인덱스와 원소를 차례대로 접근하게 해주는 반복자(iterator) 객체를 반환해주는 함수

from fixed_stack import FixedStack

Menu=Enum('Menu', ['푸시', '팝', '피크', '검색', '덤프', '종료'])

def select menu() -> Menu:
	s=[f`({m.value}){m.name}' for m in Menu]
    while True:
    	print(*s, sep='	 ', end='')
        n=int(input(': '))
        if 1<=n<=len(Menu):
        	return Menu(n)
            
s=FixedStack(64)			#최대 64개 푸시가능한 스택

while True:
	print(f'현재 데이터 개수: {len(s)/{s.capacity}')
    menu=select_menu()		#메뉴선택
    
    if menu==Menu.푸시:
    	x=int(input('데이터를 입력하세요.: '))
        try:
        	s.push(x)
        except FixedStack.Full:
        	print('스택이 가득 차 있습니다.')
            
    elif menu==Menu.팝:
    	try:
        	x=s.pop()
            print(f'팝한 데이터는 {x}입니다.')
        except FixedStack.Empty:
        	print('스택이 비어있습니다.')
            
    elif menu==Menu.피크:
    	try:
        	x=s.peek()
            print(f'피크한 데이터는 {x}입니다.')
        except FixedStack.Empty:
        	print('스택이 비어있습니다.')
        
    elif menu==Menu.검색:
    	x=int(input('검색할 값을 입력하세요.: '))
        if x in s:
        	print(f'{s.count(x)}개 포함되고, 맨 앞의 위치는 {s.find(x)}입니다.')
        else:
        	print('검색값을 찾을 수 없습니다.')
         
     elif menu==Menu.덤프:
     	s.dump()
     
     else:
     	break

collections.deque로 스택 구현 : 맨 앞과 맨 끝 양쪽에서 원소를 추가, 삭제하는 자료구조인 덱을 구현하는 컨테이너.

# 고정 길이 스택 클래스 collections.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:
    	"""스택에 value를 푸시"""
        self.__stk.append(value)
        
    def pop(self) -> Any:
    	"""스택에서 데이터를 팝"""
        return self.__stk.pop()
    
"""이하 생략"""