stack
개념
한쪽 끝에서만 자료를 넣고 뺄 수 있는 후입선출(LIFO) 형식의 자료구조
자료구조는 선형구조와 비선형구조로 구분되는데, 스택은 자료를 구성하는 데이터를 순차적으로 나열시키기 때문에 선형구조에 속합니다.
배열을 이용한 스택
- 스택을 구현할 배열 생성
- 맨 위에 있는 원소를 저장할 top 변수 생성
- 스택의 상태를 나타낼 함수 구현
- 스택에 원소를 넣는 함수 구현
- 스택에 원소를 제거하는 함수 구현
- 스택 맨 위의 원소를 확인하는 함수 구현
- 스택의 원소를 출력할 함수 구현
과제 - 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바이트)
- 즉, 노드 하나하나의 메모리 사용량이 증가합니다. 그러므로 상황에 따라 사용해야 합니다.
- 메모리를 동적으로 할당하므로 할당과 해제에 따른 시간이 소모된다는 단점이 있습니다.
- 스택을 구현할 연결리스트 생성
- 맨 위에 있는 원소를 저장할 top 포인터 변수 생성
- 스택의 상태를 나타낼 함수 구현
- 스택에 노드를 넣는 함수 구현
- 스택에 노드를 제거하는 함수 구현
- 스택 맨 위의 노드를 확인하는 함수 구현
- 스택의 노드에 있는 데이터를 출력할 함수 구현
과제 - 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;
} 