자료구조 02. 스택

들어가기 전

배열

<인덱스, 요소> 쌍의 집합

1차원 배열을 선언하는 방법

자료형 배열이름 [배열의_크기];

인덱스의 범위는 0부터 ‘배열의 크기 -1’ 까지이다.

문자열일 때는 반드시 문자열의 끝을 나타내는 NULL 문자 ‘\0’ 이 있어야 한다.

2차원 배열 선언

자료형 배열이름 [행의_크기][열의_크기];

클래스

생성자 : 객체가 생성될 때 멤버 변수에게 초깃값을 제공하고 필요한 초기화 절차를 실행하기 위한 특별한 멤버 함수
소멸자 : 객체가 파괴될 때 뒷 마무리 하는 함수

//기본 생성자
Car () { }

//매개 변수가 있는 생성자
Car(int s, int g, char* n)
    :speed(s), gear(g){			
	Strcpy(name, n);
}

//소멸자는 하나만 존재
~Car(){}

입출력 자료형
정수형 : %d
실수형 : %f
문자형 : %s
등등…

스택 (Stack)

---

후입선출 (LIFO: Last In First Out)

스택은 자료의 입출력이 후입선출로 일어나는 자료구조이다.

스택 상단 : 스택에서 입출력이 이루어지는 부분
스택 하단 : 반대쪽인 바닥 부분
요소 : 스택에 저장되는 것
공백(empty) 상태 : 스택에 요소가 하나도 없는 경우
포화(full) 상태 : 꽉 차서 더 이상 요소를 넣을 수 없는 상태

스택의 연산

연산:
▪ push(x): 주어진 요소 x를 스택의 맨 위에 추가한다.
▪ pop(): 스택이 비어있지 않으면 맨 위에 있는 요소를 삭제하고 반환한다.
▪ isEmpty(): 스택이 비어있으면 참(true)을 아니면 거짓(false)을 반환한다.
▪ peek(): 스택이 비어있지 않으면 맨 위에 있는 요소를 삭제하지 않고 반환한다.
▪ isFull(): 스택이 가득 차 있으면 참(true)을 아니면 거짓(false)을 반환한다.
▪ size(): 스택내의 모든 요소들의 개수를 반환한다.
▪ display(): 스택내의 모든 요소들의 출력한다.

pop 연산에서는 isEmpty 연산을 호출하여 스택이 공백 상태인지 검사해야 하고 push 연산에서는 isFull 연산을 호출하여 스택이 가득 찼는지 확인해야한다.

스택이 처음 시작되면 top 은 -1로 초기화 된다.
top이 MAX_STACK_SIZE-1이면 포화 상태이다.

유사 코드로 표현한 연산들

---

• 유사 코드에서 = 는 비교 연산을 의미한다.

isEmpty

isEmpty()

if top = -1
    then return TRUE
    else return FALSE</code></pre>

isFull

isFull()

if top = MAX_STACK_SIZE-1
    then return TRUE
    else return FALSE

push

push(x) 

if isfull()
     then error "overflow" 
            else top←top+1 
            data[top]←x

pop

pop()

if isEmpty()
    then error "underflow"
    else e ← data[top]
        top ← top-1
        return e