1 자료구조 스택

스택(stack): 데이터의 삽입과 삭제가 한쪽 방향에서만 일어나는 구조. 가장 최근에 삽입된 데이터가 가장 먼저 삭제 되기때문에 후입 선출(LIFO: Last-In  First Out)구조라고도 함.

스택은 배열을 이용하거나 연결리스트를 이용하여 구현가능

다음 그림은 스택의 동작 원리를 보여주는 그림이다.

스택의 초기상태가 다음과 같이 있다. 저 스택에서 데이터 4를 push 한다면 다음 그림과 같다.

스택은 후입 선출 구조이기 때문에 스택의 가장 윗 부분에 데이터가 쌓인다고 생각하면 편하다.

저 상태에서 pop 을 한다면 다음 그림과 같은 상태가 된다.

데이터의 삭제또한 한 방향에서 일어나기 때문에 가장 최근에 들어온 데이터 4가 삭제된다.

 

스택의 연산의 종류는 다음과 같다.

연산	설명
pop	데이터 삽입
push	데이터 삭제
peek	제일 윗 부분 데이터 확인
isEmpty	스택이 비어있는지 확인

기본적인 스택의 동작은 위와 같고 파이썬으로 구현한 스택의 소스코드는 다음과 같다.

stack = list()			#스택 생성
stack.append(1) 		#1을 스택에 삽입
stack.append(2) 		#2를 스택에 삽입
stack.append(3) 		#3을 스택에 삽입
print(stack)    		#현재 스택의 상태 출력
print(stack.pop())      	#스택의 가장 최근 데이터를 꺼내면서 출력
print(stack)    		#현재 스택의 상태 출력

파이썬에서는 스택에 필요한 기능이 이미 리스트 안에 구현이되어있어 리스트 자료구조를 이용하여 스택을 구현하였다.

다음 소스코드는 클래스를 이용한 스택의 구현이다.

class stack:
    def __init__(self):
        self.items = []
    def push(self, item):
        self.items.append(item)
    def pop(self):
        if self.isEmpty():
            return #스택이 비어있을시 예외 처리
        else:
            return self.items.pop()
    def peek(self):
        if self.isEmpty():
            return #스택이 비어있을시 예외 처리
        else:
            last_index = len(self.items) - 1
            return self.items[last_index]
    def isEmpty(self):
        return not self.items

stk = stack()           # stack 객체 생성
print(stk)              # stack 생성 확인
print(stk.isEmpty())    # 스택이 비어있으므로 True 출력
stk.push(1)             # 스택에 1 삽입
stk.push(2)             # 스택에 2 삽입
stk.push(3)             # 스택에 3 삽입
print(stk.pop())        # 스택의 가장 최근 데이터 3을 꺼내면서 출력
print(stk.peek())       # 스택의 가장 윗부분 데이터 확인
print(stk.pop())        # 스택의 가장 최근 데이터 2를 꺼내면서 출력
print(stk.pop())        # 스택의 가장 최근 데이터 1을 꺼내면서 출력
print(stk.isEmpty())    # 스택이 비어있으므로 True 출력

다음 소스코드는 동적 연결리스트를 이용한 스택 자료구조의 구현이다.

class Node:
    def __init__(self, value):
        self.data = value
        self.prev = None

    def __str__(self):
        return str(self.data)

class Stack:
    def __init__(self):
        self.head = None

    #데이터 삽입
    def push(self, value):
        new_node = Node(value)
        new_node.prev = self.head
        self.head = new_node

    #데이터 삭제
    def pop(self):
        if self.isEmpty():
            return #스택이 비어있을시 예외 저리
        else:
            value = self.head.data
            self.head = self.head.prev
            return value

    #마지막 원소 확인
    def peek(self):
        if self.isEmpty():
            return #스택이 비어있을시 예외 처리
        else:
            return self.head.data

    def isEmpty(self):
        return not self.head

stk = Stack()           # stack 객체 생성
print(stk)              # stack 생성 확인
print(stk.isEmpty())    # 스택이 비어있으므로 True 출력
stk.push(1)             # 스택에 1 삽입
stk.push(2)             # 스택에 2 삽입
stk.push(3)             # 스택에 3 삽입
print(stk.pop())        # 스택의 가장 최근 데이터 3을 꺼내면서 출력
print(stk.peek())       # 스택의 가장 윗부분 데이터 확인
print(stk.pop())        # 스택의 가장 최근 데이터 2를 꺼내면서 출력
print(stk.pop())        # 스택의 가장 최근 데이터 1을 꺼내면서 출력
print(stk.isEmpty())    # 스택이 비어있으므로 True 출력