Stack 개념 및 사용법

📍 스택이란?

나중에 저장된 데이터가 먼저 나오는 구조이다.
데이터의 삽입과 삭제가 한쪽 끝에서만 일어나는 선형 자료구조이다. ex) 프링글스

스택은 가장 먼저 들어간 자료가 맨 아래쪽에 쌓이고, 가장 나중에 들어간 자료가 맨 위에 쌓이기 때문에, 먼저 들어간 자료일 수록 나중에 나오고, 늦게 들어갈 수록 더 빨리 나온다.
이를 후입선출 구조라고 하고, 영어로는 LIFO : Last In First Out 라고 한다.

📍 Stack의 기본 연산

• push(), pop() : 데이터 삽입, 삭제 -> pop의 경우 데이터가 비어있는지 확인 후 실행하기
• top() = peek() : 가장 마지막 데이터(위에 있는 데이터)를 삭제 하지 않고 리턴하는 메소드
• isEmpty() : 현재 스택이 비어있는지 확인하는 메소드

💡 Stack 파이썬 코드로 구현하기

1. 파이썬에서는 스택을 리스트 또는 연결리스트로 구현
2. 강력한 내장함수를 제공해주는 리스트로 구현하면 간단함
3. S.append() 리스트 맨 끝에 원소를 추가한다. 시간복잡도는 O(1)
4. S.pop(i) 리스트의 i번째 원소를 삭제한다. S.pop(-1)은 맨 앞에 있는 원소를 삭제한다. 시간복잡도는 O(1)

1. python의 List로 구현하기

class Stack(): 
    def __init__(self): 
    	self.stack = [] 
        
    def push(self, data):   #list의 append로 구현
    	self.stack.append(data) 
        
    def pop(self): 
    	pop_object = None 
        if self.isEmpty():  #스택이 비어있는지 확인
            print("Stack is Empty") 
        else:   #스택이 비어있지 않으면 마지막 값을 꺼내 리턴
            pop_object = self.stack.pop() 
        return pop_object 
        
     def top(self): 
     	top_object = None 
        if self.isEmpty(): 
           print("Stack is Empty") 
        else: 
           top_object = self.stack[-1]  #마지막 값을 리턴
        return top_object 
        
     def isEmpty(self): 
     	is_empty = False 
        if len(self.stack) == 0: #빈 경우는 True
           is_empty = True 
       	return is_empty

📍 Stack 라이브러리

파이썬 내장모듈에서는 따로 스택 라이브러리가 존재하지 않는다.
보통 덱 라이브러리를 import 해서 스택 대신 사용한다.

from collections import deque

dq=deque() # 덱 생성
dq.append() # 덱의 가장 오른쪽에 원소 삽입
dq.popleft() # 가장 왼쪽 원소 반환
dq.appendleft() # 덱의 가장 왼쪽에 원소 삽입
dp.pop() # 가장 오른쪽 원소 반환
dp.clear() # 모든 원소 제거
dp.copy() # 덱 복사
dp.count(x) #x와 같은 원소의 개수를 계산