스택(stack)

1. 스택(stack)의 특성

• 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조입니다.
• 스택에 저장된 자료는 선형 구조를 갖습니다.
  • 선형구조 : 자료 간의 관계가 1대 1의 관계를 갖습니다.
  • 비선형구조 : 자료 간의 관계가 1대 N의 관계를 갖습니다.(예: 트리)
• 스택에 자료를 삽입하거나 스택에서 자료를 꺼낼 수 있습니다.
• 마지막에 삽입한 자료를 가장 먼저 꺼냅니다. 후입선출(LIFO, Last-In-First-Out)이라고 부릅니다.
  • 예를 들어 스택에 1, 2, 3 순으로 자료를 삽입한 후 꺼내면 역순으로 3, 2, 1 순으로 꺼낼 수 있습니다.

---

2. 스택을 프로그램에서 구현하기 위해서 필요한 자료구조와 연산

• 자료구조 : 자료를 선형으로 저장할 저장소
  • 배열을 사용할 수 있습니다.
  • 저장소 자체를스택이라고 부르기도 합니다.
  • 스택에서 마지막 삽입된 원소의 위치를 top이라고 부릅니다.
• 연산
  • 삽입 : 저장소에 자료를 저장합니다. 보통 push라고 부릅니다.
  • 삭제 : 저장소에서 자료를 꺼냅니다. 꺼낸 자료는 삽입한 자료의 역순으로 꺼냅니다. 보통 pop이라고 부릅니다.
  • 스택이 공백인지 아닌지를 확인하는 연산 : isEmpty
  • 스택의 top에 있는 item(원소)을 반환하는 연산 : peek

---

3. 스택의 삽입 / 삭제 과정

빈 스택에 원소 A, B, C를 차례로 삽입 후 한번 삭제하는 연산과정입니다.

---

4. 스택의 push 알고리즘

append 메소드를 통해 리스트의 마지막에 데이터를 삽입합니다.

def push(item):
    s.append(item)

# [참고]
def push(item, size):
    global top
    top += 1
    if top == size:
        print('overflow!')
    else:
        stack[top]  = item

size = 10
stack = [0] * size
top = -1

push(10, size)
top += 1        # push(20)
stack[top] = 20

---

5. 스택의 pop 알고리즘

def pop():
    if len(s) == 0:
        # underflow
        return
    else:
        return s.pop();

# [참고]
def pop():
    global top
    if top == -1
        prin('underflow')
        return 0
    else:
        top -= 1
        return stack[top+1]

print(pop())

if top > -1:        # pop()
    top -= 1
    print(stack[top+1])

---

6. 스택 구현 고려 사항

• 1차원 배열을 사용하여 구현할 경우 구현이 용이하다는 장점이 있지만 스택의 크기를 변경하기가 어렵다는 단점이 있습니다.
• 이를 해결하기 위한 방법으로 저장소를 동적으로 할당하여 스택을 구현하는 방법이 있습니다. 동적 연결리스트를 이용하여 구현하는 방법을 의미합니다. 구현이 복잡하다는 단점이 있지만 메모리를 효율적으로 사용한다는 장점을 가집니다.

---

연습문제

---

7. 스택의 응용

7-1. 괄호검사

---

연습문제

---

7-2. function call