스택
LIFO(Last In First Out) 즉 늦게 들어간 것부터 먼저 나오는 자료구조
입출력은 스택 맨 위(top)에서만 일어나므로 중간부터는 데이터를 삭제할 수 없다.
스택에 필요한 연산에는 full/empty 여부를 판단하는 is_full, is_empty
요소를 집어넣는 push, 요소를 삭제하는 pop이 있다
추가로 맨 위 요소를 제거하지 않고 반환만 하는 함수 peek가 있다
일차원 배열로 스택을 구현해보자.
#define MAX_STACK_SIZE 100
typedef int element;
element stack[MAX_STACK_SIZE];
int top = -1; //초기 상태에는 top = -1
int is_empty() {
return (top == -1);
}
int is_full() {
return (top == (MAX_STACK_SIZE - 1));
}
void push(element item) {
if (is_full()) {
fprintf(stderr, "스택 포화 에러\n");
exit(1);
}
else stack[++top] = item;
}
element pop() {
if (is_empty()) {
fprintf(stderr, "스택 공백 에러\n");
exit(1);
}
else return stack[top--];
}
element peek() {
if (is_empty()) {
fprintf(stderr, "스택 공백 에러\n");
exit(1);
}
else return stack[top];
}
int형의 데이터를 저장하는 스택을 위와 같이 만들었다
만약 스택에 저장하고 싶은 값이 더 복잡한 구조라면?
요소를 구조체로 하여 저장하면 된다
element의 자료형만 잘 선언해주면 어렵지 않다
이렇게 간단한 스택을 구현해봤는데, 이건 stack 배열과 top을 전역변수로 선언하는 방식이라서 한 프로그램 내에서 여러 스택을 관리하기가 어렵다. 이를 해결하기 위해 stack 배열과 top을 하나의 구조체로 묶어 선언하는 방식을 이용해서 보다 일반적인 배열 스택을 구현해보자...
typedef int element;
typedef struct {
element data[MAX_STACK_SIZE];
int top;
} StackType;
void init_stack(StackType* s) {
s->top = -1;
}
int is_empty(StackType* s) {
return (s->top == -1);
}
int is_full(StackType* s) {
return (s->top == (MAX_STACK_SIZE - 1));
}
void push(StackType* s, element item) {
if (is_full(s)) {
fprintf(stderr, "스택 포화 에러\n");
exit(1);
}
else s->data[++(s->top)] = item;
}
element pop(StackType* s) {
if (is_empty(s)) {
fprintf(stderr, "스택 공백 에러\n");
exit(1);
}
else return s->data[(s->top)--];
}
element peek(StackType *s) {
if (is_empty(s)) {
fprintf(stderr, "스택 공백 에러\n");
exit(1);
}
else return s->data[(s->top)];
}
스택 초기화 함수가 추가되었다
동적 배열 스택
data[MAX_STACK_SIZE] 처럼 정적 배열로 데이터를 입력받으면 스택 크기가 고정된다. 그치만 프로그램 내에서 스택이 얼마나 커질지 모르니까 동적할당을 이용할 수 있다.
typedef int element;
typedef struct {
element* data;
int capcity;
int top;
} StackType;capacity는 현재 크기를 의미한다.
void init_stack(StackType* s) {
s->top = -1;
s->capcity = 1;
s->data = (element*)malloc(s->capcity * sizeof(element));
}스택 초기화에서, 1개의 요소가 들어갈 공간을 동적으로 할당해준다.
void push(StackType* s, element item) {
if (is_full(s)) {
s->capacity *= 2;
s->data = (element*)malloc(s->capacity * sizeof(element));
}
s->data[++(s->top)] = item;
}full일 경우 크기를 2배로 만들어주고 그만큼의 메모리를 할당해주면 에러 없이 처리할 수 있다.
스택이 empty일 경우에는 어떻게 해줄 방법이 없으므로 pop은 변경점이 없다.
스택 응용 예제
1) 괄호 검사
괄호의 짝(모양, 방향)이 맞는지 확인하는 알고리즘으로, 문자열을 검사하면서 왼쪽 괄호를 만나면 스택에 넣고 오른쪽 괄호를 만나면 pop을 해서 나온 괄호와 짝이 맞는지 확인한다.
의사코드로 먼저 적어보자
check_basket(str):
while(str이 끝에 도달하지 않을 동안)
ch <- str의 다음 글자
switch(ch)
case '(', '[', '{' :
ch를 스택에 삽입
break
case ')', ']', '}':
if (스택이 empty) 오류
else
open_ch <- pop()
ch와 open_ch이 짝이 아니면 오류
break
if (다 끝났을 때 스택이 비어 있지 않음) 오류
구현하자
int check_basket(char* str) {
StackType s;
char ch, open_ch;
init_stack(&s);
int n = strlen(str);
for (int i = 0; i < n; i++) {
ch = str[i];
switch (ch) {
case '(': case '[': case '{':
push(&s, ch);
break;
case ')': case ']': case '}':
if (is_empty(&s)) return 0;
else {
open_ch = pop(&s);
if ((open_ch == '(' && ch != ')') ||
(open_ch == '{' && ch != '}') ||
(open_ch == '[' && ch != ']'))
return 0;
}
break;
}
}
if (!is_empty(&s)) return 0;
return 1;
}
2) 후위 표기 수식 계산
수식 표기법에는 전위, 중위, 후위 표기법이 있고 각 표기법은 연산자를 피연산자 앞/사이/뒤 중 어디에 위치시키느냐에 따라 구분된다.
예를 들어 2 + 3 * 4라는 수식이 있으면 이 자체로는 중위표기법이고
전위로는 +2*34, 후위로는 234*+ 가 된다
일반적으로 수식은 중위표기법으로 표현하지만 컴파일러는 주로 후위표기법을 사용한다. 프로그램을 작성할 때는 중위로 작성하지만 컴파일러가 읽을 때는 후위로 변환해서 계산하게 되고, 이 과정에서 스택을 사용한다.
후위 표기법은 괄호를 표기하지 않고도 연산자의 우선순위를 파악할 수 있다는 장점이 있다.
후위 표기법은 스택을 이용해 계산된다. 식을 앞에서부터 검사하면서 피연산자를 만나면 스택에 넣고, 연산자를 만나면 피연산자 두 개를 스택에서 꺼내 해당 연산자로 계산하고 그 결과값을 다시 스택에 넣는다.
예를 들어 82/3- 이라는 식이 있다고 치면,
1) 8은 피연산자이므로 스택에 넣는다.
2) 2도 피연산자이므로 스택에 넣는다.
3) /은 연산자이므로 스택에서 피연산자 두 개를 꺼내 계산한다. 8/2 = 4이므로 계산값인 4를 다시 스택에 넣는다. 이 과정 이후 스택에는 피연산자인 4 하나만 남아있게 된다.
4) 3은 피연산자이므로 스택에 넣는다. 이제 스택에는 3, 4가 들어가 있다.
5) -은 연산자이므로 스택에서 피연산자 두 개를 꺼내 계산한다. 4 - 3 = 1이므로 계산값인 1을 다시 스택에 넣는다. 이 과정 이후 스택에는 1 하나만 남아있게 된다.
6) 더 읽을 식이 없으므로 종료. 전체 연산결과는 1
의사코드로 정리해보자
calc_posfix(form):
for item in form :
if(item이 피연산자) push(s, item)
else if (item이 연산자)
second <- pop(s)
first <- pop(s)
result <- first item second
push(s, result)
final_result <- pop(s)
구현해보자
int calc_posfix(char exp[]) {
char ch;
int op1, op2, value;
int len = strlen(exp);
StackType s;
init_stack(&s);
for (int i = 0; i < len; i++) {
ch = exp[i];
if (ch != '+' && ch != '-' && ch != '/' && ch != '*') {
value = ch - '0';
push(&s, value);
}
else {
op2 = pop(&s);
op1 = pop(&s);
switch (ch) {
case '+':
push(&s, op1 + op2); break;
case '-':
push(&s, op1 - op2); break;
case '*':
push(&s, op1 * op2); break;
case '/':
push(&s, op1 / op2); break;
}
}
}
return pop(&s);
}연산자가 아닐 때는 push 연산자일 때는 pop해서 계산
3) 중위표기수식 -> 후위표기수식
연산자의 우선순위를 생각해서 넣고 빼줘야 한다. 스택에 존재하는 연산자가 현재 처리 중인 연산자보다 우선순위가 높으면 우선순위가 높은 것부터 출력해야 한다.
중위에는 괄호가 표기되지만 후위에는 그렇지 않으므로 괄호도 처리해줘야 한다.
왼쪽 괄호는 스택에 삽입한다. 우선순위는 가장 낮은 것으로 취급한다.
오른쪽 괄호를 만나면 왼쪽 괄호가 삭제될 때까지 왼쪽 괄호 위에 쌓여있는 모든 연산자를 출력한다.
아헷갈려
의사코드
infix_to_postfix(exp):
while(exp의 끝에 도달하지 않을 동안)
ch <- 다음에 처리할 문자
switch (ch)
case 연산자:
while(peek(s)의 우선순위 >= ch의 우선순위) do
e <- pop(s)
e를 출력
push(s, ch) break
case 왼쪽괄호:
push(s,ch) break
case 오른쪽괄호:
e <- pop(s)
while( e != 왼쪽괄호) do
e를 출력
e <- pop(s)
case 피연산자:
ch 출력; break
while( !is_empty(s) ) do
e<-pop(s), e를 출력
아헷갈려
int prec(char op) {
switch (op) {
case '(': case ')': return 0;
case '+': case '-': return 1;
case '*': case '/': return 2;
}
return -1;
}
void infix_to_postfix(char exp[]) {
char ch, top_op;
int len = strlen(exp);
StackType s;
init_stack(&s);
for (int i = 0; i < len; i++) {
ch = exp[i];
switch (ch) {
case '+': case '-': case '/': case '*':
while (!is_empty(&s) && (prec(peek(&s)) >= prec(ch)))
printf("%c", pop(&s));
push(&s, ch);
break;
case '(':
push(&s, ch);
break;
case ')':
top_op = pop(&s);
while (top_op != '(') {
printf("%c", top_op);
top_op = pop(&s);
}
break;
default:
printf("%c", ch);
break;
}
}
while (!is_empty(&s))
printf("%c", pop(&s));
}
4) 미로탐색
갈림길을 만나면 경로를 저장하면서 전진, 가다가 길이 막히면 다시 최근 갈림길로 돌아가 다른 갈림길을 시도하는 식으로 길을 찾을 수 있다.
루프에 빠지지 않기 위해 한번 간 길은 다시 가지 않는다.
미로는 2차원 배열로 표현하며 (행, 열) 로 위치를 표기한다. 갈 수 있는 길은 0, 갈 수 없는 길은 1로 한다.
maze_search():
스택 s, 출구 위치 x
while (현재 위치 != 출구 위치일 동안)
현재 위치를 방문했음으로 표기
if (현재 위치의 위, 아래, 왼쪽, 오른쪽 위치가 아직 방문되지 않았고 갈 수 있으면)
then 그 위치들을 push
if (is_empty(s))
then 실패
else 스택에서 위치 하나를 꺼내 현재 위치로 만듦
typedef struct {
short r;
short c;
} element;
element here = { 1,0 }, entry = { 1,0 };스택에 들어갈 데이터를 row, col을 가진 구조체 형태로 선언
현재 위치를 here, 시작점을 entry(e), 도착점을 x, 이미 지나간 곳은 .으로 표기한다고 하자
char maze[MAZE_SIZE][MAZE_SIZE] = {
{'1','1','1','1','1','1'},
{'e','0','1','0','0','1'},
{'1','0','0','0','1','1'},
{'1','0','1','0','1','1'},
{'1','0','1','0','0','x'},
{'1','1','1','1','1','1'}
};
void push_loc(StackType* s, int r, int c) {
if (r < 0 || c < 0) return;
if (maze[r][c] != '1' && maze[r][c] != '.') {
element tmp;
tmp.r = r;
tmp.c = c;
push(s, tmp);
}
}
void maze_print(char maze[MAZE_SIZE][MAZE_SIZE]) {
printf("\n");
for (int r = 0; r < MAZE_SIZE; r++) {
for (int c = 0; c < MAZE_SIZE; c++) {
printf("%c", maze[r][c]);
}
printf("\n");
}
}
int main() {
int r, c;
StackType s;
init_stack(&s);
here = entry;
while (maze[here.r][here.c] != 'x') {
r = here.r;
c = here.c;
maze[r][c] = '.';
maze_print(maze);
push_loc(&s, r - 1, c);
push_loc(&s, r + 1, c);
push_loc(&s, r, c - 1);
push_loc(&s, r, c + 1);
if (is_empty(&s)) {
printf("실패\n");
return;
}
else here = pop(&s);
}
printf("성공\n");
return 0;
}
연습문제
12. 문자열 압축 프로그램 (aaaabbb -> 4a3b)
void runlength(char exp[]) {
int len = strlen(exp);
char ch;
char a;
int count=0;
StackType s;
init_stack(&s);
for (int i = 0; i < len; i++) {
ch = exp[i];
if (is_empty(&s) || (ch == peek(&s))) {
push(&s, ch);
count++;
}
else {
while (!is_empty(&s))
a = pop(&s);
printf("%d%c", count, a);
push(&s, ch);
count = 1;
}
}
printf("%d%c", count, pop(&s));
}비어있거나 이전것과 같은 문자일 경우에는 스택에 넣고, 다른 문자일 경우에는 전부 빼서 출력해준 뒤 새 문자를 push해 다시 카운트를 센다
입력받은걸 전부 lowercase로 바꾸는 부분을 추가해서 실행해야 하겠지만 쨌든 대충 이런 식
16. 회문 검사
int palindrome(char exp[]) {
StackType s;
init_stack(&s);
int len = strlen(exp);
char ch;
for (int i = 0; i < len; i++) {
ch = exp[i];
push(&s, ch);
}
for (int i = 0; i < len; i++) {
if (pop(&s) != exp[i]) return 0;
}
return 1;
}마찬가지로 공백이나 특수기호삭제가 필요하겠다만
귀찮음.
'알고리즘' 카테고리의 다른 글
| BOJ: 행운의 바퀴(2840) [C++] (0) | 2024.02.27 |
|---|---|
| C언어로 복습하는 자료구조 (5) 큐 (0) | 2024.02.16 |
| C언어로 복습하는 자료구조 (3) 포인터 (0) | 2024.02.14 |
| C언어로 복습하는 자료구조 (2) 배열, 구조체 (0) | 2024.02.14 |
| C언어로 복습하는 자료구조 (1) 순환 (0) | 2024.02.12 |