링크 스 택 (Link Stack) - 스 택 의 링크 구현

스 택 의 실현 에 있어 서 연속 적 으로 분 배 된 배열 을 사용 합 니 다.이러한 스 택 구 조 는 큰 연속 적 인 저장 공간 이 필요 하 다 는 결함 이 있다.스 택 (Stack) - 후진 선 출 (LIFO) 의 데이터 구조 (Data Structures)
비 연속 공간 을 이용 하 는 방식 은 링크 입 니 다.
링크 방식 으로 이 루어 진 스 택 을 링크 스 택 이나 스 택 의 링크 실현 이 라 고 합 니 다.링크 스 택 의 구조 에서 기록 간 에 반드시 물리 적 저장 공간 에서 연결 되 어야 하 는 것 은 아니다.모든 기록 은 데이터 항목 을 저장 하 는 것 외 에 링크 스 택 의 다음 기록 을 가리 키 는 지침 도 저장 합 니 다.그 가 지적 한 조작 유형 과 수량 은 연속 창고 와 완전히 같다.
클래스 의 정의 차원 에서 볼 때 링크 스 택 과 연속 스 택 은 별 차이 가 없 으 며 유일한 차이 점 은 데이터 구성원 에 있 습 니 다.연속 스 택 의 데이터 구성원 은 하나의 배열 이 고 스 택 을 연결 하 는 데이터 구성원 은 스 택 헤드 포인터 일 뿐 입 니 다.
다음은 링크 스 택 의 클래스 정의 입 니 다.

//Link_Stack in C++
#include
using namespace std;
typedef double stackEntry;

const int overflow = 1;										//    
const int underflow = 2;
const int success = 0;

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

class link_stack
{
public:
	link_stack()											//    ，       
	{
		top_node = NULL;
	}
	bool link_stack::empty() const							//       
	{
		if (top_node != NULL)
			return false;
		return true;
	}

	int link_stack::push(const stackEntry &item)			//   item    （    ）
	{
		Node * new_top = new Node;							//   item      ，            

		if (new_top == NULL)
			return overflow;
		new_top->data = item;
		new_top->next = top_node;
		top_node = new_top;
		return success;
	}

	int link_stack::pop()									//      ，      ；      
	{
		Node * old_top = top_node;
		if (top_node == NULL)
			return underflow;
		top_node = old_top->next;
		delete old_top;
		return success;
	}

	int link_stack::top(stackEntry &item) const				//        item 
	{
		if (top_node == NULL)
			return underflow;
		item = top_node->data;
		return success;
	}

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

	link_stack::link_stack(const link_stack &original)		//      ，      
	{
		Node * new_copy;
		Node*original_node = original.top_node;
		if (original_node = NULL)
			top_node = NULL;
		else
		{
			top_node = new_copy = new Node;
			new_copy->data = top_node->data = original_node->data;
			new_copy->next = top_node->next = NULL;
			while (original_node->next != NULL)
			{
				original_node = original_node->next;
				new_copy->next = new Node;
				new_copy = new_copy->next;
				new_copy->next = NULL;
			}
		}
	}

	link_stack::~link_stack()								//        
	{
		while (!empty())
			pop();
	}
protected:
	Node * top_node;
};