[스택과 큐] #1. 스택

스택

• 데이터를 일시적으로 저장하기 위해 사용하는 자료 구조.
• 데이터의 입쳑과 출력 순서는 후입선출이다.

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

푸시	스택에서 데이터를 넣는 작업
	푸시를 하는 위치	꼭대기
팝	스택에서 데이터를 꺼내는 작업
	스택의 가장 밑 바닥	바닥

스택

프로그램에서의 스택 사용

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

void x(){ }

void y(){ }

void z(){ 
    x();
    y();
}

int main() {
    z();
}

A. Main 함수가 실행되기 전의 상태
B. Main 함수를 실행
C. Z 함수를 호출
D. X함수를 호출
E. X함수가 종료되고 z함수로 돌아옴
F. Y함수를 호출
G. y함수가 종료되고 z함수로 돌아옴
H. Z함수를 종료하고 main함수로 돌아옴
I. Main함수가 종료됨

스택의 응용

간접응용	• 웹 브라우저에서 방문한 웹페이지들의 기록 • 재귀의 구현 • 되돌리기 구현
직접응용	• 알고리즘 수행을 위한 보조 데이터 구조 • 다른 데이터 구조를 구성하는 요소

스택의 구현

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

/*스택을 구현하는 구조체*/
typedef struct {
    int max; //스택용량
    int prt; //스택 포인터
    int *stk;//스택의 첫 요소에 대한 포인터
}IntStack;

/*스택 초기화*/
int Initialisze(IntStack *s,int max);

/*스택에 데이터를 푸시*/
int Push(IntStack *s,int x);

/*스택에 데이터를 팝*/
int Pop(IntStack *s,int *x);

/*스택에서 데이터를 피크*/
int Peek(IntStack *s,int *x);

/*스택 비우기*/
int Clear(IntStack *s);

/*스택의 최대 용량*/
int Capacity(IntStack *s);

/*스택의 데이터 개수*/
int Size(IntStack *s);

/*스택이 비어있는지의 유무*/
int isEmpty(IntStack *s);

/*스택이 가득 찼는지의 유무*/
int isFull(IntStack *s);

/*스택에서의 검색*/
int Search(IntStack *s,int max);

/*스택의 모든 데이터 출력*/
int Print(IntStack *s);

/*스택 종료*/
void Terminate(IntStack *s);

int main() {

}

스택 구조체: IntStack

• 스택을 관리하는 구조체. 3개의 멤버로 구성된다.

stk	스택으로 사용할 배열을 가리키는 포인터 stk
	> 스택으로 푸시된 데이터를 저장할 용도의 배열을 가리키는 포인터 > 배열의 메모리 공간 할당은 Initialisze함수를 통해 생성된다.
max	스택의 최대 용량을 나타내는 멤버. 배열 stk의 요소 개수와 같다.
prt	스택에 쌓여있는 데이터의 개수를 나타내는 멤버. 이 값을 스택 포인터라고 한다.
	> 가장 먼저 푸시된 바닥의 데이터는 stk[0], 가장 나중에 푸시된 꼭대기의 데이터는 stk[prt-1]