Last in First Out(LIFO) → 가장 최근에 들어온 데이터가 가장 먼저 나감
입력의 역순 출력이 필요한 이유
에디터에서 되돌리기 기능
함수호출에서 복귀주소 기능
ADT
객체 : 0개 이상의 원소를 가지는 유한 리스트
연산 :
create(size) ::= 최대 크기가 size인 빈 스택을 생성
is_empty(s) ::= 스택 s가 비어있는지를 검사
is_full(s) ::= 스택 s가 가득 찼는가를 검사
push(s, x) ::= 스택 s의 맨 위에 요소 x를 추가
pop(s) ::= 스택 s의 맨 위에 있는 요소를 삭제
peek(s) ::= 스택 s의 맨 위에 있는 요소를 삭제하지 않고 반환
구현
배열을 이용한 스택
1차원 배열 stack [MAX_STACK_SIZE] 사용
스택이 공백상태이면 top은 -1
가장 먼저 들어온 요소는 stack [0]에 저장
가장 최근에 들어온 요소는 stack [top]에 저장
top이 MAX_STACK_SIZE-1이면 스택은 포화상태
#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK 100
int stack[MAX_STACK];
int top = -1;
void error(const char* msg){
printf("%s\n",msg);
exit(1);
}
int isFull()
{
return (top == MAX_STACK-1);
}
int isEmpty(){
return (top == -1);
}
//삽입함수
void push(int item){
if(isFull()) error("큐가 다 찼습니다");
stack[++top] = item;
}
//삭제함수
int pop(){
if(isEmpty()) error("큐가 비었습니다");
return stack[top--];
}
//피크함수
int peek(){
if(isEmpty()) error("큐가 비었습니다");
return stack[top];
}
int main(){
push(3);
push(2);
push(1);
printf("%d\n",pop());
printf("%d\n",pop());
printf("%d\n",pop());
printf("%d\n",pop());
}
출력
스택 구조체 배열
복잡한 자료형이 섞여있을 경우 → 스택 구조체로 구현
// 구조체 element 정의
typedef struct{
int number;
char* name;
}element;
...
element stack[MAX_STACK]; // stack을 element 자료형을 선언
...
//스택에 넣을때 매개변수를 구조체 형식으로
void push(element item){
if(isFull()) error("큐가 다 찼습니다");
stack[++top] = item;
}
//반환을 구조체로 해야하기 때문에 element로 반환
element pop(){
if(isEmpty()) error("큐가 비었습니다");
return stack[top--];
}
//마찬가지
element peek(){
if(isEmpty()) error("큐가 비었습니다");
return stack[top];
}
int main(){
element in = {1,"hong"};
push(in);
element out = pop();
printf("%s\n",out.name);
printf("%d",out.number);
}
