[Data Structure] 스택 (Stack)
2021. 11. 30. 21:15ㆍMajor`/자료구조
스택이란?
"LIFO 구조" : Last-In First-Out
- 프링글스 과자라고 생각하면 된다
- 프링글스는 제조 과정에서 과자들을 차례대로 통에 넣어준다
- 당연히 프링글스를 사먹는 사람들은 일반적으로 제조과정에서 마지막에 넣은 과자를 먼저 먹게된다
이처럼 스택은 몇몇 요소들을 넣으면 가장 나중에 넣은 요소들부터 차레대로 pop이 되는 구조이다
스택 ADT (추상 자료형)
- n개의 element형의 요소들의 선형 리스트
boolean is_full(stack *s)
- 스택 포화 상태 검출 함수
boolean is_empty(stack *s)
- 스택 공백 상태 검출 함수
void push(stack *s, element item)
- 스택 s에 item을 삽입
element pop(stack *s)
- 스택 s의 가장 상단에 있는 element return 후 스택에서 삭제
element peek(stack *s)
- 스택 s의 가장 상단에 있는 element return
- pop과는 달리 스택에서 삭제하지 않는다
배열로 구현한 스택
스택 구조체 정의 (Array)
#define MAX_STACK_SIZE 100
typedef int element;
typedef struct {
element stack[MAX_STACK_SIZE];
int top;
} Stack;
void init_stack(Stack* s) {
// 스택 초기화 함수 (공백상태이면 top = -1)
s->top = -1;
}- 스택에는 항상 마지막으로 들어온 element를 가리키는 SP(Stack Pointer)가 존재한다
- SP를 int top으로 조절하면서 top 변수는 항상 스택의 마지막 element의 index를 가리키게 해준다
1. is_full / is_empty
int is_full(Stack* s) {
// 스택이 가득 차있으면 가장 상단의 인덱스 = MAX_STACK_SIZE -1
return s->top == (MAX_STACK_SIZE)-1;
}
int is_empty(Stack* s) {
// 공백상태이면 top = -1, 그러므로 return top == -1
return s->top == -1;
}- is_full
- 스택이 가득 차있으면 더이상 push(삽입) 불가
- 가득 차있으면 스택의 최상단 인덱스 = 스택의 최대크기 - 1
- is_empty
- 스택이 비어있으면 pop(삭제), peek(선택) 불가
- 비어있으면 스택의 top = -1 (공백상태)
2. push
void push(Stack* s, element item) { // 스택의 top에 새로운 item을 삽입하는 함수
// 스택이 꽉 찼으면 push 불가, 스택 top을 1 증가시키고 1 증가시킨 인덱스에 item push
if (is_full(s)) {
fprintf(stderr, "스택이 꽉 찼습니다!!\n");
return;
}
else s->stack[++(s->top)] = item;
}- 스택이 가득 차있으면 error발생
- push를 하려면 top을 1 증가시켜야하고 이 증가시킨 배열에 item을 추가해야 한다
- 그러므로 ++(s->top)을 통해서 top을 1증가시키고
- 증가시킨 배열 s-stack[++(s->top)]에 item을 추가
3. pop
element pop(Stack* s) { // 스택의 top에 있는 item을 꺼내고 스택에서 삭제시키는 함수
// 스택이 비어있으면 pop불가, 스택에서 top에 있는 배열item을 꺼내고 top을 1 감소
if (is_empty(s)) {
fprintf(stderr, "스택이 공백입니다!!\n");
return;
}
else return s->stack[(s->top)--]; // 스택을 꺼내고 top을 1 감소
}- 스택의 top에 존재하는 item을 꺼냄으로써, top은 1 감소된다
- s->stack[(s->top)--]에서
- 먼저 s->top에 해당하는 item을 return시키고
- 이다음에 (s->top)--를 통해 top을 1 감소시킨다
4. peek
element peek(Stack* s) { // top에 있는 item 보여주는 함수
// 스택이 비어있으면 peek 불가, 스택에서 top에 있는 item을 return
if (is_empty(s)) {
fprintf(stderr, "스택이 공백입니다!!\n");
return;
}
else return s->stack[s->top];
}- 그냥 스택의 top에 있는 item을 보여주기만 하기 때문에 item이 삭제되거나 top이 바뀌지 않는다
5. Full Code (Stack : Array)
#include <stdio.h>
#include <stdlib.h>
// 배열로 구현한 스택
#define MAX_STACK_SIZE 100
typedef int element; // 스택 각각의 item
typedef struct {
element stack[MAX_STACK_SIZE];
int top; // 스택의 top, 공백상태면 -1
} Stack;
void init_stack(Stack* s) {
// 스택 초기화 함수 (공백상태이면 top = -1)
s->top = -1;
}
int is_full(Stack* s) {
// 스택이 가득 차있으면 가장 상단의 인덱스 = MAX_STACK_SIZE -1
return s->top == (MAX_STACK_SIZE)-1;
}
int is_empty(Stack* s) {
// 공백상태이면 top = -1, 그러므로 return top == -1
return s->top == -1;
}
void push(Stack* s, element item) { // 스택의 top에 새로운 item을 삽입하는 함수
// 스택이 꽉 찼으면 push 불가, 스택 top을 1 증가시키고 1 증가시킨 인덱스에 item push
if (is_full(s)) {
fprintf(stderr, "스택이 꽉 찼습니다!!\n");
return;
}
else s->stack[++(s->top)] = item;
}
element pop(Stack* s) { // 스택의 top에 있는 item을 꺼내고 스택에서 삭제시키는 함수
// 스택이 비어있으면 pop불가, 스택에서 top에 있는 배열item을 꺼내고 top을 1 감소
if (is_empty(s)) {
fprintf(stderr, "스택이 공백입니다!!\n");
return;
}
else return s->stack[(s->top)--]; // 스택을 꺼내고 top을 1 감소
}
element peek(Stack* s) { // top에 있는 item 보여주는 함수
// 스택이 비어있으면 peek 불가, 스택에서 top에 있는 item을 return
if (is_empty(s)) {
fprintf(stderr, "스택이 공백입니다!!\n");
return;
}
else return s->stack[s->top];
}
int main(void) {
Stack s;
init_stack(&s);
push(&s, 1);
push(&s, 3);
push(&s, 5);
push(&s, 7);
for (int i = 0; i < 4; i++) {
printf("%d ", peek(&s));
}
printf("\n");
for (int i = 0; i < 4; i++) {
printf("%d ", pop(&s));
}
return 0;
}
- peek함수는 스택의 top을 보여주기만 하는거이기 때문에 스택 top의 item만 return된다
- pop함수는 스택 top의 item을 가져오면서 스택에서 삭제
연결리스트로 구현한 스택
- 장점 : 크기 제한 X
- 단점 : 구현이 복잡, 삽입/삭제 시간이 오래 걸린다
- 크기에 제한이 없기 때문에 스택이 포화인지 확인할 필요가 없다
스택 구조체 정의 (LinkedList)
typedef int element; // 스택 item의 타입
typedef struct stacknode {
element item; // 스택의 item
struct stacknode* link; // 스택의 item들을 연결해주는 link
} stacknode;
typedef struct { stacknode의 top을 가리키는 linkedstack
stacknode* top;
}linkedstack;
1. is_empty
int is_empty(linkedstack* s) {
if ((s->top) == NULL)
return 1;
return 0;
}
2. push
- push할 새로운 노드(newnode) 동적 할당
- newnode의 item칸에 push할 item 저장
- newnode의 link칸에 top 주소 저장
- top을 newnode로 변경
void push(linkedstack* s, element item) {
/*
(1) push할 새로운 노드(newnode) 동적 할당
(2) newnode의 item칸에 push할 item 저장
(3) newnode의 link칸에 top 주소 저장
(4) top을 newnode로 변경
*/
stacknode* newnode = (stacknode*)malloc(sizeof(stacknode)); // (1)
if (newnode == NULL) {
fprintf(stderr, "메모리 할당 에러");
return;
}
else {
newnode->item = item; // (2)
newnode->link = s->top; // (3)
s->top = newnode; // (4)
}
}
3. pop
- 삭제할 노드(맨 위 노드) 임의 설정 후, top(맨 위 노드) 주소값 저장
- return할 item에 top(맨 위 노드)의 item 저장
- top 포인터에 2번째 노드(맨 위 다음 노드)의 주소값 저장
- 맨 위 노드 제거 (free)
- item return
element pop(linkedstack* s) {
/*
(1) 삭제할 노드(맨 위 노드) 임의 설정 후, top(맨 위 노드) 주소값 저장
(2) return할 item에 top(맨 위 노드)의 item 저장
(3) top 포인터에 2번째 노드(맨 위 다음 노드)의 주소값 저장
(4) 맨 위 노드 제거 (free)
(5) item return
*/
if (is_empty(s)) {
fprintf(stderr, "Error : Stack is empty!!");
return;
}
else {
stacknode* d_node = s->top; // (1)
element item = d_node->item; // (2)
s->top = d_node->link; // (3)
free(d_node); // (4)
return item; // (5)
}
}- (1)을 통해서 d_node를 top이라고 임의설정
- (3)을 통해서 top포인터에 삭제할 노드(맨 위 노드)의 link를 저장
- -> top포인터가 맨 위에서 2번째 노드를 가리키게 된다
- -> 이를 통해서 top 포인터와 맨 위에서 2번째 노드가 새롭게 서로 연결
4. peek
element peek(linkedstack* s) {
if (is_empty(s)) {
fprintf(stderr, "Error : Stack is empty!!");
exit(1);
}
else
return s->top->item;
}
5. Full Code (Stack : LinkedList)
#include <stdio.h>
#include <stdlib.h>
typedef int element; // 스택 item의 타입
typedef struct stacknode {
element item; // 스택의 item
struct stacknode* link; // 스택의 item들을 연결해주는 link
} stacknode;
typedef struct { // 연결된 스택의 타입
stacknode* top;
}linkedstack;
int is_empty(linkedstack* s) {
if ((s->top) == NULL)
return 1;
return 0;
}
void push(linkedstack* s, element item) {
/*
(1) push할 새로운 노드(newnode) 동적 할당
(2) newnode의 item칸에 push할 item 저장
(3) newnode의 link칸에 top 주소 저장
(4) top을 newnode로 변경
*/
stacknode* newnode = (stacknode*)malloc(sizeof(stacknode)); // (1)
if (newnode == NULL) {
fprintf(stderr, "메모리 할당 에러");
return;
}
else {
newnode->item = item; // (2)
newnode->link = s->top; // (3)
s->top = newnode; // (4)
}
}
element pop(linkedstack* s) {
/*
(1) 삭제할 노드(맨 위 노드) 임의 설정 후, top(맨 위 노드) 주소값 저장
(2) return할 item에 top(맨 위 노드)의 item 저장
(3) top 포인터에 2번째 노드(맨 위 다음 노드)의 주소값 저장
(4) 맨 위 노드 제거 (free)
(5) item return
*/
if (is_empty(s)) {
fprintf(stderr, "Error : Stack is empty!!");
exit(1);
}
else {
stacknode* d_node = s->top; // (1)을 통해서 d_node를 top이라고 임의설정
element item = d_node->item; // (2)
s->top = d_node->link; // (3), top포인터에 삭제할 노드(맨 위 노드)의 link를 저장
free(d_node); // (4)
return item; // (5)
}
}
element peek(linkedstack* s) {
if (is_empty(s)) {
fprintf(stderr, "Error : Stack is empty!!");
exit(1);
}
else
return s->top->item;
}
void printStack(linkedstack* s) {
if (is_empty(s)) {
fprintf(stderr, "Error : Stack is empty!!");
return;
}
else {
stacknode* p_node = s->top;
while (p_node) {
printf("%d ", p_node->item);
p_node = p_node->link;
}
printf("\n");
}
}
int main(void) {
stacknode* s = (stacknode*)malloc(sizeof(stacknode));
linkedstack* ls = NULL;
push(&ls, 10);
push(&ls, 20);
push(&ls, 30);
push(&ls, 40);
push(&ls, 50);
printf("#####peek 실행#####\n");
for (int i = 0; i < 5; i++) {
printf("%d ", peek(&ls));
}
printf("\n\n");
printf("#####printStack 실행#####\n");
printStack(&ls);
printf("\n");
printf("#####pop 실행#####\n");
for (int i = 0; i < 5; i++) {
printf("%d ", pop(&ls));
}
printf("\n\n");
printf("#####printStack 실행#####\n");
printStack(&ls);
printf("\n");
return 0;
}
