03 数据结构之栈

阅读引言： 只是分享我在复习过程中写的关于栈的代码

顺序栈

/* squence_stack.h */
#ifndef _SQUENCE_STACK
#define _SQUENCE_STACK

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define DEBUG(msg) printf("---%s---%d, ---%s---", __func__,__LINE__, msg)

typedef int data_t;
typedef struct {
	data_t *p_data;
	int top;
	int maxlen;
}SqStack_t;

SqStack_t *sqstack_create(int len);
int sqstack_free(SqStack_t *s);
int sqstack_clear(SqStack_t *s);
int sqstack_push(SqStack_t *s, data_t data);
data_t sqstack_pop(SqStack_t *s);
int sqstack_isempty(SqStack_t *s);
int sqstack_isfull(SqStack_t *s);
data_t sqstack_top_value(SqStack_t *s);

#endif

/* squence_stack.c */
#include "squence_stack.h"

SqStack_t *sqstack_create(int len)
{
	SqStack_t *p = (SqStack_t *)malloc(sizeof(SqStack_t));
	if(p == NULL) {
		DEBUG("malloc failed!\n");
		return NULL;
	}

	p->p_data = (data_t *)malloc(sizeof(data_t) * len);
	if(p->p_data == NULL) {
		free(p);
		DEBUG("malloc failed!\n");
		return NULL;
	}
	
	memset(p->p_data, 0, sizeof(data_t) * len);
	p->top = -1;
	p->maxlen = len;

	return p;
}

int sqstack_free(SqStack_t *s)
{
	if(s == NULL) {
		DEBUG("param is invalid\n");
		return -1;
	}

	s->maxlen = 0;
	s->top = -1;
	if(s->p_data != NULL)
		free(s->p_data);
	free(s);

	return 0;
}

int sqstack_clear(SqStack_t *s)
{
	if(s == NULL) {
		DEBUG("param is invalid\n");
		return -1;
	}

	memset(s->p_data, 0, sizeof(data_t) * s->maxlen);
	s->top = -1;
	
	return 0;
}


int sqstack_push(SqStack_t *s, data_t data)
{
	if(s == NULL) {
		DEBUG("param is invalid\n");
		return -1;
	}

	if(s->top < s->maxlen) {
		s->top++;
		s->p_data[s->top] = data;
	} else {
		DEBUG("top beyond maxlen\n");
		return -1;
	}

	return 0;
}




data_t sqstack_pop(SqStack_t *s)
{
	if(s == NULL) {
		DEBUG("param is invalid\n");
		return -1;
	}

	return s->p_data[s->top--];
}

int sqstack_isempty(SqStack_t *s)
{
	if(s == NULL) {
		DEBUG("param is invalid\n");
		return -1;
	}

	return (s->top == -1? 1 : 0);
}


int sqstack_isfull(SqStack_t *s)
{
	if(s == NULL) {
		DEBUG("param is invalid\n");
		return -1;
	}

	return (s->top == s->maxlen - 1 ? 1:0);
	
}


data_t sqstack_top_value(SqStack_t *s)
{
	if(s == NULL) {
		DEBUG("param is invalid\n");
		return -1;
	}

	return (s->p_data[s->top]);
}

链式栈

/* link_stack.h */

#ifndef _LINK_STACK_H
#define _LINK_STACK_H

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define DEBUG(msg) \
	printf("%s, %s", __func__, msg)

typedef int data_t;
typedef struct node {
	data_t data;
	struct node *next;
}node_stack, *link_stack;

link_stack link_stack_create();
int link_stack_free(link_stack H);
int link_stack_push(link_stack H, data_t value);
data_t link_stack_pop(link_stack H);
void link_stack_show(link_stack H);
data_t get_top_value(link_stack H);
int link_stack_isempty(link_stack H);

#endif

/* link_stack.c */
#include "link_stack.h"

/*brife: create a link stack, return heap address of link stack 
 *
 * */
link_stack link_stack_create()
{
	link_stack H = NULL;

	H = (link_stack)malloc(sizeof(node_stack));
	if(H == NULL) {
		DEBUG("malloc failed\n");
		return NULL;
	}

	H->data = 0;
	H->next = NULL;

	return H;
}


/*brife: release a link stack 
 *
 * */	
int link_stack_free(link_stack H)
{
	if(H == NULL) {
		DEBUG("param is NULL\n");
		return -1;
	}

	link_stack p = NULL;

	while(H != NULL) {
		p = H;
		H = H->next;
		free(p);
	}

	return -1;
}


/*brife: entry stack
 *
 * */
int link_stack_push(link_stack H, data_t value)
{
	if(H == NULL) {
		DEBUG("param is NULL\n");
		return -1;
	}

	link_stack p = (link_stack)malloc(sizeof(node_stack));
	if(p == NULL) {
		DEBUG("malloc failed\n");
		return -1;
	}

	p->next = NULL;
	p->data = value;

	p->next = H->next;
	H->next = p;
	
	return 0;
}

/*brife: out stack
 *
 * */
data_t link_stack_pop(link_stack H)
{
	if(H == NULL) {
		DEBUG("param is NULL\n");
		return -1;
	}

	data_t ret = H->next->data;
	link_stack p = H->next;
	H->next = p->next;
	free(p);

	return ret;
}


/*brife: foreach the link stack
 *
 * */
void link_stack_show(link_stack H)
{
	if(H == NULL) {
		DEBUG("param is NULL\n");
		return ;
	}
		
	link_stack p = H->next;

	while(p != NULL) {
		printf("%d ", p->data);
		p = p->next;
	}
	puts("");

	return ;
}


/*brife: get value of link stack top 
 *
 * */
data_t get_top_value(link_stack H)
{
	if(H == NULL) {
		DEBUG("param is NULL\n");
		return -1;
	}

	if(H->next == NULL) {
		return -1;
	}

	return H->next->data;
}


/*brife: judge link stack is empty?
 *
 * */
int link_stack_isempty(link_stack H)
{
	if(H == NULL) {
		DEBUG("param is NULL\n");
		return -1;
	}

	return (H->next == NULL?1:0);
}