[자료구조] - Python으로 스택 간단 구현하기

✅스택이란?

2022.08.24 - [기타] - [자료구조] - 스택 (Stack)

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

---

 

📍ADT Stack

ADT(Abstract Data Type)란?
프로그래밍 언어에서 사용되는 데이터형을 정의함에 있어서 그 데이터형에 적용 가능한 연산 형식과 제약 조건 등만을 보여주고 실제로 그 연산이 어떻게 구체적으로 표현되어 있는지는 알 수 없게 하는 기능.
출처 : 추상 데이터형 [abstract data type, 抽象-型] (컴퓨터인터넷IT용어대사전, 전산용어사전편찬위원회)

→ 간단히 말해, 구현 방법은 알리지 않고 실제 기능이나 형식(e.g. 함수)을 정의해 놓은 것.

• push(item) : 스택에 데이터(item) 추가
• pop() : 스택 맨 위 원소를 제거하고 반환
• peek() : 스택의 맨 위의 값을 반환 (제거하지 않음)
• clear() : 스택 안 모든 값 강제 초기화
• isEmptyStack() : 스택이 비어있는지 여부 확인 (비어있다면 True, 비어있지 않다면 False)
• isFullStack() : 스택이 가득 찼는지 여부 확인 (차 있다면 True, 차있지 않다면 False)
• size() : 현재 스택에 들어있는 원소의 개수 반환 (크기 확인)
• display() : top 위치에 있는 원소부터 차례대로 출력

 

 

 

 

🚩스택 구현하기 - 부분 설명

 

1. 클래스 생성과 __init__

class STACK:
    def __init__(self, max_size=5):
        self.stack = []
        self.top = -1
        self.max = max_size-1

STACK이라는 클래스를 생성해주었다.

 

__init__ 함수

1. 원소를 넣어줄 리스트 생성
   이 리스트가 원소가 들어갈 스택 역할을 하는 것이다.
2. top 변수를 선언해준다.
   top가 -1인 이유는 스택이 비어있는 상태로 설정해주기 위함이고, 리스트는 0번지부터 시작하기 때문이다.
3. 스택의 최대 크기를 정해준다.
   위에서 max_size를 정해주었는데, 이는 5개의 원소를 넣을 수 있다는 의미로 정해주었다.
   max_size-1을 해준 이유는 첫 번째 원소의 인덱스 값이 0이기 때문에 총 5칸을 만들어주기 위함이다.

 

 

2. isEmptyStack()과 isFullStack()

    def isEmptyStack(self):
        if self.top == -1:
            return True
        else:
            return False

    def isFullStack(self):
        if self.top == self.max:
            return True
        else:
            return False

push와 pop을 해주기 위해서는 먼저 스택이 완전히 비워져 있는지, 혹은 꽉 차있는지를 알아야 한다. (오버플로우, 언더플로우 확인)

따라서 스택의 상태를 검사해줄 함수 isEmptyStack()과 isFullStack()을 먼저 선언해줄 것이다.

 

isEmptyStack 함수

1. 만약 top이 -1(스택이 완전히 비워져 있음)이라면 True를 반환하고, 아니라면 False를 반환해준다.

isFullStack 함수

1. 만약 top이 스택의 최대 크기와 일치(스택이 완전히 차있음)한다면 True를 반환하고, 아니라면 False를 반환해준다.

 

 

3. peek()

    def peek(self):
        if self.isEmptyStack() == True:
            print("Stack is empty.")
        else:
            return self.stack[self.top]

먼저, 스택이 비어있는지 검사해주어 비어있다면 "Stack is empty."라는 메시지를 띄워준다.

비어있지 않다면 스택 맨 위의 값인 top을 반환해준다.

 

 

 

4. clear()

    def clear(self):
        self.stack = []
        self.top = -1

stack 변수를 다시 빈 리스트로 선언해주고, top의 값도 -1로 저장해준다.

 

 

 

5. size()

    def size(self):
        return len(self.stack)

len()을 이용해 스택의 크기를 반환해준다.

 

 

 

6. display()

    def display(self):
        for a in reversed(self.stack):
            print(a)

스택 안 값들을 top을 기준으로 출력해준다. (top을 제일 먼저 출력)

 

 

 

7. push()

    def push(self, item):
        if self.isFullStack() == True:
            print("Stack is full.")
        else:
            self.stack.append(item)
            self.top += 1

스택이 가득 차 있는지 검사를 해주고 가득 차 있다면 "Stack is full"을 출력해준다.

가득 차 있지 않다면 stack 안에 item 인자 값을 추가해주고, top의 위치를 1 증가시켜준다.

 

 

 

8. pop()

    def pop(self):
        if self.isEmptyStack() == True:
            print("Stack is empty.")
        else:
            pop_item = self.stack[self.top]
            del self.stack[self.top]
            self.top -= 1
            return pop_item

스택이 비어있는지 검사를 해주고 비어있다면 "Stack is empty."를 출력해준다.

완전히 비어있지 않다면 pop_item 변수에 스택의 가장 위 원소를 저장해주고, 그 값을 스택에서 삭제해준다.

top의 위치 값도 1 감소시켜준다.

마지막으로 pop_item(스택 맨 위의 값)을 반환해준다.

 

 

 

 

 

🔎전체 코드

class STACK:
    def __init__(self, max_size=5):
        self.stack = []
        self.top = -1
        self.max = max_size-1

    def isEmptyStack(self):
        if self.top == -1:
            return True
        else:
            return False

    def isFullStack(self):
        if self.top == self.max:
            return True
        else:
            return False

    def peek(self):
        if self.isEmptyStack() == True:
            print("Stack is empty.")
        else:
            return self.stack[self.top]

    def clear(self):
        self.stack = []
        self.top = -1

    def size(self):
        return len(self.stack)

    def display(self):
        for a in reversed(self.stack):
            print(a)

    def push(self, item):
        if self.isFullStack() == True:
            print("Stack is full.")
        else:
            self.stack.append(item)
            self.top += 1

    def pop(self):
        if self.isEmptyStack() == True:
            print("Stack is empty.")
        else:
            pop_item = self.stack[self.top]
            del self.stack[self.top]
            self.top -= 1
            return pop_item