[TIL] 스택 Stack Python

 

스택 Stack

데이터를 임시 저장하는, 하나씩 쌓아 올린 형태의 자료 구조
LIFO - Last In First Out 또는 FILO - First In Last Out 

 

like 식당에 쌓여있는 접시, 프링글스, 콘 아이스크림 

아래에서부터 쌓고, 위에서부터 꺼내는 방식

스택의 동작은 모두 Top 이라는 스택의 한쪽 끝에서만 일어난다 

출처 https://yoongrammer.tistory.com/45

 

스택 구성

stk 스택 배열 - 푸시한 데이터를 저장하는 스택 본체인 list 형 배열 

capacity 스택 크기 - 스택의 최대 크기를 나타내는 int 형 정수 

ptr 스택 포인터 - 스택이 쌓여 있는 데이터를 개수를 나타내는 정수값 

스택의 연산 

push() Top 에 있는 원소를 제거 

pop(x) 원소 x 를 Top 에 추가 

peek() 스택의 상단에 있는 항목을 제거하지 않고 반환 (Top 요소를 확인만 하고 제거는 하지 않음)

is_empty() 스택이 비어 있는지 확인

size 스택에 있는 항목의 개수를 반환

 

Overflow - 스택이 완전히 꽉 찬 상태에서 추가로 항목을 삽입하려고 할 때 발생 

Underflow - 스택이 완전히 비어있는 상태에서 항목을 제거하려고 할 때 발생 

 

 

스택 코드

class Stack:
    def __init__(self) -> None:
        self.items = []
    
    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        else:
            raise IndexError("Pop from Empty Stack")
        
    def peep(self):
        if not self.is_empty():
            return self.items[-1]
        else:
            raise IndexError("Peek from Empty Stack")
        
    def is_empty(self):
        return len(self.items) == 0
    
    def size(self):
        return len(self.items)

 

Push 작업 단계

1. 스택이 가득 찼는지 확인한다
2. 스택이 가득 차면 오류가 발생하고 종료된다
3. 스택이 가득 차지 않으면 Top 값을 증가시킨다
4. Top 이 가리키는 스택 위치에 데이터를 추가한다 

 

Pop 작업 단계

1. 스택이 비어 있는지 확인한다
2. 스택이 비어 있으면 오류가 발생하고 종료된다
3. 스택이 비어 있지 않으면 Top 이 가리키는 데이터를 제거한다 
4. Top 값을 감소시킨다 
5. 성공을 반환한다 

 

시간 복잡도

Operation	Average	Worst
Access	O(n)	O(n)
Search	O(n)	O(n)
Push	O(1)	O(1)
Pop	O(1)	O(1)

Push 와 Pop 은 항상 Top 에서만 일어나기 때문에 O(1) 시간이 걸린다   

스택의 장단점 

1. 배열 사용

 - 장점 ; 구현하기 쉬움

 - 단점 ; 크기가 동적이 아님 (고정되어 있음)

 

2. 연결 리스트 사용

 - 장점 ; 크기가 동적임 

 - 단점 ; 포인터를 위한 추가 메모리 공간이 필요함 

 

스택 사용 예시

1) 괄호 짝 맞추기

2) 10진수를 2진수로 변환하기 

 

 Deque 양방향 연결리스트 Python

# 양방향 연결리스트 정의
class Node:
    def __init__(self, item):
    	self.data = item
        self.prev = None
        self.next = None 

class DoublyLinkedList:
    def __init__(self, item):
    	self.nodeCount = 0
        self.head = Node(None)
        self.tail = Node(None)
        
        self.head.prev = None
        self.head.next = self.tail
        self.tail.prev = self.head
        self.tail.next = None
 
 # 양방향 연결리스트로 스택 구현
 class LinkedListStack:
     def __init__(self):
     	self.data = DoublyLinkedList()
     
     def size(self):
     	return self.data.getLength()
     
     def isEmpty(self):
     	return self.size() == 0
     
     def push(self, item):
     	node = Node(item)
        self.data.insertAt(self, size() +1, node)
     
     def pop(self):
     	return self.data.popAt(self.size())
     
     def peek(self):
     	return self.data.getAt(self.size()).data