[Algorithm] 자료구조와 알고리즘 - 3. 자료구조 - 스택(Stack)

 

이 포스팅은 <파이썬 자료구조와 알고리즘 for beginner>를  학습하면서 정리한 내용이다.

https://www.yes24.com/Product/Goods/97142842

파이썬 자료구조와 알고리즘 for Beginner - 예스24

---

스택(Stack)

입구와 출구가 하나, 먼저 들어간 데이터가 가장 나중에 나오게 되는 구조

 

스택 : 한쪽이 막힌 파이프

• push : 스택에 데이터를 삽입
• pop : 스택에 데이터를 추출
• top : 스택에 들어있는 가장 위에 있는 데이터

 

 

Stack Overflow 

Stack 영역의 메모리가 지정된 범위를 넘어갈 때 발생

overflow 일어날 수 있으므로 스택 full 인지, Empty인지  확인해야 한다.

• isStackFull() 스택이 꽉 찼는지 확인하는 함수 생성
  • 확인방법 : top == SIZE(스택 메모리 사이즈) -1,
• isStackEmpty()
  • 확인방법 : top == -1

---

01. 삽입/추출/확인 단순 구현

## 함수


## 변수
#stack = [None, None, None, None, None]
SIZE = 5
stack = [None for _ in range(SIZE)]
top = -1

## 메인

## Push()
top += 1
stack[top] = '커피'
top += 1
stack[top] = '녹차'
top += 1
stack[top] = '꿀물'
print('바닥:', stack)

## Pop()
data = stack[top]
stack[top] = None
top -= 1
print('팝-->', data)
data = stack[top]
stack[top] = None
top -= 1
print('팝-->', data)
data = stack[top]
stack[top] = None
top -= 1
print('팝-->', data)

print('바닥:', stack)

---

02. 삽입/추출/확인 스택의 일반구현

*코드 구현 과정

 

1. 스택 초기화 ( SIZE 값에 따라 구조 변경)

## 변수 SIZE = 5 stack = [None for _ in range(SIZE)] top = -1 # top 이 비어있는 상태를 초깃값으로 설정

2. 데이터 삽입

• 스택이 꽉 찼는지 확인 (True/ False)

## 함수 def isStackFull() :     global SIZE, stack, top     if (top >= SIZE-1) :         return True     else :         return False

 

• 스택에 데이터를 삽입하는 함수 Push

def push(data) :     global SIZE, stack, top     if (isStackFull()) :         print('스택 꽉!')         return     top += 1     stack[top] = data

 

3. 데이터 추출 

 

• 스택이 비어있는지 확인하는 함수 isStackFull()

def isStackEmpty() :     global SIZE, stack, top     if (top <= -1) :         return True     else :         return False

 

• 스택에서 데이터를 추출하는 함수 pop

def pop() :     global SIZE, stack, top     if (isStackEmpty()) :         print('스택 텅~')         return     data = stack[top]     stack[top] = None     top -= 1     return data

 

## 함수
def isStackFull() :
    global SIZE, stack, top
    if (top >= SIZE-1) :
        return True
    else :
        return False

def push(data) :
    global SIZE, stack, top
    if (isStackFull()) :
        print('스택 꽉!')
        return
    top += 1
    stack[top] = data

def isStackEmpty() :
    global SIZE, stack, top
    if (top <= -1) :
        return True
    else :
        return False

def pop() :
    global SIZE, stack, top
    if (isStackEmpty()) :
        print('스택 텅~')
        return
    data = stack[top]
    stack[top] = None
    top -= 1
    return data

def peek() :
    global SIZE, stack, top
    if (isStackEmpty()) :
        print('스택 텅~')
        return
    return stack[top]

## 변수
SIZE = 5
stack = [None for _ in range(SIZE)]
top = -1

## 메인
push('커피')
push('녹차')
# push('꿀물')
# push('콜라')
# push('환타')
# print('바닥:', stack)
# push('게토레이')
print('바닥:', stack)

retData = pop()
print('팝데이터==>', retData)

print('다음 데이터:', peek())

retData = pop()
print('팝데이터==>', retData)
retData = pop()
print('팝데이터==>', retData)
print('바닥:', stack)

출력

바닥: ['커피', '녹차', None, None, None] 팝데이터==> 녹차 다음 데이터: 커피 팝데이터==> 커피 스택 텅~ 팝데이터==> None 바닥: [None, None, None, None, None]