C 语言堆栈的实现,数组版本,链表版本

2014-07-19 18:22:12   3752
#include "stdafx.h"
#include "stdio.h"
#include <string.h>
#if 0
//数组实现堆栈
#define MAX_LEN  1000
#define EMPTY  -1
#define FULL  (MAX_LEN - 1)

typedef enum boole {fal, tru}  boolean;
 //enum boolean boolean;

typedef struct stack
{
	char s[MAX_LEN];
	int top;
}stack;

void reset(stack *stk)
{
	stk -> top = EMPTY;
}
void push(char c,stack *stk)
{
	stk->top++;                //等价于 (strk -> top) ++
	stk->s[stk->top] = c;
}
char pop(stack *stk)
{
	return (stk->s[stk ->top -- ]);
}
char top(const stack *stk)
{
	return (stk ->s[stk ->top ]);
}
boolean empty(const stack *stk)
{
	return ((boolean)(stk ->top == EMPTY));
}
boolean full(const stack *stk)
{
	return ((boolean)(stk ->top == FULL));
}

int main(int argc, char* argv[])
{
	char str[] = "My name is Laura Pohl!";
	int i;
	stack s;
	reset(&s);
	printf("In the string : %s \n",str);
	for(i = 0; str[i] != '\0'; ++i)
	if(!full(&s))
		push(str[i],&s);
	printf("From the stack: ");
	while(!empty(&s))
		putchar(pop(&s));
	putchar('\n');
	return 0;
}
#endif
//链表实现堆栈
#include <stdio.h>
#include <stdlib.h>
#define EMPTY 0
#define FULL 10000
typedef char data;
typedef enum {fal,tru} boolean;
struct elem{
	data d;
	struct elem *next;
};
typedef struct elem elem;
struct stack{
	int cnt;
	elem *top;
};
typedef struct stack stack;
void initialize(stack *stk);
void push(data d, stack *stk);
data pop(stack *stk);
data top(stack *stk);
boolean empty(const stack *stk);
boolean full(const stack *stk);
void initialize(stack *stk)
{
	stk -> cnt = 0;
	stk -> top = NULL;
}
void push(data d, stack *stk)
{
	elem *p;
	p = (elem*)malloc(sizeof(elem));
	p -> d = d;
	p -> next = stk -> top;
	stk -> top = p;
	stk -> cnt ++;
}
data pop(stack *stk)
{
	data d;
	elem *p;
	d = stk ->top ->d;
	p = stk ->top;
	stk ->top = stk->top->next;
	stk ->cnt--;
	free(p);
	return d;
}
data top(stack *stk)
{
	return (stk ->top ->d); 
}
boolean empty(const stack* stk)
{
	return ((boolean) (stk->cnt == EMPTY));
}
boolean full(const stack *stk)
{
	return ((boolean) (stk ->cnt == FULL));
}
int main()
{
	//printf("链表实现堆栈\n");
	char str[] = "My name is Joanna Kelley!";
	int i;
	stack s;
	initialize(&s);
	printf("In the string : %s\n",str);
	for(i = 0; str[i] != '\0'; ++i)
		if(!full(&s))
			push(str[i],&s);
		printf("From the stack :");
		while(!empty(&s))
			putchar(pop(&s));
		putchar('\n');
	return 0;
}