linkstack.cpp

数组堆栈与链表堆栈的实现代码

#include<cstddef>

typedef char Stack_entry;
typedef Stack_entry Node_entry;



enum error_code{
	success,overflow,underflow
};

struct Node{
		Node_entry entry;
		Node *next;
		Node();
		Node(Node_entry item,Node *add_on=NULL);
	};

Node::Node(){
	next=NULL;
}

Node::Node(Node_entry item,Node *add_on){
	entry=item;
	next=add_on;
}

class Stack{
public:
	Stack();
	~Stack();
	Stack(const Stack &original);
	void operator = (const Stack &origninal);

	bool empty() const;
	error_code push(const Stack_entry &item);
	error_code top(Stack_entry &item) const;
	error_code pop();
protected:
	Node *top_node;
};

Stack::Stack(){
	top_node=NULL;
	return;
}

Stack::~Stack(){
	while(!empty())
		pop();
}

Stack::Stack(const Stack &original){
      Node *copy_node,*original_node=original.top_node;
	if(original.top_node==NULL)
		top_node=NULL;
	else{
		top_node=copy_node=new Node(original_node->entry);
		while(original_node->next!=NULL){
			original_node=original_node->next;
			copy_node->next=new Node(original_node->entry);
			copy_node=copy_node->next;
		}
	}
}

void Stack::operator= (const Stack &original){
	Node *new_top,*new_copy,*original_node=original.top_node;
	if(original_node==NULL) new_top=NULL;
	else{
		new_copy=new_top=new Node(original_node->entry);
		while(original_node->next!=NULL){
			original_node=original_node->next;
			new_copy->next=new Node(original_node->entry);
			new_copy=new_copy->next;
		}
	}
	while(!empty())
		pop();
	top_node=new_top;

}

bool Stack::empty() const{
	bool outcome=false;
	if(top_node==NULL) outcome=true;
	return outcome;
}

error_code Stack::push(const Stack_entry &item){
	Node *new_node=new Node(item,top_node);
	if(new_node==NULL) return overflow;
	top_node=new_node;
	return success;
}

error_code Stack::top(Stack_entry &item) const{
	if(top_node==NULL) return underflow;
	else item=top_node->entry;
	return success;
}

error_code Stack::pop(){
	Node *old_top=top_node;
	if(top_node=NULL) return underflow;
	else{
		top_node=top_node->next;
		delete old_top;
	}
	return success;
}