알고리즘 2주차 - 스택

Keywords : 스택, push, pop, 추상 자료형 (ADT)

 

스택

• 쌓아 올린 형태
• LIFO (후입선출)

 

스택의 연산

• isEmpty : 비어있으면 true
• push : isEmpty 확인 => top += 1 => S(top) = x
• pop : isEmpty 확인 => return S(top) => top -= 1
• delete : isEmpty 확인 => 맨 윗 값 삭제
• peek : isEmpty 확인 => 맨 윗 값 반환

 

순차 자료구조 이용한 스택 구현

• 스택 크기 : 배열 크기
• 스택 저장 순서 : 배열의 인덱스 
• top : 초기값 -1
• 장점 : 구현 쉬움
• 단점 : 크기 변경 어려움 + 순차 자료구조 단점

# 순차 자료구조 이용한 스택 구현
def push(item):
    stack.append(item)

def peek():
    return stack[-1]

def pop():
    if len(stack) != 0:
        item = stack.pop(-1)
        return item

stack = []
push('apple')
push('orange')
push('cherry')
print('After push : ', stack)
print('Top : ' + peek())
print('Pop : ' + pop())
print('After Pop : ', stack)

# 결과
After push :  ['apple', 'orange', 'cherry']
Top : cherry
Pop : cherry
After Pop :  ['apple', 'orange']

 

연결 자료구조 이용한 스택 구현

• 스택 원소 : 노드
• top : 연결 리스트의 마지막 노드 가리키는 포인터 변수, 초기값 null

# 연결 자료구조 이용한 스택 구현
class Node:
    def __init__(self, item, link):
        self.item = item
        self.next = link

def push(item):
    global top
    global size
    top = Node(item, top)
    size += 1

def peek():
    if size != 0:
        return top.item

def pop():
    global top
    global size
    if size != 0:
        top_item = top.item
        top = top.next
        size -= 1
        return top_item

def print_stack():
    print('top -> ', end='')
    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('After push : ', end=''), print_stack()
print('Top : ', peek())
print('Pop : ', pop())
print('After Pop : ', end=''), print_stack()

# 결과
After push : top -> cherry -> orange -> apple
Top :  cherry
Pop :  cherry
After Pop : top -> orange -> apple