자료구조 알고리즘 Chapter 1 스택

이승우·2025년 7월 9일

자료구조 파이썬

자료구조 알고리즘

목록 보기

1/2

1-1 스택

요소(element)의 입출력이 후입선출(LIFO)
ex) 입력:A->B->C, 출력:C->B->A
스택 상단(stack top): 열린 곳. 입출력은 스택 상단에서만 가능

스택 활용

웹 브라우저의 [되돌리기(undo)]

첫 페이지에서 '스포츠' 페이지로 이동하면 페이지의 링크가 스택에 삽입
[이전 페이지로 이동] 하면 스택에서 삭제

추상 자료형

기본 자료형 : int, float, str...
문제 해결을 할때 기본 자료형만으로는 불편, 비효율적
-> 새로운 자료형 정의 - 필수적이고 중요한 특징만 골라서 단순화 시킴 (추상화 abstraction)
추상 자료형(ADT: Abstract Data Type) : 추상화를 통해 정의한 자료형
ex) push, pop, isEmpty, isFull..

ex) 스택의 추상 자료형 - 스택이 어떤 자료를 다루고, 어떤 연산이 필요한지를 정의하는 것

스택의 연산

push(e) #새로운 요소 e를 스택의 맨 위에 추가
pop() #스택 상단의 요소 꺼내서 반환
isEmpty() #스택 비어있으면 True, 아니면 False를 반환
isFull() #스택이 가득 차 있으면 True, 아니면 False를 반환
peek() #스택의 맨 위에 있는 항목을 삭제하지 않고 반환(상태 변하지 않음)
size() #스택에 들어 있는 전체 요소의 수를 반환

스택 연산 오류

오버플로 : 포화 상태에 새로운 요소 삽입 시
언더플로 : 공백 상태에 pop()이나 peek() 호출 시

1-2 배열 구조 스택 구현

자료구조의 구현 방법 - 배열 구조 / 연결된 구조

배열 구조 : 모든 요소는 인접한 메모리 공간에 저장. 공간이 가득 차면 추가 불가능
연결된 구조 : 인접한 메모리 공간이 아닌 흩어져 있는 요소들을 연결. 각 요소의 위치를 바꾸거나 새로운 요소를 쉽게 추가, 삭제 가능. (배열보다 유연하게 사용, 관리가 복잡)

배열 구조의 스택을 위한 데이터

array[] #스택 요소 저장할 배열
capacity #스택의 최대 용량(상수)
top #스택 상단 요소의 위치(변수, 인덱스)

#데이터 준비
capacity = 10
array = [None]*capacity #모든 요소 None으로 초기화, 길이=10
top = -1 #스택 상단 인덱스의 위치를 -1로 초기화. 비어있다는 뜻

isEmpty/isFull 구현

def isEmpty():
  if top == -1: return True #top이 
  else : return False
def isFull() : return top == capacity-1 #array는 0~9이기 때문

push(e) 연산

포화 상태가 아니라면 top 하나 증가
그 위치에 요소 e를 복사

def push(e) :
  global top #함수 안에서 변수 값 변경하기 위해서
  if not isFull() :
    top += 1
    array[top] = e
  else :
    print("stack overflow")
    exit()
    
push(10)
print(array[:top+1])

->[10]

pop() 연산

공백 상태가 아니라면 top 위치 요소 반환
top 하나 감소

def pop() :
    global top
    if not isEmpty():
        value = array[top]
        top -= 1
        return value
    else:
        print("stack underflow")
        exit()

문제

여러개의 스택이 동시에 필요한 문제에 사용할 수 없음 -> 전역 변수로 선언된 배열이 하나이므로 하나의 스택만 존재할 수 있음

스택을 객체 지향 프로그래밍으로 구현

추상 자료형(ADT)는 함수를 기반으로 하는 절차지향이다.
자료구조는 클래스를 기반으로 하는 객체 지향이 좋다.

전역 변수는 모두 클래스의 멤버변수로 옮겨야 한다
-> __init__() 이라는 생성자로 멤버변수 선언, 초기화

파이썬은 C++이나 Java와 다르게 생성자를 포함한 클래스의 모든 멤버함수의 첫 번쨰 매개변수로 객체 자신을 나타내는 'self'를 넣는다. (C++의 this 역할)

클래스의 모든 메서드에서 다른 메서드나 멤버 변수를 사용할때 앞에'self.' 추가

class ArrayStack :
    def __init__(self, capacity): #ArrayStack 클래스 생성자
        self.capacity = capacity
        self.array = [None]*self.capacity
        self.top = -1

s1 = ArrayStack(10) #용량 20 객체 s1 생성
s2 = ArrayStack(30) #용량 30인 객체 s2 생성

이승우

다음 포스트

자료구조 알고리즘 Chapter 1 스택