스택

스택

스택이란

한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조로 되어있는 자료구조입니다.

 

즉 앞에서 배운 연결리스트와 개념이 비슷합니다.

 

 

 

 

 

 

 

 

 

후입 선출

만약 [1,2,3]이 있었고 4를 추가로 넣었다면

결과는 [1,2,3,4]가 될 것입니다.

 

이때 데이터를 출력할 때 가장 최근에 넣었던 4가 출력이 됨을 의미합니다.

 

 

 

 

 

 

 

 

구조

스택의 구조는 총 3가지로 분류할 수 있습니다.

 

---

탑

스택의 가장 위에 있는 원소

가장 최근에 들어온 원소

 

바텀

스택의 가장 아래에 있는 원소

가장 예전에 들어온 원소

 

스택의 크기

스택에 들어가있는 데이터의 개수

 

---

 

 

 

 

 

 

 

 

 

푸시(push)

푸쉬는 자료를 넣는 것을 의미합니다.

즉 스택에서 기존의 탑 위에 새로운 원소를 추가합니다.

 

 

 

 

 

 

 

 

팝(pop)

자료를 삽입하는 푸시와는 반대로

팝은 넣어둔 자료를 꺼내는 것을 의미합니다.

 

위에서 설명했던 것처럼 스택의 특징인 후입선출에 따라

스택에 들어가있던 원소들 중 가장 최근에 들어온 원소를 꺼냅니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

구현

앞에서 알아보았던 연결리스트처럼

스택 역시 연결리스트를 이용하여 구현할 수 있습니다.

 

실제로 구현해보면 알고리즘 자체가 비슷함을 알 수 있습니다.

 

 

 

먼저 노드 클래스를 생성하겠습니다.

 

class Node:
    def __init__(self, data, next):
        self.data = data
        self.next = next

 

앞에서 다룬 노드와 같은 것이기 때문에 코드 역시 동일합니다.

 

 

 

 

 

다음은 스택 클래스를 만들고

생성자, 크기 그리고 비어있는지 확인하는 메소드를 생성하겠습니다.

 

class LinkedListStack:
    def __init__(self):
        self.no = 0
        self.top = None
        
    def __len__(self):
        return self.no
    
    def is_empty(self):
        return self.top is None

이렇게 연결리스트의 초기환경을 구성해주었습니다.

 

 

 

 

push

이번에 생성해볼 메서드는 푸시이며,

위에서 설명했던 것처럼 스택에 데이터를 삽입하는 메서드입니다.

 

def push(self, data):
    ptr = self.top
    self.top = Node(data, ptr)
    self.no += 1

 

위 코드를 보시면 일전에 생성해보았던

add_first메소드와 유사함을 확인할 수 있습니다.

 

 

 

 

 

 

 

 

pop

스택이 비어있지 않다면, 

스택의 top에 위치한 데이터를 꺼냅니다.

 

예를 들어 top이 C인 [A B C] 스택이 존재한다면

pop이후의 스택의 모습은 [A B]가 됩니다.

 

즉 뒤에서 다루는 peek과는

탑에 있는 데이터를 리턴한다는 점에서는 동일하지만

pop은 리턴된 데이터가 삭제되고,

peek은 리턴된 데이터가 삭제되지 않는다는 차이가 있습니다.

 

만약 스택이 비어있다면 IndexError를 일으킵니다.

 

def pop(self):
    if not self.is_empty():
        data = self.top.data
        self.top = self.top.next
        self.no -= 1
        return data

    else:
        raise IndexError("Stack is empty")

 

 

 

 

 

 

 

 

peek

위에서 말했던 것처럼 pop과 비슷하게

탑에 있는 데이터를 가져옵니다.

 

하지만 pop과는 다르게 가져온 데이터를 삭제하지 않습니다.

 

만약 스택이 비어있다면 IndexError를 일으킵니다.

 

def peek(self):
    if not self.is_empty():
        return self.top.data
    else:
        raise IndexError("Stack is empty")

 

 

 

 

 

 

 

 

print

스택에 있든 모든 데이터를

top에서 부터 순서대로 출력합니다.

 

이 역시 탑이 C인 스택 [A B C]가 있고 print메소드를 호출하게 되면

Top:C->B->A 가 출력되게 됩니다.

 

def print(self):

    ptr = self.top
    print("Top:", end='')
    while ptr is not None:
        print(ptr.data, end='')
        if ptr.next is not None:
            print('->', end='')
        else:
            print()
        ptr = ptr.next

 

 

 

 

 

 

 

 

find

스택에 있는 데이터들 중

지정한 data가 들어 있는 위치를 리턴합니다.

 

만약 발견하지 못하면 -1를 리턴합니다.

 

def find(self, data):
    idx = 0
    ptr = self.top
    while ptr is not None:
        if ptr.data == data:
            return idx
        idx += 1
        ptr = ptr.next
    return -1

 

 

 

 

 

 

 

 

__contains__

스택안에 지정한 data가 존재하면

True를 리턴합니다.

 

def __contain__(self, data):
    return self.find(data) >= 0

 

 

 

 

 

 

 

 

clear

스택 내에 있는 모든 데이터를 지웁니다.

 

def clear(self):
    while not self.is_empty():
        self.pop()
    self.no = 0

 

 

 

 

 

 

 

 

 

 

하지만 파이썬에는 이미 위 스택을 리스트로 구현해놓았습니다.

 

그래서 이번에는 파이썬의 리스트를 이용하여

스택 클래스를 구현해보도록 하겠습니다.

 

class Stack:
    def __init__(self):
        self.stack = []
        
    def is_empty(self):
        return len(self.stack) == 0
    
    def pop(self):
        if not self.is_empty():
            return self.stack.pop()  # 파이썬 리스트의 pop 함수 존재
        else:
            raise IndexError("Stack is empty")
            
    def push(self, data):
        self.stack.append(data)  # 파이썬 리스트의 append 함수 사용
        
    def peek(self):
        if not self.is_empty():
            return self.stack[-1]  # 리스트의 가장 최근 값을 리턴
        else:
            raise IndexError("Stack is empty")
            
    def print(self):
        print(f"{self.stack} : Top")
        
    def clear(self):
        while not self.is_empty():
            self.pop()  # 리스트가 비어있을 때까지 pop 연산 반복
    
    def __len__(self):
        return len(self.stack)

 

위 코드처럼 파이썬의 리스트 함수들을 사용하여

stack을 구현할 수 있습니다.

 

append() 함수를 이용하여 push 연산이 가능하며,

pop() 함수를 이용하여 pop연산이 가능하고,

-1 인덱싱을 이용하여 peek연산이 가능하며,

len() 함수를 이용하여 스택의 크기를 리턴할 수 있습니다.