자료구조 스택과 큐 (1)- 스택

"스택(Stack)"
“스택”(stack)은 한 쪽 끝에서만 항목을 삭제하거나 새로운 항목을 저장하는 자료구조이다.

Python에서 스택을 구현하려면,
python 자체의 리스트를 이용하는 방법과
앞서 배운 단순연결리스트(SLL)를 이용하는 방법이 있다.

우선,구현에 앞서 스택을 구성하는 여러가지 연산에 대해 알아보자.
스택에는 여러가지 연산이 존재한다.

첫 번째로,
#Push() 연산
새 항목을 스택 top 자리에 삽입하는 연산이다.
이는,스택이 LIFO(Last In First Out)구조 임을 나타내는 대표적인 연산이다.
*LIFO = “가장 최근(마지막)에 삽입한 항목이 가장 먼저 나오는 구조”
단순연결리스트로 구현했을때는,push는 value를 가지고 있는 노드를
top자리에-즉,연결리스트의 첫 노드로 삽입하는 것이다.

두 번째로,
#Pop() 연산
top 자리에 있는 가장 최근 삽입한 항목을 제거하는 연산이다.
단순연결리스트(SLL)로 스택을 구현할 시,
delete() 연산처럼 레퍼런스를 다음 노드로 갱신해주기만 하면 된다.

마지막으로,
#Peek() 연산
top 자리에 있는 항목을 보여주는 연산이다.

구현은 python으로 하였으며,
단순연결리스트를 이용하여 구현하였다.

#Top 은 스택의 가장 위에 있는 항목을 참조하는 레퍼런스.
#stack이 empty == top = None

class Node:
    def __init__(self, item, link): #노드 생성자
        self.item = item
        self.next = link

def push(item): #스택 push 함수, 새로운 항목을 스택에 저장함
    global top #전역 변수 top, size
    global size
    top = Node(item,top) #새로운 노드를 top으로 선언 동시에 
    size += 1 #크기 증가 (LIFO,Last In First Out)

def peek(): #top의 요소를 출력해주는 peek
    if size != 0: #빈 스택이 아닐때 작동
        return top.item

def pop(): #스택의 항목을 제거하는 pop(top에 있는 항목)
    global top #전역 변수 top,size
    global size
    if size != 0: #빈 스택이 아닐때,
        top_item = top.item #top에 있는 요소를 다른 변수에 저장
        top = top.next #top 갱신(하나를 빼니까,top의 위치 갱신)
        size -= 1 #스택 크기 감소
        return top_item #pop 한 항목 출력

def print_stack(): #스택 출력
    print('top ->\t', end='') #출력 기준 맨 왼쪽부터 top
    p = top 
    while p: #스택 항목 끝까지(요소가 존재할 때 출력)
        if p.next != None: #출력할 다음요소가 존재할 때
            print(p.item, '->', end='')
        else: #마지막 항목일때
            print(p.item, end='')
        p = p.next #출력할 다음 항목으로 넘어감
    print()

아래는 예제 실행코드이다.

top = None #초기화
size = 0

push('apple')
push('orange')
push('cherry')
print('사과,체리,오렌지 push 후:\t',end='') #cherry -> orange -> apple
print_stack()

print('top 항목: ',end ='') #cherry
print(peek())

push('pear')
print('배 push 후:\t\t', end ='') #pear -> cherry -> orange -> apple
print_stack()

pop()
push('grape')
print('pop(), 포도 push 후:\t', end='') #grape -> cherry -> orange -> apple
print_stack()

#실행시)
사과,체리,오렌지 push 후:       top ->  cherry ->orange ->apple
top 항목: cherry
배 push 후:             top ->  pear ->cherry ->orange ->apple 
pop(), 포도 push 후:    top ->  grape ->cherry ->orange ->apple

이 처럼 단순연결리스트(SLL)를 이용하여 스택을 구현할 수 있지만,
python 내부 자체의 리스트를 사용하여 스택을 구현할 수 있다.

다만,구현시
삽입,삭제시 파이썬의 리스트 크기가 동적으로 변화하여,
스택(리스트)의 모든 항목을 다시 새 리스트로 복사해야하기에
단순연결리스트로 구현할 때 보다 더 긴 O(N)이라는 시간이 걸린다.
*참고로 단순연결리스트로 구현하였을때, 삽입 삭제 연산의 시간복잡도는 O(1)이다.
이는 리스트의 맨앞부분에서 노드를 삭제하거나 삽입하기 때문이다.

아래는 파이썬 리스트로 구현한 스택이다.

def push(item): #push 연산
    stack.append(item) #리스트의 맨 마지막에 항목 추가하는 append()

def peek(): #peek 연산
    if len(stack) != 0: #빈리스트가 아닐때
        return stack[-1] #리스트의 맨 마지막 항목을 리턴
    
def pop(): #pop 연산
    if len(stack) != 0: #빈리스트가 아닐때
        item = stack.pop(-1) #리스트의 맨 마지막 항목을 제거
        return item 

#실제 예시
stack = [] #리스트 생성 필요

push('apple')
push('orange')
push('cherry')
print('사과,오렌지,체리 push 후:\t',end='') 
print(stack,'\t<- top')

print('top 항목: ',end='')
print(peek())

push('pear')
print('배 push 후:\t\t', end='')
print(stack, '\t<- top')

pop()
push('grape')
print('pop(), 포도 push 후:\t', end='')
print(stack, '\t<- top')

#실행 결과
사과,오렌지,체리 push 후:       ['apple', 'orange', 'cherry']   <- top
top 항목: cherry
배 push 후:             ['apple', 'orange', 'cherry', 'pear']   <- top
pop(), 포도 push 후:    ['apple', 'orange', 'cherry', 'grape']  <- top

스택은 다양한 문제풀이에 쓰이거나 토대가 되는 자료구조이다.

대표적인 응용으로는,
1.괄호 짝 맞추기
=컴파일러가 소스코드에 있는 괄호들이 짝이 맞는지 검사할 때,
스택을 이용하여 좌에서 우로 항목(괄호)을 읽어가며 검사한다.
왼쪽 괄호는 스택에 push,오른쪽 괄호를 읽으면 pop을 수행한다.
이때, pop된 왼쪽 괄호와 바로 읽었던 오른쪽 괄호가 다른 종류이면 에러처리하고,
같은 종류이면 다음 괄호를 읽는다.
모든 연산을 처리한 후 스택이 empty가 아니면, 짝이 맞지 않은 괄호가 남아있다는 의미이다.
이는 에러처리를 한다.

2.회문(Palindrome)
=회문이란 앞에서 읽으나 뒤에서 읽으나 같은 String을 말한다.
이 회문을 검사할 때, 스택이 이용되는데
주어진 String의 앞부분 반을 차례대로 읽어 스택에 Push 한 후,
문자열 길이가 짝수이면 뒷부분의 문자 1개를 읽을 때마다 pop 하여
읽어들인 문자와 pop된 문자를 비교하는 과정을 반복 수행한다.
마지막 까지 문자가 동일하고, 스택이 empty가 되면, 해당 문자열은 회문이 된다.
단,문자열의 길이가 홀수인 경우, 주어진 스트링의 앞 부분 반을 차례로 읽어 스택에 push 한 후,
중간 문자를 읽고 버린다. 이후 똑같이 진행한다.

이러한 응용외에도, 스택은 미로 찾기, 트리의 순회, 그래프의 탐색을 수행하는데 기본이 된다.
함수 호출도 스택 자료구조를 바탕으로 구현한다.

• 자료구조
• 이론