数据结构实现－堆栈－用链表来实现[anank].cpp

包含了数据结构实现堆栈的方法。 主要有链表实现和数组实现以及堆栈的应用。

/*****************************************************************************************
** Program Name : Implementation of stack with chain 
** Author       : Lu Jian Hua
** Time         : 2007-5-23
******************************************************************************************/

#include <iostream>
using namespace std ; 

class Node										// class of Node
{ 
public: 
	Node() : data(0), next(NULL) {} ; 
	int data ; 
	Node *next ; 
} ; 

class Stack										// class of Stack 
{ 
public: 
	Stack() ; 
	Node* Pop() ;								// pop 
	void Push() ;								// push 
	Node* GetTopValue() const ;					// get the top value 
	bool IsEmpty() const ;						// is empty ? 
	void Stack_Delete() ; 
private: 
	Node *top ;									// top element 
} ; 

void Stack::Stack_Delete() 
{ 
	int count = 0 ; 

	while (top) 
	{ 
		Node *record = top->next ;				 
		cout << "Deleting ... " << " Node " << ++count << endl ; 
		delete top ; 
		top = record ; 
	} 
} 

Stack::Stack()									// construct a stack, now top is NULL
{ 
	top = NULL ; 
} 

Node* Stack::Pop() 
{ 
	if (top == NULL) 
	{ 
		cout << "The stack is empty!" << endl << endl ; 
		return NULL ; 
	} 

	Node *temp = top ;							// get the value
	top = top->next ;							// move the top

	return temp ; 
} 

void Stack::Push() 
{ 
	Node *value = new Node() ; 
	
	if (value == NULL) 
		cout << "Have not enough memory to share!" << endl << endl ; 
	cout << "Enter the value : " ; 
	cin >> value->data ; 
	cout << endl ; 

	Node *temp = top ; 
	top = value ; 
	top->next = temp ; 
}

Node* Stack::GetTopValue() const 
{ 
	if (top == NULL) 
	{ 
		cout << "The stack is empty! " << endl << endl ; 
		return NULL ; 
	} 
	
	return top ; 
} 

bool Stack::IsEmpty() const 
{ 
	return (top == NULL) ; 
} 

Stack* CreateStack() 
{ 
	Stack *stk = new Stack() ; 
	return stk ; 
} 



int main() 
{ 
	Stack *stk = new Stack() ;					 
	
	Node *ptr ; 
	
	while (true) 
	{ 
		cout << "-------------------------------------" << endl
			 << "Please select : " << endl 
			 << "1> Push" << endl 
			 << "2> Pop" << endl 
			 << "3> Get the top value " << endl 
			 << "4> Is empty ?   " ;
		
		char c = 0 ; 
		cin >> c ; 
		cout << endl ; 
		
		if (c == 'q') 
			break ; 
		
		switch (c) 
		{ 
			case '1': 
				stk->Push() ; 
				break ; 
			case '2': 
				ptr = stk->Pop() ; 
				cout << "The value of the top element : " ; 
				if (ptr == NULL) 
					cout << "NULL" << endl << endl ; 
				else 
					cout << ptr->data << endl << endl ; 
				break ; 
			case '3' : 
				ptr = stk->GetTopValue() ; 
				cout << "The value of the top element : " ; 
				if (ptr == NULL) 
					cout << "NULL" << endl << endl ; 
				else 
					cout << ptr->data << endl << endl ; 
				break ; 
			case '4' : 
				cout << "Is empty ? " << (stk->IsEmpty() ? "Yes" : "No" ) << endl << endl ; 
				break ; 
			default: 
				break ; 
		}// switch 
	} 
	
	stk->Stack_Delete() ;
	
	return 0 ;
}

/********************************************************************************
*
* Notice : This Program Can Be Launched In VC6.0 Environment
*
********************************************************************************/