C언어로 스택(Stack) 자료구조 만들기
스택(Stack)은 데이터 구조의 한 종류로 나중에 입력된 것이 먼저 출력된다(Last in First out => LIFO)는 특징을 가진 데이터 구조이다. 쉽게 생각하면 책을 위로 쌓다가 읽고 싶은 책이 아래에 있다면 위의 책들을 차례대로 치우고 원하는 책을 읽을 수 있는 것과 비슷하다. 책을 하나씩 쌓는(데이터를 입력하는) 행위를 push라고 하며 책을 하나씩 제거하는(데이터를 출력하는) 행위를 pop이라고 한다. 스택에 저장된 데이터를 읽을 때에는 맨 상단 스택의 데이터만 읽을 수 있기 때문에 상단의 스택이 중요하다.
이번에 만들어 볼 스택에서는 문자열을 입력받도록 하고 push, pop기능에 더해서 스택을 비우거나 완전히 삭제하는 기능을 만들어 보려고 한다. C언어에서 스택을 만드는 방법은 크게 2가지가 존재한다. 첫번째는 배열을 이용하는 방법이고 두 번째는 포인터를 이용하는 방법이다. 두 가지 방법은 각각 장단점을 가지고 있지만 이번에는 포인터를 사용하는 방법을 사용해 보려고 한다. 배열은 크기를 확장시키는 것이 불가능하기 때문에 데이터의 최대 저장개수가 존재하지만 포인터를 이용하면 동적할당을 통해 원하는 만큼 데이터를 저장할 수 있다. 그러면 배열을 처음에 크게 만들어놓으면 되지 않느냐?하는 의문을 가질 수도 있는데 그렇게 배열을 만들고 매우 작은 양의 데이터만 저장한다면 메모리의 낭비가 심해진다. 다만 배열을 이용하면 데이터를 검색하는 시간복잡도가 상수이기 때문에 데이터의 양을 예측 가능하다면 배열을 사용하는 것이 더 좋을 수도 있다.
이 코드는 학교 수업인 데이터구조 수업에서 배운 내용을 가지고 직접 스택을 구현해 보는 과제였다. 따라서 일부 기능이 불완전한 부분이 있을 수도 있다, 이 점에 유의하며 봐주시면 될 것 같다.
문자열을 입력받을 것이기 때문에 하나의 문자마다 하나의 스택을 할당하여 줄 것이다. 이것은 다음 스택의 주소를 저장해야 하기 때문에 char형 변수와 주소를 저장할 변수가 필요하다. 따라서 구조체를 선언하여 하나의 문자마다 문자의 데이터와 다음 스택의 주소를 저장해 줄 것이다.
struct stack {
char element; //정보
struct stack* pre; //이전 스택 주소
struct stack* next; //다음 스택 주소
};하지만 구조체를 보면 다음 스택 주소뿐만 아니라 이전 스택 주소도 선언해 주었다. 이러면 메모리는 더 소모하지만 무조건 상단부터 검색하는게 아니라 하단부터 검색할 수도 있어 편의성이 증가한다. 하지만 꼭 필요한 것은 아니다. 스택주소는 스택 자체를 가리켜 구조체 포인터 변수로 선언하였다.
다음은 사용할 변수들을 선언해 준다.
int select, ch, add, out, del, emp;
int i = 0;
struct stack firststack = { '\0','\0','\0' };
struct stack* p1 = &firststack; //p1은 항상 마지막에 만든 스택을 가르키는 포인터 변수
struct stack* p2, * p3, * p4, * p5, * p6, * p7, * p8, * p9, * p10, * p11;조건문과 반복문에 사용할 변수들과 최초의 스택구조를 선언해주고 Null(\0)로 초기화해 준다. 그리고 대입과정에 사용될 포인터변수들을 선언해 주는데 이때 p1은 항상 최상단, 즉 마지막에 생성한 스택을 가리키게 해 줄 것이다.
여기부터는 while(1) 무한 반복문을 이용하여 한가지 동작을 하고 다음 동작을 계속할 수 있게 해 줄 것이다.
printf("실행할 작업의 번호를 입력해주세요\n1.문자열 입력\n2.문자열 전체 출력\n3.문자열 선택출력\n4.stack 1개생성\n5.stack 1개삭제\
\n6.stack empty\n7.stack empty 확인\n8.top element 확인\n9.메인메뉴로 돌아가기\n번호 입력:");
scanf_s("%d", &select);
switch (select)원하는 동작의 번호를 입력받아 실행되게 하였고 무한반복문으로 동작이 끝나면 항상 실행할 작업의 번호를 다시 입력받도록 한다. 입력을 받아 switch-case구문을 이용해 특정 동작이 실행되게 한다.
먼저 문자열 입력에 관한 case이다.
case 1: //문자열 입력 p1, p2
while (getchar() != '\n') {} //버퍼 초기화
printf("문자열(영어)을 입력하세요:");
while (1) {
ch = getchar();
if (ch == '\n') break;
p2 = (struct stack*)malloc(sizeof(firststack));
p1->next = p2; //전스택next에 새로만든 스택 주소대입
p2->pre = p1; //새로만든 스택pre에 전 스택 주소대입
p1 = p1->next; //p1에 새로만든 스택 주소 대입
p1->next = '\0'; //새로만든 스택next초기화
p1->element = ch; //새로만든 스택에 문자 대입
}
printf("\n");
break;문자열은 getchar를 이용해 입력받고 동적할당도 사용할 것이라서 #include <stdlib.h>를 추가해 주어야 한다. getchar는 버퍼에 저장된 문자열에서 문자를 한 개씩 읽어 들여 저장하므로 문자가 하나 입력되면 그것이 \n 즉 구분문자가 아닌지 확인하고 새로운 스택을 동적할당받아 최상단 스택 위에 쌓으면서 포인터를 서로 연결해 준다. 이때 새로 만든 스택의 next를 초기화하지 않으면 쓰레기값이 들어가 이상한 결과가 나올 수 있으니 주의하자. getchar는 엔터(\n)가 나올 때까지 문자열의 한 글자씩 리턴해주고 반복문이 종료된다. 이때 주의사항이 있는데 getchar는 버퍼를 이용하므로 기존에 버퍼에 뭔가가 존재한다면 내가 입력한 값이 나오지 않거나 입력조차 안되고 바로 종료될 수도 있다. 따라서 입력 전에 버퍼를 초기화시켜 주는 작업이 필요하다. 여기서는 구분문자(\n)이 나올 때까지 버퍼를 출력하는 방법을 사용했다.
이제 문자열 출력에 관한 case이다.
case 2: //문자열 전체 출력 p3
p3 = p1;
printf("출력할 문자열은 ");
while (1) {
printf("%c", p3->element);
if (p3->pre == '\0') break;
p3 = p3->pre;
}
printf("입니다.\n\n");
break;스택에 입력된 문자열을 전부 출력해주는 기능이다. 다만 출력만 해줄 뿐 문자를 제거(pop) 하지는 않는다. 이것은 단순히 최상단 스택부터 아래로 내려가면서 내용을 출력해 주면 된다. 맨 아래의 스택은 pre 즉 자신의 아래 스택이 존재하지 않으므로 pre==Null이다. pre가 \0일 때까지 반복문을 통해 출력을 하고 종료한다. 출력을 해보면 입력한 문자열이 뒤집힌 형태로 출력되는 것을 볼 수 있는데 이것은 스택이 후입선출 구조이기 때문이다. apple을 입력하면 a가 첫 번째로 저장되고 그 위에 p, p, l, e 순서로 저장되기 때문에 상단의 스택부터 출력하면 elppa가 출력되는 것이다.
다음은 전체 문자열이 아닌 일부의 문자열만 출력하는 기능이다.
case 3: //문자열 선택 출력 p3
printf("출력할 문자의 개수를 입력하세요:");
scanf_s("%d", &out);
p3 = p1;
printf("출력할 문자열은 ");
for (i = 0; i < out; i++) {
printf("%c", p3->element);
if (p3->pre == '\0') break;
p3 = p3->pre;
}
printf("입니다.\n\n");
break;최상단의 스택부터 몇개의 문자를 출력할지 입력받고 반복문을 통해 해당 횟수만큼만 출력을 해 주는 간단한 기능이다. 이때는 숫자를 입력받기도 하고 한 글자이기 때문에 scanf_s를 사용했다. 이 코드에서는 범위를 넘어서는 입력에 관한 예외처리는 고민하지 않았다. 사용자가 잘 써야지 5개 입력하고 10개 출력하는건 무슨 생각이야! 사실 이런 예외처리를 해야지 완벽한 스택이지만 기능구현에 집중하였다.
다음 기능은 중간에 스택 하나 새로 생성하기이다.
case 4: //스택 추가 p4, p5, p6
printf("top에서 몇개 아래에 stack을 새로 만들 것인지 입력하세요:");
scanf_s("%d", &add);
p5 = p1;
for (i = 1; i < add; i++) {
p5 = p5->pre;
}
if (p5->pre == '\0') {
p6 = (struct stack*)malloc(sizeof(firststack));
p6->pre = '\0';
p6->next = p5;
p5->pre = p6;
}
else {
p4 = p5->pre; //p4아래스택 p5위스택 p6새스택
p6 = (struct stack*)malloc(sizeof(firststack));
p4->next = p6; //아래 스택next를 새 스택 주소로 대입
p6->pre = p4; //새 스택pre를 아래 스택으로 대입
p6->next = p5; //새 스택next에 위 스택 대입
p5->pre = p6; //위 스택pre에 새 스택 대입
}
printf("새로운 stack에 입력할 문자 1개를 입력하세요:");
while (getchar() != '\n') {}
ch = getchar();
p6->element = ch;
printf("\n");
break;만약 스택 자료구조를 이용해 코딩을 할 때는 중간에 데이터를 넣으려면 그 위의 스택을 전부 제거하면서 저장해 놨다가 새로운 스택을 만들고 다시 전부 넣어줘야 한다. 배열로 스택을 구현해도 이 과정은 같다. 배열은 중간에 데이터를 끼워 넣는 게 불가능하니 말이다. 하지만 포인터는 이게 가능하다! 중간에 스택을 끼워 넣고 그 위, 아래 스택의 포인터를 적절히 수정만 해주면 아무 문제가 없다. 만약 스택 중간에 데이터를 삽입할 일이 많다면 이런 포인터 구조가 월등히 우수한 성능을 낸다. 먼저 어디에 스택을 새로 만들지 입력을 받고 그 위치까지 반복문을 통해 이동한다. 그리고 새로 만들 위치가 최하단인 경우와 아닌 경우로 나누었는데 최하단이면 이전 스택이 없기 때문에 이전 스택을 호출하면 에러가 나기 때문이다. 새 스택 공간을 동적할당받은 뒤 위, 아래 포인터를 적절히 연결해 주고 만약 최하단이면 Null도 넣어주었다.
다음은 스택을 삭제하는 기능이다. pop의 확장버전(?) 같은 기능이다. pop은 최상단의 스택만 제거할 수 있지만 여기서는 중간의 스택도 삭제할 수 있게 구현하였다,.
case 5: //스택 삭제 p7 p8 p9
printf("top에서 몇 번째의 stack을 삭제할것인지 입력하세요:");
scanf_s("%d", &del);
p7 = p1;
for (i = 1; i < del; i++) {
p7 = p7->pre;
}
if (del == 1) {
if (p7->pre == '\0') {
printf("모든 stack삭제되어 프로그램 종료");
exit(0);
}
p8 = p7->pre;
p8->next = '\0';
p1 = p8;
free(p7);
}
else if (p7->pre == '\0') {
p9 = p7->next;
p9->pre = '\0';
free(p7);
}
else {
p8 = p7->pre;
p9 = p7->next; //p7 지울 스택 p8 아래 스택 p9 위 스택
p8->next = p9;
p9->pre = p8;
free(p7); //p7 메모리 반환
}
printf("\n");
break;pop을 하려면 1번째 스택을 지운다고 입력을 하면 된다. 만약 1번째를 삭제했는데 더이상 남은 스택이 없으면 프로그램이 종료되게 하였다. 새로운 스택을 만드는 기능이 기존 스택의 존재를 가정하고 만들어 모든 스택이 지워지면 추가를 할 수 없기 때문이다. 이 부분을 조금 수정해서 더 자세한 기능을 구현해 보면 좋을 것 같다. 여기서도 최하단인 경우와 중간인 경우 삭제를 구분하였다. 삭제는 해당 스택의 위, 아래 스택을 포인터로 바로 이어주고 동적할당받은 메모리를 free 해주면 된다.
다음 기능은 스택을 삭제하는게 아니라 비워주는 기능이다.
case 6: //스택 비우기 p10
printf("top에서 몇 번째의 stack을 비울것인지 입력하세요:");
scanf_s("%d", &emp);
p10 = p1;
for (i = 1; i < emp; i++) {
p10 = p10->pre;
}
p10->element = 32; //비울 스택에 스페이스(32)대입
printf("\n");
break;스택 비우기는 아주 간단한데 어디 스택을 비울지 입력을 받고 찾아가서 값만 바꿔주면 된다. 여기서는 공란 스페이스를 대입하여 출력 시 app e 이렇게 빈 부분이 나와 비었다는 것을 인식할 수 있게 하였다. 32는 화이트 스페이스의 아스키코드값이다. 32를 숫자로 출력하면 그대로 32가 나오지만 문자로 출력하면 공란이 나오게 된다.
다음기능은 스택이 비었는지 확인하는 기능과 스택의 최상단을 확인하는(peek) 기능이다.
case 7: //스택 비우기 확인 p11 띄어쓰기,NULL 빈 걸로 인식
printf("top에서 몇 번째의 stack을 확인할지 입력하세요:");
scanf_s("%d", &emp);
p11 = p1;
for (i = 1; i < emp; i++) {
p11 = p11->pre;
}
if (p11->element == 32) printf("스택이 비었습니다.");
else if (p11->element == '\0')printf("스택이 비었습니다.");
else printf("스택이 비어있지 않습니다.");
printf("\n\n");
break;
case 8: //맨위 확인
printf("top element는 %c입니다.\n\n", p1->element);
break;
case 9:
printf("\n");
return;
}스택이 비었는지 확인은 해당 스택으로 가서 데이터가 32인지 검사하면 된다. 32이면 비었다고 판단하고 아니면 비어있지 않다고 판단한다. 최상단 스택 확인은 p1으로 바로 확인이 가능하다. 케이스9번은 초기 메뉴로 돌아가는 기능이다. 사실 이 코드는 스택과 큐를 한 번에 구현한 코드의 일부분이라 최초화면에 스택, 큐를 선택하는 기능이 있는데 그곳으로 돌아가는 기능이다. 큐는 다음 글에서 다룰 예정이다.
여기까지가 직접 구현한 스택 자료구조이다. 교수님이 이 과제를 내주시면서 copy 하지 말라고 다 안다고 하셔서 참고한 것 없이 직접 구현하였는데 덕분에 스택에 대한 이해를 더 확실히 하는 기회가 되었던 것 같다. C에서는 이렇게 직접 구현을 해야 하는데 JAVA는 자료구조가 제공되어서 너무 편하다.