HDU1507(最大二分匹配)

    为了更好的理解栈的原理,本文分别用数组和链表实现了栈,

    关于堆和栈的区别可参考文章:http://blog.csdn.net/oshirdey/article/details/20154627

    工程下载地址:http://download.csdn.net/detail/oshirdey/7162855

    1 数组实现栈:

/*
@ brife：数组实现栈类
*/
#include <Windows.h>

#ifndef  ARRAYSTACK_H
#define  ARRAYSTACK_H

const UINT DEFUALF_STACK_SIZE = 3;

template <typename T>
class CArrayStack
{
public:
	CArrayStack(void)
	{
		stackNode = new T[DEFUALF_STACK_SIZE];

		top = -1;

		capacity = DEFUALF_STACK_SIZE;
	}

	~CArrayStack(void)
	{
		delete[] stackNode;
		stackNode = NULL;

		count = 0;
		capacity = 0;
	}

	BOOL isEmpty()
	{
		return -1 == top;
	}

	void Push(const T& data)
	{
			//first be sure the array is enough big
			if(top+1 >= capacity)
			{
				capacity = capacity*2;

				T* tmp  = new T[capacity];
				for(int i = 0 ; i <= top ;++i)
				{
					tmp[i] = stackNode[i];
				}

				T* tmp1 = stackNode;
				stackNode = tmp;
				delete[] tmp1;
				tmp1 = NULL;
			}

			stackNode[++top]=data; 
	}
	
	void Pop()
	{
		if(!isEmpty())
		{
			--top;
		}
	}
	T& GetTop() 
	{
			if(!isEmpty())
			{
				return stackNode[top];
			}
	}

	int GetCount() const
	{
		return top+1;
	}

	int GetCapacity() const
	{
		return capacity;
	}

private:
	T *stackNode;

	int top; 
	int count;
	int capacity;
};
#endif

2  链表实现的栈

#include <Windows.h>

#ifndef  LISTSTACK_H
#define  LISTSTACK_H

template <typename T>
struct linknode{  
	 T data;  
	 linknode* next;  
}; 

template <typename T>
class CListStack
{
public:
	CListStack(void)
	{
		head = NULL;
		top = NULL;
		length = 0;
		
	}
	~CListStack(void)
	{
		linknode<T>* temp = head;

		while(!isEmpty())  
		{
			Pop(); 
		}
	}

	BOOL isEmpty()
	{
		return (NULL == head);
	}

	void Push(const T& data)
	{
		linknode<T>* temp = new linknode<T>;
		if(NULL == temp)
		{
			return;
		}
		temp->data = data;
		temp->next = NULL;
		
		if(NULL == head)
		{	
			head = temp;
			top = temp;
		}
		else
		{
			top->next = temp;
			top = temp;
		}
	
		length++;
		return;
	}

	void Pop()
	{
		if(isEmpty())
		{
			return;
		}

		linknode<T>* node = head;
		if(node == top)
		{
			head = NULL;
			top = NULL;
		}
		else
		{
			while(node->next != top)
			{
				node = node->next;
			}
			
			top = node;
			node = node->next;	
		}

		delete node;
		node = NULL;
		length--;
	}

	T& GetTop() 
	{
		if(!isEmpty())
		{
			linknode<T>* node = head;
		
			while(node->next != NULL)
			{
				node = node->next;
			}
			return node->data;
		}
		
	}

	int GetCount() const
	{
		return length;
	}

private:
	linknode<T> *head;  
	linknode<T> *top;  
	int length; 
};
#endif

3 测试代码

// 数据结构-栈.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "ArrayStack.h"
#include "ListStack.h"
#include <iostream>

using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
	CArrayStack<int> arrayStack;
	arrayStack.Push(1);
	arrayStack.Push(2);
	arrayStack.Push(3);

	arrayStack.Push(4);

	int top = arrayStack.GetTop();

	cout<<"the capacity is "<<arrayStack.GetCapacity()<<endl;
	arrayStack.Push(4);
	arrayStack.Push(4);
	arrayStack.Push(4);
	cout<<"the capacity is "<<arrayStack.GetCapacity()<<endl;

	CListStack<int> listStack;
	listStack.Push(1);
	listStack.Push(3);
	listStack.Push(5);
	int val = listStack.GetCount();
	val = listStack.GetTop();
	//getchar();
	return 0;
};

HDU1507(最大二分匹配),布布扣,bubuko.com

HDU1507(最大二分匹配)

原文：http://blog.csdn.net/mfmy_szw/article/details/23205717