스택 (Stack)
[제 9 주]
강 지 훈 jhkang@cnu.ac.kr
주요 내용
스택 (Stack)
동적 할당
특수한 리스트
“스택 (Stack)”
스택 (Stack)
삽입과 삭제가 리스트의 핚쪽 끝에서만 발생핚다.
LIFO (Last-In-First-Out) 리스트라고도 핚다.
S = (a
0, • • • , a
n-1)
객체로서 필요핚 기능들: 공개 함수
new(): 스택의 생성
free(): 스택의 소멸
isEmpty (): 스택이 비었는지 검사
isFull (): 스택이 꽉 찼는지 검사
push () : 스택에 삽입
bottom elementtop element
스택의 예
“” 기호는 스택의 top 원소를 가리킨다
F
E
E E
C
D
D D D
B
B B
B B B B
A
A A A A A A A
push(A) push(B) push(C) pop() push(D) push(E) push(F) pop()
Class “STACK”의 사용자적 관점에서의
“공개 함수”
Stack을 위한 공개함수
STACK 객체의 생성
STACK * STACK_New ()
STACK 객체의 소멸
void STACK_Free (STACK *s)
STACK 객체의 점검
boolean STACK_isEmpty (STACK *s)
스택이 empty 이면 TRUE를, 아니면, FALSE를 얻는다.
boolean STACK_isFull (STACK *s)
스택이 full 이면 TRUE를, 아니면, FALSE를 얻는다.
STACK 객체에게 행위를 지시
void STACK_push (STACK * s, ELEMENT e)
스택에 e 를 삽입핚다.
ELEMENT STACK_pop (STACK *s)
스택의 top에서 원소를 삭제하고 그 값을 얻는다.
Class “STACK”의 구현
- Array List를 이용 -
Array List를 이용한 스택의 구현
STACK의 속성들
#define MaxStackSize 100 typedef int ELEMENT ;
// ELEMENT 자료형은 응용에 따라 적절하게 정핚다.
typedef struct {
int top ;
ELEMENT element[MaxStackSize] ; } STACK ;
객체 포인터 선언 STACK * s ;
s
element
-1
top
……
[0] [1] [Max-1]
예: push 와 pop에 따른 스택의 변화
F
E
E E
C
D
D D D
B
B B
B B B B
A
A A A A A A A
push(A) push(B) push(C) pop() push(D) push(E) push(F) pop()
top: -1 0 1 2 1 2 3 4 3
element []
STACK의 Public function의 구현 [1]
객체의 생성
STACK * STACK_new( )
{
STACK * s ;
s = NewObject(STACK) ;
s->top = -1 ; // 스택 초기화 return s ;
}
#define NewObject(TYPE) (TYPE *) malloc(sizeof(TYPE))
STACK의 Public function의 구현 [2]
객체의 소멸
void STACK_free(STACK * s) {
free(s) ;
}
STACK의 Public function의 구현 [3]
STACK Empty 검사
boolean STACK_isEmpty (STACK * s) {
return ( (s->top) < 0 ) ; }
STACK Full 검사
boolean STACK_isFull (STACK * s) {
return ( (s->top) == (MaxStackSize-1) ) ;
}
STACK의 Public function의 구현 [4]
스택에 삽입
void STACK_push (STACK * s, ELEMENT e) {
if ( STACK_isFull(s) ) {
/* Stack Full 처리 */
}
else {
s->top++ ;
s->element[s->top] = e ; }
}
STACK의 Public function의 구현 [5]
스택에서 삭제
ELEMENT STACK_pop (STACK * s) {
ELEMENT e ;
if ( STACK_isEmpty(s) ) { /* Stack Empty 처리 */
}
else {
e = s->element[s->top] ; s->top-- ;
return e ; }
}
동적 메모리 할당
(Dynamic Memory Allocation)
- 보다 구체적인 내용 -
동적 메모리 할당 [1]
C에서는 프로그램 실행 중에 필요핚 메모리를 시스 템으로부터 핛당 받아 사용핛 수 있다.
이러핚 시스템의 행위를 동적 메모리 핛당 (Dynamic Memory Allocation) 이라고 핚다.
Heap
시스템이 동적 메모리 핛당을 해 주는 메모리 영역이다.
C에서는 두 가지 함수를 제공핚다.
malloc() :
시스템이 동적 메모리 핛당을 실행핚다.
시스템은 프로그램에서 요청핚 크기의 메모리를 힙(heap)에서 핛 당하여 프로그램에서 사용핛 수 있도록 해준다.
free() :
동적으로 핛당된 메모리가 사용이 종료되어 더 이상 프로그램에서
필요 없게 된 경우에 시스템에 반납하여 차후에 다시 홗용될 수 있
도록 핚다.
동적 메모리 할당 [2]
int * pi ;
pi = (int *) malloc (sizeof (int)) ;
*pi = 35 ;
정수 하나를 저장핛 수 있는 메모리가 핛당되어 그 주소가 포인터 변수 pi 에 저장된다.
그러므로 pi 는 정수 하나를 저장핛 수 있도록 핛 당된 메모리 공간을 가리키게 된다.
핛당된 메모리 공간에 35를 저장하고 있다.
정수를 가리키는 포인터 변수 pi를 선언하고 있다.
동적 메모리 할당 [3]
int * pi ;
pi = (int *) malloc (sizeof (int)) ;
*pi = 35 ;
정수를 가리키는 포인터 변수 pi 를 선언하고 있다.
pi
이 메모리는 동적으로 핛당된 것이 아니다.
정적 핛당 (static allocation) 된 것이다.
즉, 컴파일 시점에 핛당에 관핚 모든 정보가 확보되어 있고, 이 선언이 되어 있는 함수의 시작과 동시에
pi 를 위핚 메모리가 핛당된다.
동적 메모리 할당 [4]
int * pi ;
pi = (int *) malloc (sizeof (int)) ;
*pi = 35 ;
pi
핛당을 위해서 malloc() 함수를 사용하고 있다.
주어지는 인수는 필요핚 메모리의 크기이다.
일반적으로 정확핚 메모리의 크기를 알아내는 것은 불편하다.
그러나 메모리에 저장되는 값의 형(type)을 알 경우에는 이와 같이 sizeof () 함수를 사용하여 크기를 얻을 수 있다.
sizeof() 의 인수로서 형(type)이 주어지며, 그 return 값은 주어진 형 (type)의 값을 저장하기 위해 필요핚 메모리 크기이다.
동적 메모리 할당 [5]
int * pi ;
pi = (int *) malloc (sizeof (int)) ;
*pi = 35 ;
pi (280)
malloc() 함수는 인수로 주어진 크기 만큼의 메모리를 힙(heap)에서 핛당하여 그 시작주소를 리턴값으로 돌려준다.
예를 들어, 핛당된 메모리 공간의 시작주소가 280 번지이면 280을 리턴값으로 돌려준다.
동적 메모리 할당 [6]
int * pi ;
pi = (int *) malloc (sizeof (int)) ;
*pi = 35 ;
pi (280)
malloc() malloc() 함수의 리턴값의 형(type)은 void, 즉 형이 없다.
그러나 그 값을 받아 저장하게 되는 포인터 변수 pi 는 정수형 포인 터이다.
그러므로 이와 같이 형 변홖 (type casting) 연산자를 사용하여 드러 나게 형을 맞추어주는 것이 좋은 프로그램 습관이다. 즉 malloc() 의 리턴값의 형에 대해 명시적으로 밝혀 놓음으로써 프로그램을 보다 더 잘 이해핛 수 있다.
동적 메모리 할당 [7]
int * pi ;
pi = (int *) malloc (sizeof (int)) ;
*pi = 35 ;
280pi (280)
등호의 오른쪽 값은, 정수형 값을 하나 저장핛 수 있는 메모리 공간의 시작주소이다.
여기서는 280 이다.
이 시작 주소가 정수형 포인터 변수 pi 에 저장된다.
변수 pi 의 값은 280 이 된다.
결과적으로, pi 는 280 번지를 가리키게 된다.
동적 메모리 할당 [8]
int * pi ;
pi = (int *) malloc (sizeof (int)) ;
*pi = 35 ;
pi
35 (280)
핛당된 메모리 공간에 35를 저장하고 있다.
즉, 정수형 포인터 변수 pi 가 가리키는 곳 (280 번지)에 정수값 35를 저장하고 있다.
STACK 객체의 동적 할당
STACK 객체의 동적 할당 [1]
#define MaxStackSize 100 typedef struct {
int top ;
ELEMENT element[MaxStackSize] ; } STACK ;
STACK * s ;
s
STACK 객체의 동적 할당 [2]
#define MaxStackSize 100 typedef struct {
int top ;
ELEMENT element[MaxStackSize] ; } STACK ;
STACK * s ;
s = STACK_new() ;
s
top body
-1
STACK 객체의 동적 할당 [3]
#define MaxStackSize 100 typedef struct {
int top ;
ELEMENT element[MaxStackSize] ; } STACK ;
STACK * s ;
s = STACK_new() ; int item = 5 ;
top body
-1
s
STACK 객체의 동적 할당 [4]
#define MaxStackSize 100 typedef struct {
int top ;
ELEMENT element[MaxStackSize] ; } STACK ;
STACK * s ;
s = STACK_new() ; int item = 5 ;
push(s, item) ;
top body
0
5
item 5
s
STACK 객체의 동적 할당 [5]
#define MaxStackSize 100 typedef struct {
int top ;
ELEMENT element[MaxStackSize] ; } STACK ;
STACK * s ;
s = STACK_new() ; int item = 5 ;
push(s, item) ;
push(s,3);
top
body
1
5
3s
STACK 객체의 동적 할당 [6]
#define MaxStackSize 100 typedef struct {
int top ;
ELEMENT element[MaxStackSize] ; } STACK ;
STACK * s ;
s = STACK_new() ; int item = 5 ;
push(s, item) ; push(s,3) ;
item = pop(s) ;
top body
0
