3-1データ構造-スタック

stack

コンセプト

データ構造は先入先出(LIFO)形式を採用し、一端でしかデータを挿入・削除できない.
データ構造は線形構造と非線形構造に分けられ、スタックは線形構造の一部であり、データを構成するデータが順番にリストされるためである.

アレイスタック

スタック

を実装するためにアレイを作成する.
上部変数を作成して、

の上部にある要素

を格納します.

スタックの状態を示す関数

を実装する.

スタックに要素を入れる関数

を実装する.

スタック内の要素除去関数

を実現する.

スタックの上部要素を決定するための関数

を実装する.

スタック内の要素

を出力するために関数を実装する.

課題-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バイトの空間を割り当てる必要がある.(コンパイル32 bitで4バイト/64 bitで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;
}