3-1 자료구조 - stack

stack

개념

한쪽 끝에서만 자료를 넣고 뺄 수 있는 후입선출(LIFO) 형식의 자료구조
자료구조는 선형구조와 비선형구조로 구분되는데, 스택은 자료를 구성하는 데이터를 순차적으로 나열시키기 때문에 선형구조에 속합니다.

배열을 이용한 스택

1. 스택을 구현할 배열 생성
2. 맨 위에 있는 원소를 저장할 top 변수 생성
3. 스택의 상태를 나타낼 함수 구현
4. 스택에 원소를 넣는 함수 구현
5. 스택에 원소를 제거하는 함수 구현
6. 스택 맨 위의 원소를 확인하는 함수 구현
7. 스택의 원소를 출력할 함수 구현

과제 - 1 (배열 이용)

#include <stdio.h>
#include <string.h>						//strlen, strcmp

enum { MAX = 32, TRUE = 1, FALSE = 0,
	PALINDROME = 11, NOT_PALINDROME = 12,
	SIZE_ERROR = -32 };

char stack[MAX];						//스택
int top = -1;							//스택 제일 위에 있는 원소 번호
int Push(char c);						//문자 하나씩 push
char Pop();								//pop과 동시에 top에 있던 문자 리턴
int Check(char a[], char b[], int n);	//단어를 앞과 뒤로 읽어도 같은지 판단

int Push(char c)
{
	if (top < MAX / 2 - 1) {			//MAX/2의 값보다 1이 작아야 공간추가 가능
		top++;
		stack[top] = c;
		return TRUE;
	}
	else
		return FALSE;
}

char Pop()
{
	if (top > -1)
		return stack[top--];
	else
		return FALSE;
}

int Check(char a[], char b[], int n)
{
#ifdef DEBUG
	printf("strcmp value: %d\n", strncmp(a, b, n));
#endif
	if (strncmp(a, b, n) == 0) {
		printf("palindrome\n");
		return PALINDROME;
	}
	else {
		printf("not palindrome\n");
		return NOT_PALINDROME;
	}
}

int main()
{
	char input[MAX];
	char temp[MAX / 2 + 1];				//널문자 공간 추가를 위해 +1
    int i;
	scanf("%s", input);

	int size = (int)strlen(input);
	if (size > MAX) {
		puts("단어가 32자를 초과하였습니다.\n");
		return SIZE_ERROR;
	}

	for (int i = size / 2; i < size; i++) {
		Push(input[i]);
#ifdef DEBUG
		printf("%c ", input[i]);
#endif
	}
#ifdef DEBUG
	puts("");
#endif
	for (i = 0; i < size / 2; i++) {	//임시공간에 그대로 팝해서 a b c d 입력
		temp[i] = Pop();
#ifdef DEBUG
		printf("%c ", temp[i]);
#endif
	}
#ifdef DEBUG
	puts("");
#endif

	temp[i+1] = '\0';					//문자열 끝에 널문자 대입
	Check(input, temp, strlen(temp));	//strncmp을 이용해서, temp의 길이만큼
										//처음 입력받은 input 문자열과 temp 문자열을 비교
										//strlen은 널문자 제외한 문자열 길이
	return 0;
}              

연결리스트를 이용한 스택

• 크기의 제약이 있는 배열과 달리, 연결리스트를 이용한 스택은 크기의 제약이 없습니다.
• 하지만 연결리스트를 이루는 각각의 노드들은 데이터를 저장할 변수와 다음 노드의 주소값을 저장할 포인터 변수로 이루어져 있기 때문에 포인터를 추가로 저장해야합니다.
• 따라서 기존의 배열 스택과 달리 기존 데이터 크기에 8바이트의 공간을 더 할당받아야 합니다. (32bit로 컴파일시 4바이트/64bit로 컴파일시 8바이트)
• 즉, 노드 하나하나의 메모리 사용량이 증가합니다. 그러므로 상황에 따라 사용해야 합니다.
• 메모리를 동적으로 할당하므로 할당과 해제에 따른 시간이 소모된다는 단점이 있습니다.

1. 스택을 구현할 연결리스트 생성
2. 맨 위에 있는 원소를 저장할 top 포인터 변수 생성
3. 스택의 상태를 나타낼 함수 구현
4. 스택에 노드를 넣는 함수 구현
5. 스택에 노드를 제거하는 함수 구현
6. 스택 맨 위의 노드를 확인하는 함수 구현
7. 스택의 노드에 있는 데이터를 출력할 함수 구현

과제 - 1 (연결리스트 이용)

#include <stdio.h>
#include <string.h>				//strlen, strcmp
#include <stdlib.h>				//malloc, free

enum { MAX = 32, TRUE = 1, FALSE = 0, EMPTY_ERROR = -99,
	PALINDROME = 11, NOT_PALINDROME = 12,
	SIZE_ERROR = -32 };

typedef struct stack {			//연결리스트 노드 구조체
	char data;					//문자
	struct stack* link;			//다음 노드의 주소값을 저장할 포인터 변수
} stack;

stack* top;						//스택의 맨 위의 노드 주소를 저장할 포인터 변수 (기본값 NULL)
int isEmpty();					//스택이 공백 상태인지 검사
void Push(char data);
char Pop();

int isEmpty()
{
	if (top == NULL) {			//top이 아무것도 가르키지 않는 경우
		puts("스택이 비어있습니다.");
		return EMPTY_ERROR;
	}
    return 0;
}

void Push(char data)
{
	//새로운 노드 s 동적 할당
	stack* s = (stack *)malloc(sizeof(stack));
	s->data = data;				//s의 data에 값(단어의 알파벳 한 문자) 저장
	s->link = top;				//s의 link에 맨 위의 노드 주소 저장
								//(top이 맨 위의 노드 주소를 가지고 있음)
	top = s;					//이제 s가 맨위노드가 되었으므로 top에 s 주소 저장
}

char Pop()
{
	if (!isEmpty()) {			//배열이 비어있지 않은 경우
		stack* temp = top;		//temp 포인터를 선언해 맨 위 노드의 주소값을 저장
		char ch = temp->data;	//ch 변수를 새로 선언하여 맨 위 노드의 데이터 저장
		top = temp->link;		//top 포인터에 2번째 노드(맨 위 다음 노드)의 주소값 저장
		free(temp);				//맨 위 노드 제거
		return ch;				//문자 리턴
	}
	else
		return 0;
}

/////////////////////////////////아래부터는 배열을 이용한 스택 풀이와 같음
int Check(char a[], char b[], int n)
{
#ifdef DEBUG
	printf("strcmp value: %d\n", strncmp(a, b, n));
#endif
	if (strncmp(a, b, n) == 0) {
		printf("palindrome\n");
		return PALINDROME;
	}
	else {
		printf("not palindrome\n");
		return NOT_PALINDROME;
	}
}

int main()
{
	char input[MAX];
	char temp[MAX / 2 + 1];			//널문자 공간 추가를 위해 +1
    int i;
	scanf("%s", input);

	int size = (int)strlen(input);
	if (size > MAX) {
		puts("단어가 32자를 초과하였습니다.\n");
		return SIZE_ERROR;
	}

	for (int i = size / 2; i < size; i++) {
		Push(input[i]);
#ifdef DEBUG
		printf("%c ", input[i]);
#endif
	}
#ifdef DEBUG
	puts("");
#endif
	for (i = 0; i < size / 2; i++) {	//임시공간에 그대로 팝해서 a b c d 입력
		temp[i] = Pop();
#ifdef DEBUG
		printf("%c ", temp[i]);
#endif
	}
#ifdef DEBUG
	puts("");
#endif

	temp[i+1] = '\0';					//문자열 끝에 널문자 대입
	Check(input, temp, strlen(temp));	//strncmp을 이용해서, temp의 길이만큼
										//처음 입력받은 input 문자열과 temp 문자열을 비교
										//strlen은 널문자 제외한 문자열 길이
	return 0;
}