[Python 자료구조] 스택 (Stack)

📌스택이란?

스택은 후입선출,LIFO :Last In First Out 구조로, 가장 먼저 들어간 데이터가 맨 아래층에 쌓이고, 가장 나중에 들어간 자료가 맨 위에 쌓인다. 구멍이 하나밖에 없는 병이라고 생각하면 이해하기 쉽다.

📌스택의 기본 연산

◼ push() : 스택에 원소를 추가한다.
◼ pop() : 스택 가장 위에 있는 원소를 삭제하고 그 원소를 반환한다.
◼ peek() : 스택 가장 위에 있는 원소를 반환한다. (원소를 삭제하지는 않는다.)
◼ empty() : 스택이 비어있으면 1, 아니면 0을 반환한다.

📌스택 구현

Stack 생성

파이썬에서는 스택을 리스트 또는 연결리스트로 구현한다. 따라서 처음에 빈 리스트를 만들어서 초기화한다.

class Stack
	#리스트를 이용하여 스택 생성
    def __init__(self):
    	self.top = []

?(.top은 뭐지..)

#스택의 크기(길이)를 출력
	def __len__(self):
    	return len(self.top)
        
#스택에 저장된 모든 데이터를 string 형태로 반환
	def __str__(self):
    	return str(self.top[::1])

Stack 구현 함수

• push

def push (self,item):
	self.top.append(item)

파이썬 list에 내장되어 있는 append함수를 사용하여 리스트 끝에 값을 추가한다.

• pop

def pop(self):
    if not self.isEmpty():
       return self.top.pop(-1) 
        
     else:
        print("Stack underflow")
        exit()

먼저 스택이 비어있는지 확인하고 비어있지 않다면 파이썬 list 안에 내장되어 있는 함수 pop에 -1을 인자로 넘겨 리스트의 가장 마지막에 있는 데이터를 반환한다.

• clear

#스택 초기화
	def clear(self):
    	self.top=[]

Stack 클래스의 멤버변수인 top을 새로운 리스트로 초기화한다.

• isContain

#해당 자료가 포함되어 있는지 여부 반환
	def isContain(self,item):
    	return item in self.top

• peek

#스택의 top값을 읽어온다.
	def peek(self):
    	if is not self.isEmpty():
        	return self.top[-1]
        else:
        	print("Stack is underflow")
            exit()

• isEmpty

def isEmpty(self):
	return len(self.top)==0