c++线性栈及链栈

本文主要是介绍c++线性栈及链栈，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

• 黑书作者的异常头文件
  myexception.h

// exception classes for various error types

#ifndef myExceptions_
#define myExceptions_
#include <string>
#include<iostream>
using namespace std;

// illegal parameter value
class illegalParameterValue
{
public:
	illegalParameterValue(string theMessage = "Illegal parameter value")
	{
		message = theMessage;
	}
	void outputMessage() { cout << message << endl; }
private:
	string message;
};

// illegal input data
class illegalInputData
{
public:
	illegalInputData(string theMessage = "Illegal data input")
	{
		message = theMessage;
	}
	void outputMessage() { cout << message << endl; }
private:
	string message;
};

// illegal index
class illegalIndex
{
public:
	illegalIndex(string theMessage = "Illegal index")
	{
		message = theMessage;
	}
	void outputMessage() { cout << message << endl; }
private:
	string message;
};

// matrix index out of bounds
class matrixIndexOutOfBounds
{
public:
	matrixIndexOutOfBounds
	(string theMessage = "Matrix index out of bounds")
	{
		message = theMessage;
	}
	void outputMessage() { cout << message << endl; }
private:
	string message;
};

// matrix size mismatch
class matrixSizeMismatch
{
public:
	matrixSizeMismatch(string theMessage =
		"The size of the two matrics doesn't match")
	{
		message = theMessage;
	}
	void outputMessage() { cout << message << endl; }
private:
	string message;
};

// stack is empty
class stackEmpty
{
public:
	stackEmpty(string theMessage =
		"Invalid operation on empty stack")
	{
		message = theMessage;
	}
	void outputMessage() { cout << message << endl; }
private:
	string message;
};

// queue is empty
class queueEmpty
{
public:
	queueEmpty(string theMessage =
		"Invalid operation on empty queue")
	{
		message = theMessage;
	}
	void outputMessage() { cout << message << endl; }
private:
	string message;
};

// hash table is full
class hashTableFull
{
public:
	hashTableFull(string theMessage =
		"The hash table is full")
	{
		message = theMessage;
	}
	void outputMessage() { cout << message << endl; }
private:
	string message;
};

// edge weight undefined
class undefinedEdgeWeight
{
public:
	undefinedEdgeWeight(string theMessage =
		"No edge weights defined")
	{
		message = theMessage;
	}
	void outputMessage() { cout << message << endl; }
private:
	string message;
};

// method undefined
class undefinedMethod
{
public:
	undefinedMethod(string theMessage =
		"This method is undefined")
	{
		message = theMessage;
	}
	void outputMessage() { cout << message << endl; }
private:
	string message;
};
#endif

• 虚基类以及派生类
  stack.h

#pragma once
#include<iostream>
#include "myexception.h"
#include <sstream>
using std::ostringstream;
template<class T>
class stack
{
public:
	virtual ~stack(){}
	virtual bool empty()const = 0;
	virtual int size()const = 0;
	virtual T& top() = 0;
	virtual void pop() = 0;
	virtual void push(const T &) = 0;
};
template<class T>
class arraystack : public stack<T>
{
public:
	arraystack(int initialcapacity = 10);
	~arraystack() { delete[] stack; }
	bool empty()const { return stacktop == -1; }
	int size()const { return stacktop + 1; }
	T& top()
	{
		if (stacktop == -1)
			throw stackEmpty();
		return stack[stacktop];
	}
	void pop()
	{
		if (stacktop == -1)
			throw stackEmpty();
		stack[stacktop--].~T();
	}
	void push(const T& theelement);
private:
	int stacktop;
	int arraylength;
	T * stack;
};
template<class T>
arraystack<T>::arraystack(int initialcapacity)
{
	if (initialcapacity < 1)
	{
		ostringstream s;
		s << "Initial capacity" << initialcapacity << "must be > 0";
		throw illegalParameterValue(s.str());
	}
	arraylength = initialcapacity;
	stack = new T[arraylength];
	stacktop = -1;
}
template<class T>
void arraystack<T>::push(const T&theelement)
{
	stack[++stacktop] = theelement;
}
template<class T>
struct chainnode
{
	T element;
	chainnode<T> * next;
	chainnode() {}
	chainnode(const T &theelement)
	{
		this->element = theelement;
	}
	chainnode(const T &theelement, chainnode<T> * next)
	{
		this->element = theelement;
		this->next = next;
	}

};
template<class T>
class linkedstack : public stack<T>
{
private:
	int stacksize;
	chainnode<T> * stacktop;
public:
	linkedstack()
	{
		stacksize = 0;
		stacktop = NULL;
	}
	~linkedstack();
	bool empty() const { return stacksize == 0; }
	int size()const { return stacksize; }
	T& top()
	{
		if (stacksize == 0)
			throw stackEmpty();
		return stacktop->element;
	}
	void pop();
	void push(const T& theelement)
	{
		stacktop = new chainnode<T>(theelement, stacktop);
		stacksize++;
	}
};
template<class T>
linkedstack<T>::~linkedstack()
{
	while (stacktop != NULL)
	{
		chainnode<T> * nextnode = stacktop->next;
		delete stacktop;
		stacktop = nextnode;
	}
}
template<class T>
void linkedstack<T>:: pop()
{
	if (stacksize == 0)
		throw stackEmpty();
	chainnode<T>* nextnode = stacktop->next;
	delete stacktop;
	stacktop = nextnode;
	stacksize--;
}

• 测试文件，没写全…

#include <iostream>
#include"mystack.h"
int main()
{
    std::cout << "Hello World!\n";
	arraystack<int> j (5) ;
	j.push(2);
	j.top();
	linkedstack<int>a;
	a.push(6);
	a.pop();
	std::cout<<a.top();

}

这篇关于c++线性栈及链栈的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！