기본 연산 Push와 Pop
1. Push와 Pop 연산
- 스택에서의 원소 삽입/삭제 과정
* 공백 스택에 원소 A, B, C를 순서대로 삽입하고 한번 삭제하는 연산과정 동안의 스택 변화
2. Push 알고리즘
- 스택의 Push 알고리즘
① top ← top+1;
▪ 스택 S에서 top이 마지막 자료를 가리키고 있으므로 그 위에 자료를 삽입하려면
> 먼저 top의 위치를 하나 증가(+1)
▪ 만약 이때 top의 위치가 스택의 크기(stack_SIZE)보다 크다면
> 오버플로우(Overflow) 상태가 되므로 삽입 연산을 수행하지 못하고 연산 종료
② S(top) ← x;
▪ 오버플로우 상태가 아니라면 스택의 top이 가리키는 위치에 x 삽입
push(S, x)
top ← top+1; // ①
if (top > stack_SIZE) then
overflow;
else
S(top) ← x; // ②
end push( )- 스택의 Pop 알고리즘
① return S(top);
▪ 스택이 공백 스택이 아니라면 top이 가리키는 원소를 먼저 반환
② top ← top-1;
▪ 스택의 top 원소를 반환하였으므로 top의 위치는 그 아래의 원소로 변경하기 위해 top의 위치를 하나 감소
pop(S)
if (top = 0) then underflow;
else
{
return S(top); // ①
top ← top-1; // ②
}
end pop( )
순차 자료구조를 이용한 스택의 구현
1. 구조
- 순차 자료구조인 1차원 배열을 이용하여 구현
▪ 스택의 크기: 배열의 크기
▪ 스택에 저장된 원소의 순서: 배열 원소의 인덱스
> 인덱스 0번 : 스택의 첫 번째 원소
> 인덱스 n-1번 : 스택의 n 번째 원소
▪ 변수 top: 스택에 저장된 마지막 원소에 대한 인덱스 저장
> 공백 상태 : top = -1(기본값)
> 포화 상태 : top = n-1
2. 수행 과정
- 순차 자료구조를 사용한 스택에서의 연산 과정
① 공백 스택 생성: createStack(S, 5);
② 원소 A 삽입: push(S, A);
③ 원소 B 삽입: push(S, B);
④ 원소 C 삽입: push(S, C);
⑤ 원소 삭제: pop(S);
3. 예제
#include <stdio.h>
#include <stdlib.h>
#define STACK_SIZE 100
typedef int element; // int를 스택 element의 자료형으로 정의
element stack[STACK_SIZE];
int top = -1; // 스택의 top의 초기값을 -1로 설정
void push(element item) // 스택의 삽입 연산
{
if (top >= STACK_SIZE - 1) // 스택이 이미 꽉 찬 경우
{
printf("\n\n Stack is FULL! \n");
return;
}
else stack[++top] = item;
}
element pop() // 스택의 삭제 후 반환 연산
{
if (top == -1) // 현재 스택이 공백인 경우
{
printf("\n\n Stack is empty!\n");
return 0;
}
else return stack[top--];
}
void del() // 스택의 삭제 연산
{
if (top == -1) // 현재 스택이 공백인 경우
{
printf("\n\n Stack is empty!\n");
exit(1);
}
else top--;
}
element peek()
{
if (top == -1) // 현재 스택이 공백인 경우
{
printf("\n\n Stack is empty!\n");
exit(1);
}
else return stack[top];
}
void printStack()
{
int i;
printf("\n STACK [ ");
for (i = 0; i <= top; i++)
printf("%d ", stack[i]);
printf("] ");
}
void main(void)
{
int item;
printStack();
push(1);
printStack();
push(2);
printStack();
push(3);
printStack();
item = peek();
printStack();
printf("peek top => %d", item);
del();
printStack();
item = pop();
printStack();
printf("peek top => %d", item);
item = pop();
printStack();
printf("peek top => %d", item);
pop();
getchar();
}4. 장, 단점
- 순차 자료구조로 구현한 스택의 장·단점
> 장점
▪ 순차 자료구조인 1차원 배열을 사용하여 쉽게 구현
> 단점
▪ 물리적으로 크기가 고정된 배열을 사용하므로 스택의 크기 변경 어려움
▪ 순차 자료구조의 단점을 그대로 가지고 있음
연결 자료구조를 이용한 스택의 구현
1. 구조
- 단순 연결 리스트를 이용하여 구현
▪ 스택의 원소: 단순 연결 리스트의 노드
- 스택 원소의 순서: 노드의 링크 포인터로 연결
> push : 리스트의 마지막에 노드 삽입
> pop : 리스트의 마지막 노드 삭제
▪ 변수 top: 단순 연결 리스트의 마지막 노드를 가리키는 포인터 변수
- 초기 상태: top = null
2. 수행 과정
① 공백 스택 생성: createStack(S);
② 원소 A 삽입: push(S, A);
③ 원소 B 삽입: push(S, B);
④ 원소 C 삽입: push(S, C);
⑤ 원소 삭제: pop(S);
3. 예제
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef int element; // int를 스택 element의 자료형으로 정의
typedef struct stackNode // 스택의 노드 구조 정의
{
element data;
struct stackNode* link;
}stackNode;
stackNode* top; // 스택의 top 노드를 지정하기 위한 포인터 top 선언
void push(element item) // 스택의 삽입 연산
{
stackNode* temp = (stackNode*)malloc(sizeof(stackNode));
temp->data = item;
temp->link = top;
top = temp;
}
element pop() // 스택의 삭제 후 반환 연산
{
element item;
stackNode* temp = top;
if (top == NULL) // 현재 스택이 공백 리스트인 경우
{
printf("\n\n Stack is empty !\n");
return 0;
}
else // 현재 스택이 공백 리스트가 아닌 경우
{
item = temp->data;
top = temp->link;
free(temp);
return item;
}
}
element peek() // 스택의 top 원소 검색 연산
{
element item;
if (top == NULL) // 현재 스택이 공백 리스트인 경우
{
printf("\n\n Stack is empty !\n");
return 0;
}
else // 현재 스택이 공백 리스트가 아닌 경우
{
item = top->data;
return item;
}
}
void del() // 스택의 삭제 연산
{
stackNode* temp;
if (top == NULL) // 현재 스택이 공백 리스트인 경우
{
printf("\n\n Stack is empty !\n");
}
else // 현재 스택이 공백 리스트가 아닌 경우
{
temp = top;
top = top->link;
free(temp);
}
}
void printStack() // 스택의 내용 출력 연산
{
stackNode* p = top;
printf("\n STACK [ ");
while (p)
{
printf("%d ", p->data);
p = p->link;
}
printf("] ");
}
void main(void)
{
element item;
top = NULL;
printStack();
push(1);
printStack();
push(2);
printStack();
push(3);
printStack();
item = peek();
printStack();
printf("peek top => %d\n", item);
del();
printStack();
item = pop();
printStack();
printf("peek top => %d\n", item);
item = pop();
printStack();
printf("peek top => %d\n", item);
pop();
getchar();
}