スタックのリニアストレージとチェーンストレージ


1.スタックのリニアストレージ
//main.cpp
#include 
#include 

using namespace std;

struct stack
{
	int len;
	int top;
	char *_space;
};

void initStack(stack *s,int size)
{
	s->top = 0;
	s->len = size;
	s->_space = new char[size];
}

bool isStackFull(stack *s)
{
	return s->top >= s->len;
}

bool isStackEmpty(stack *s)
{
	return s->top == 0;
}

void push(stack *s,char ch)
{
	s->_space[s->top++] = ch;
}

char pop(stack *s)
{
	return s->_space[--s->top];
}

void reset(stack *s)
{
	s->top = 0;
}

void clear(stack *s)
{
	delete s->_space;
}

int main()
{
	stack s;
	initStack(&s,10);

	for(char ch = 'A';ch <= 'Z';ch++)
	{
		if(!isStackFull(&s))
			push(&s,ch);
	}

	//reset(&s);
	while(!isStackEmpty(&s))
		printf("%c  ",pop(&s));
	return 0;
}

2.スタックのチェーンストレージ
//main.cpp
#include 
#include 

using namespace std;

struct Node
{
	char data;
	Node *next;
};

struct stack
{
	Node *top;
};

void initStack(stack *s)
{
	s->top = new Node;
	s->top->next = NULL;
}

int isStackEmpty(stack *s)
{
	return s->top->next == NULL;
}

void push(stack *s,char ch)
{
	Node *cur = new Node;
	cur->data = ch;

	cur->next = s->top->next;
	s->top->next = cur;
}

char pop(stack *s)
{
	Node *t = s->top->next;
	char ch = t->data;
	s->top->next = t->next;
	delete t;
	return ch;
}

void reset(stack *s)
{
	while(!isStackEmpty(s))
		pop(s);
}

void clear(stack *s)
{
	reset(s);
	delete s->top;
	s->top = NULL;
}


int main()
{
	stack s;
	initStack(&s);

	for(char ch = 'A';ch <= 'M';ch++)
	{
		push(&s,ch);
	}

	while(!isStackEmpty(&s))
		printf("%c  ",pop(&s));
	clear(&s);

	return 0;
}