堆疊-順序存盤

#ifndef STACK_ARRAY_H_
#define STACK_ARRAY_H_

#ifndef PTOI
#define PTOI( p ) ((int32_t)(int64_t)(p))
#endif
#ifndef ITOP
#define ITOP( i ) ((void *)(int64_t)(i))
#endif

#define ADT StackArray

// 功能: a與b的比較程序.
// 引數: a, b.
// 回傳: a>b回傳正數, a<b回傳負數, 否則回傳0.
// 注意: a不為NULL且b為NULL,回傳正數, a為NULL且b不為NULL,回傳負數, a與b都為NULL,回傳0.
typedef int ( CompareFunc )( const void *a, const void *b );

typedef struct StackArray ADT;

// 功能: 創建一個新的堆疊.
// 引數: capacity(堆疊的最大容量).
// 回傳: 一個新的堆疊.
// 注意: 當 capacity 小于0時,默認為512; 當記憶體分配失敗時,將錯誤退出程式.
extern ADT *newStackArray( int32_t capacity );

// 功能: 將用戶資料壓入堆疊頂.
// 引數: stack(堆疊物件指標), data(用戶資料).
// 回傳: 被壓入堆疊頂的用戶資料.
// 注意: 當 stack 為NULL 或 滿堆疊狀態 時, 將錯誤退出程式.
extern void *pushStackArray( ADT *stack, void *data );

// 功能: 將堆疊頂用戶資料彈出堆疊.
// 引數: stack(堆疊物件指標).
// 回傳: 被彈出的堆疊頂用戶資料.
// 注意: 當 stack 為NULL 或 空堆疊狀態 時, 將錯誤退出程式.
extern void *popStackArray( ADT *stack );

// 功能: 偷看堆疊頂用戶資料.
// 引數: stack(堆疊物件指標).
// 回傳: 堆疊頂用戶資料.
// 注意: 當 stack 為NULL 或 空堆疊狀態 時, 將錯誤退出程式.
extern void *peekStackArray( ADT *stack );

// 功能: 偷看堆疊呼叫戶資料.
// 引數: stack(堆疊物件指標).
// 回傳: 堆疊頂用戶資料.
// 注意: 當 stack 為NULL 或 空堆疊狀態 時, 將錯誤退出程式.
extern void *peekBottomStackArray( ADT *stack );


// 功能: 堆疊中所有用戶資料中是否包含了data.
// 引數: stack(堆疊物件指標), data(需查找的用戶資料), cmp(用戶自定義比較函式).
// 回傳: 包含了data回傳1, 否則回傳0.
// 注意: 當 stack 為NULL 或 cmp 為NULL 時, 將錯誤退出程式.
extern int existStackArray( ADT *stack, void *data, CompareFunc *cmp );

// 功能: 從堆疊頂到堆疊底方向開始查找data.
// 引數: stack(堆疊物件指標), data(需查找的用戶資料), cmp(用戶自定義比較函式).
// 回傳: 堆疊中包含了data, 回傳data所在位置, 否則回傳-1.
// 注意: 當 stack 為NULL 或 cmp 為NULL 時, 將錯誤退出程式.
extern int32_t findStackArray( ADT *stack, void *data, CompareFunc *cmp );

// 功能: 從堆疊底到堆疊頂方向開始查找data.
// 引數: stack(堆疊物件指標), data(需查找的用戶資料), cmp(用戶自定義比較函式).
// 回傳: 堆疊中包含了data, 回傳data所在位置, 否則回傳-1.
// 注意: 當 stack 為NULL 或 cmp 為NULL 時, 將錯誤退出程式.
extern int32_t findTailStackArray( ADT *stack, void *data, CompareFunc *cmp );

// 功能: 堆疊實際已使用大小.
// 引數: stack(堆疊物件指標).
// 回傳: 堆疊實際已使用大小.
// 注意: 當 stack 為NULL 時, 將錯誤退出程式.
extern int32_t sizeStackArray( ADT *stack );

// 功能: 空堆疊狀態.
// 引數: stack(堆疊物件指標).
// 回傳: 是空堆疊回傳1, 否則回傳0.
// 注意: 當 stack 為NULL 時, 將錯誤退出程式.
extern int emptyStackArray( ADT *stsack );

// 功能: 滿堆疊狀態.
// 引數: stack(堆疊物件指標).
// 回傳: 是滿堆疊回傳1, 否則回傳0.
// 注意: 當 stack 為NULL 時, 將錯誤退出程式.
extern int fullStackArray( ADT *stack );

// 功能: 堆疊最大容量.
// 引數: stack(堆疊物件指標).
// 回傳: 堆疊最大容量.
// 注意: 當 stack 為NULL 時, 將錯誤退出程式.
extern int32_t capacityStackArray( ADT *stack );

// 功能: 清空堆疊.
// 引數: stack(堆疊物件指標).
// 回傳: 無.
// 注意: 當 stack 為NULL 時, 將錯誤退出程式.
extern void clearStackArray( ADT *stack );

// 功能: 銷毀堆疊.
// 引數: stack(存放堆疊物件指標的指標).
// 回傳: 無.
// 注意: 當 stack 為NULL 時, 將錯誤退出程式.
extern void delStackArray( ADT **stack );

#undef ADT

#endif

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include "stackArray.h"


// 功能: 列印錯誤資訊后就錯誤退出程式.
// 引數: expression(錯誤判斷運算式), message(需列印的錯誤資訊).
// 回傳: 無.
// 注意: 當運算式 expression 為真時, 才觸發.
#define ERROR_EXIT( expression, message )                                    \
if( (expression) ) {                                                         \
	fprintf( stderr, "\nerror location: file = %s, func = %s, line = %d.\n", \
	                       __FILE__, __func__, __LINE__ );                   \
	fprintf( stderr, "error  message: %s%s.\n\a",                            \
	                       (message) != NULL ? (message) : __func__,         \
		                   (message) != NULL ? "" : " function error" );     \
	exit( EXIT_FAILURE );                                                    \
}

#define ADT StackArray


struct StackArray {
	int32_t capacity;
	int32_t top;
	void *array[0];
};


ADT *newStackArray( int32_t capacity ) {
	ADT *stack = NULL;

	capacity = capacity < 0 ? 512 : capacity;
	stack = malloc( sizeof(*stack) + sizeof(stack->array[0]) * capacity );
	ERROR_EXIT( !stack, NULL );
	stack->capacity = capacity;
	stack->top = 0;

	return stack;
}

void *pushStackArray( ADT *stack, void *data ) {
	ERROR_EXIT( !stack || stack->top >= stack->capacity, NULL );

	return (stack->array[stack->top++] = data);
}

void *popStackArray( ADT *stack ) {
	ERROR_EXIT( !stack || stack->top < 1, NULL );

	return stack->array[--stack->top];
}

void *peekStackArray( ADT *stack ) {
	ERROR_EXIT( !stack || stack->top < 1, NULL );

	return stack->array[stack->top - 1];
}

void *peekBottomStackArray( ADT *stack ) {
	ERROR_EXIT( !stack || stack->top < 1, NULL );

	return stack->array[0];
}

int existStackArray( ADT *stack, void *data, CompareFunc *cmp ) {
	ERROR_EXIT( !stack || !cmp, NULL );

	for( int32_t i = 0; i < stack->top; ++i ) {
		if( !cmp( stack->array[i], data ) ) {
			return 1;
		}
	}

	return 0;
}

int32_t findStackArray( ADT *stack, void *data, CompareFunc *cmp ) {
	ERROR_EXIT( !stack || !cmp, NULL );

	for( int32_t i = 0; i < stack->top; ++i ) {
		if( !cmp( stack->array[i], data ) ) {
			return i;
		}
	}

	return -1;
}

int32_t findTailStackArray( ADT *stack, void *data, CompareFunc *cmp ) {
	ERROR_EXIT( !stack || !cmp, NULL );

	for( int32_t i = stack->top - 1; i >= 0; --i ) {
		if( !cmp( stack->array[i], data ) ) {
			return i - 0; // 0為堆疊底位置.
		}
	}

	return -1;
}

int32_t sizeStackArray( ADT *stack ) {
	ERROR_EXIT( !stack, NULL );

	return stack->top;
}


int emptyStackArray( ADT *stack ) {
	ERROR_EXIT( !stack, NULL );

	return stack->top < 1;
}

int fullStackArray( ADT *stack ) {
	ERROR_EXIT( !stack, NULL );

	return stack->top >= stack->capacity;
}

int32_t capacityStackArray( ADT *stack ) {
	ERROR_EXIT( !stack, NULL );

	return stack->capacity;
}

void clearStackArray( ADT *stack ) {
	ERROR_EXIT( !stack, NULL );

	stack->top = 0;
}

void delStackArray( ADT **stack ) {
	ERROR_EXIT( !stack, NULL );
	free( *stack );
	*stack = NULL;
}

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <time.h>
#include "stackArray.h"

// a>b回傳正數, a<b回傳負數, 否則回傳0.
static int cmp( const void *a, const void *b ) {
	return *(int32_t *) a - *(int32_t *) b;
}

int main( int argc, char *argv[] ) {
	char *tf[] = {"false", "true"};
	int32_t *a = NULL, n = 0;
	int32_t i = 0, k = 0;
	StackArray *s = NULL;

	srand( time( NULL ) );
	printf( "please input array length: n = " );
	scanf( "%d%*c", &n );
	printf( "\n" );

	a = malloc( sizeof(*a) * n );
	for( i = 0; i < n; ++i ) {
		a[i] = rand() % 322;
		//a[i] = 1;
	}

	printf( "&s = %p, s = %p\n", &s, s );
	s = newStackArray( n );
	printf( "new: &s = %p, s = %p\n", &s, s );

	printf( "peek       = %d\n", emptyStackArray( s ) ? INT32_MIN : *(int32_t *) peekStackArray( s ) );
	printf( "peekBottom = %d\n", emptyStackArray( s ) ? INT32_MIN : *(int32_t *) peekBottomStackArray( s ) );
	printf( "size     = %d\n", sizeStackArray( s ) );
	printf( "empty = %s\n", tf[emptyStackArray( s )]);
	printf( "full  = %s\n", tf[fullStackArray( s )] );
	printf( "capacity = %d\n", capacityStackArray( s ) );
	printf( "\n" );

	printf( "push all: [" );
	for( i = 0; i < n; ++i ) {
		printf( ", %5d", *(int32_t *) pushStackArray( s, &a[i] ) );
	}
	printf( "]\n" );

	printf( "peek       = %d\n", emptyStackArray( s ) ? INT32_MIN : *(int32_t *) peekStackArray( s ) );
	printf( "peekBottom = %d\n", emptyStackArray( s ) ? INT32_MIN : *(int32_t *) peekBottomStackArray( s ) );
	printf( "size     = %d\n", sizeStackArray( s ) );
	printf( "empty = %s\n", tf[emptyStackArray( s )] );
	printf( "full  = %s\n", tf[fullStackArray( s )] );
	printf( "capacity = %d\n", capacityStackArray( s ) );
	printf( "\n" );

	//k = a[0];
	k = rand();
	printf( "exist &k(%d) = %s\n", k, tf[existStackArray( s, &k, cmp )] );
	printf( "\n" );

	k = a[0];
	//k = rand();
	printf( "find &k(%d) = %d\n", k, findStackArray( s, &k, cmp ) );
	printf( "\n" );

	//k = a[0];
	k = rand();
	printf( "findTile &k(%d) = %d\n", k, findTailStackArray( s, &k, cmp ) );
	printf( "\n" );

	printf( "pop all:  [" );
	while( !emptyStackArray( s ) ) {
		printf( ", %5d", *(int32_t *) popStackArray( s ) );
	}
	printf( "]\n" );

	printf( "peek       = %d\n", emptyStackArray( s ) ? INT32_MIN : *(int32_t *) peekStackArray( s ) );
	printf( "peekBottom = %d\n", emptyStackArray( s ) ? INT32_MIN : *(int32_t *) peekBottomStackArray( s ) );
	printf( "size     = %d\n", sizeStackArray( s ) );
	printf( "empty = %s\n", tf[emptyStackArray( s )] );
	printf( "full  = %s\n", tf[fullStackArray( s )] );
	printf( "capacity = %d\n", capacityStackArray( s ) );
	printf( "\n" );

	delStackArray( &s );
	printf( "del: &s = %p, s = %p\n", &s, s );

	return EXIT_SUCCESS;
}