또리야 개발하자

//********************************************************************
//	list class
//********************************************************************
#include 
#include  
using namespace std;
// 이중연결리스트
template 
class Node
{
public:
	T data;
	Node * next;
	Node * prev;
};
template 
class List
{
private:
	Node * head;
	Node * tail;
public:
	List()
	{
		head = new Node;
		tail = new Node;
		head->next = tail;
		head->prev = NULL;
		tail->prev = head;
		tail->next = NULL;
	}
	Node * Begin() { return head->next; }	// 맨 앞 노드를 리턴
	Node * End() { return tail; }		// 맨 뒤 노드를 리턴
	// 삽입
	void insert(Node * Where, T data)
	{
		Node * NewNode = new Node;
		NewNode->data = data;
		NewNode->next = Where->next;
		NewNode->prev = Where;
		Where->next->prev = NewNode;	// 순서주의
		Where->next = NewNode;
	}
	void push_back(T data)
	{
		insert(End()->prev, data);
	}
	void push_front(T data)
	{
		insert(head, data);
	}
	// 삭제
	void erase(Node * Where)
	{
		Where->prev->next = Where->next;
		Where->next->prev = Where->prev;
		delete Where;l
	}
	void pop_back()
	{
		erase(End()->prev);
	}
	void pop_front()
	{
		erase(Begin());
	}
	// 출력
	void show()
	{
		Node *p = Begin();
		while(p != End()->next)
		{
			cout << p->data << endl;
			p = p->next;
		}
	}
	class iterator
	{
	public:
		Node * cur;
	public:
		iterator( Node * p = 0 ) : cur(p){}
		// 역참조 오버로딩
		T & operator *()
		{
			return cur->data;	// 현재의 값을 리턴
		}
		// 다음 칸으로 이동
		iterator operator++()
		{
			if(cur != NULL)	// tail이 아닐때만
				cur = cur->next;
			return *this;
		}
		// 이전 칸으로 이동
		iterator operator--()
		{
			if(cur != NULL)	// head가 아닐때만
				cur = cur->prev;
			return *this;
		}
		bool operator != ( const Node * p )
		{
			if(cur != p)
				return true;
			else
				return false;
		}
	};
};
template  
class Queue
{
private:
	List list; 
public : 
	void push( T data)
	{
		list.push_back(data);
	}
	void pop()
	{
		list.pop_front();
	}
	T & front(){ return list.Begin()->data; }
	T & back(){ return  (list.End()-1)->data; }
};
void main()
{
	queue q;
	q.push(10);
	q.pop(); 
	List l;
	//List::iterator p = l.Begin();// 노드를 가리키는 객체 p 생성
	l.push_back(10);
	l.push_back(20);
	l.push_back(30);
	// 노드를 가리킬 수 있는 포인터 클래스
	List::iterator p;
	for( p = l.Begin(); p != l.End(); p++ )
		cout << *p << endl;
}

//*******************************************************
// 이중 연결 리스트 
//*******************************************************
//  -  head , tail 
#include 
#include 
//*******************************************************
struct Node
{
	int data; 
	Node * prev; // 앞의 노드를 가르키는 포인터 
	Node * next; // 뒤의 노드를 가리키는 포인터 
};
//*******************************************************
Node * head = NULL;
Node * tail  = NULL; 
//*******************************************************

Node * Begin(){ return head->next;}
Node * End(){   return tail->prev; }
//*******************************************************
// Utility 함수 !! 
//*******************************************************
Node * CreateNode( int data) 
{
	Node * NewNode =  (Node*)malloc(sizeof(Node)); 
	NewNode->data = data;
	NewNode->prev = NULL;
	NewNode->next = NULL; 
	return NewNode;
}
//*******************************************************
//  InitList : head, tail 노드 초기화 !! 
//*******************************************************
void InitList() 
{
	head = CreateNode(0); 
	tail = CreateNode(0); 
	head->next = tail;
	head->prev = head; 
	tail->next = tail; 
	tail->prev = head;
}

//*******************************************************
//  Insert( Node * first ,  Node * last ,  int data) 
//  : first포인터와 ㅣlast포인터 사이에 data를 넣어라 !! 
//*******************************************************
void Insert( Node * first ,  Node * last , int data ) 
{	
	// 노드 생성 
	Node * NewNode =  CreateNode(data); 
	//링크 연결 !! 
	NewNode->next = last; 
	NewNode->prev = first; 
	first->next = NewNode;
	last->prev = NewNode; 
}
//*******************************************************

void push_back(int data)
{
	Insert( End(), tail , data);
}
//*******************************************************
void push_front( int data )
{
	Insert( head, Begin(), data);
}
//*******************************************************
//*******************************************************
Node * find( int data) 
{
	Node * p = head->next; 
	while( p != tail)
	{
		if( p->data == data)
		{
			return p;
		}
		else 
		{
			p  = p->next;
		}
	}
	return NULL;
}
//*******************************************************

void show()
{
	Node * p = head->next; 
	while( p != tail)
	{
		printf("%d--", p->data);
		p = p->next;
	}
	puts("");
}
//*******************************************************
// erase( Node * where); 해당 노드를 삭제한다 !! 
//*******************************************************
void erase( Node * Where )
{	
	Where->prev->next = Where->next; 
	Where->next->prev = Where->prev; 
	free(Where);
}
void erase( int data )
{	
	erase( find(data)) ;
}
void pop_back()
{
	erase( End()); 
}
void pop_front()
{
	erase( Begin()); 
}

//**************************************************************
//  연결리스트 !! 
//**************************************************************
//  데이타를 갖는 노드를 포인터를 통해 연결하여 순차적인 선형 자료구조 !! 

// 배열 --> 연접리스트

// 물리적으로 떨어져있는 데이타들을 링크( 포인터)를 통해 연결하여 논리적인
// 선형 구조를 갖게한다 !! 
//                       1024             2048
//   [  10  ]         [  20  ]          [  30  ][  40  ]
//   [ 1024]  ----> [ 2048 ]   ----> [       ]  
       
//  연결리스트 --> 메모리가 절약 --> 필요할때마다 노드르 늘려 나간다 !! 
//             --> 크기를 모는 경우에 유용하다.  
//   동적배열 VS 연결리스트 !! 
// 동적배열은 크기가 늘어나거나 줄어들때 전체를 복사 할당 재할당 해제가 필요 !! 
// 연결리스트는 필요한 만큼만 사용한다 !! 
 
// 어디서든 !!  삽입 삭제 속도가 빠르게 동작한다 !! 



#include 
#include 
//*******************************************************************
// 단일 연결리스트 구현 
//*******************************************************************
// 노드 구조체 :  리스트내의 하나의 노드를 나타내기위한 구조체 !! 데이타와 링크 !! 
struct Node
{
	int Data; // 데이타 저장소 
	Node * next;  //  다음 노드를 가르킬 포인터 
};
//*******************************************************************
// 1) 더미노드를 활용하는 방법 !!  
//   head,tail더미 노드사이에 노드들을 추가하는 방법 !! 
// 2) head 노드만 갖고 구현하는 방법 !! 
// --> tail노드 대신에 next가 null인노드를 찾는 방법으로 리스트의 끝을 판별 !! 
// 3) head * 만 갖고 구현하는 방법 !! 
//*******************************************************************
// 더미 노드 선언 !! 
//*******************************************************************
Node * head = NULL; 
Node * tail = NULL; 
//*******************************************************************
// InitList :head, tail 노드생성 
//*******************************************************************
void InitList()
{
	//head생성 
	head = (Node*)malloc(sizeof(Node)); 
	// tail노드 생성 
	tail = (Node*)malloc(sizeof(Node)); 
	// 링크 연결 
	head->next =  tail; 
	tail->next  = NULL; 
}
//-----------------------------------------------------------------
// push_back :  리스트에 맨위에 노드를 삽입하는 함수 !! 
//-----------------------------------------------------------------
void push_back( int data) 
{
	// 1) 노드생성 
	Node * NewNode =  (Node*)malloc(sizeof(Node)); 
	NewNode->Data = data; 
	NewNode->next = NULL; 
	//2) 삽입 위치 찾기 !! 
	Node * p =  head; 
	while( p->next != tail)
	{
		p = p->next; 
	}
	// 3) 링크 연결 
	NewNode->next = p->next;
	p->next = NewNode;

}
//-----------------------------------------------------------------
//  2) 맨앞에 삽입하는 경우 
//-----------------------------------------------------------------
void push_front( int data)
{// 1) 할당 
	Node * NewNode = (Node*)malloc(sizeof(Node)); 
	NewNode->Data = data;
	NewNode->next = head->next;
	head->next =  NewNode;
}
//-----------------------------------------------------------------
// 3) 중간에 삽입  :  key값 뒤에 data삽입하자 !! 
//-----------------------------------------------------------------
void Insert( int key ,  int data)
{	
	// 1)노드 생성 !! 
	Node * NewNode = (Node*)malloc(sizeof(Node)); 
	NewNode->Data = data; 
	NewNode->next = NULL; 

	Node * p = head->next; 
	while( p != tail)
	{
		if( p->Data == key) 
		{
			NewNode->next = p->next; 
			p->next =  NewNode; 
			return;
		}
		else
		{
			p = p->next;
		}
	}
	free(NewNode);
	push_back(data);
	
}
//-----------------------------------------------------------------
// 맨뒤에서 삭제 
//-----------------------------------------------------------------
void pop_back() 
{
	Node * p, *s; 
	
	if( head->next == tail) 
	{
		puts("list Empty ~ !!"); return; 
	}
	else 
	{
		p = head->next;
		s = head; 
		while( p->next != tail)
		{
			s = p;
			p = p->next;
		}
		s->next = p->next; 
		free(p);
	}
}
//-----------------------------------------------------------------
//-----------------------------------------------------------------
// 맨앞에서 삭제 
//-----------------------------------------------------------------
void pop_front()
{
	Node * p = head->next; 
	if(head->next == tail) 
	{	
		puts("list empty !! ");
	}
	else
	{
		head->next = p->next;
		free( p );
	}
}
//-----------------------------------------------------------------
//  중간에서 삭제 !! 
//-----------------------------------------------------------------
void erase( int key)
{	
	Node * p, *s; 
	if( head->next == tail) 
	{
		puts("list empty !!");
	}
	else
	{
		s = head;
		p = head->next;
		while( p != tail) 
		{
			if( p->Data == key) 
			{
				s->next = p->next;
				free(p); 
				return;
			}
			else
			{
				s = p;
				p = p->next;
			}
			
		}
	} 
}
//-----------------------------------------------------------------
//-----------------------------------------------------------------
//-----------------------------------------------------------------
// Show() : 리스트 출력 !! 
//-----------------------------------------------------------------
void Show()
{
	Node * p = head->next; 
	while( p != tail) 
	{	
		printf("%d --> " ,  p->Data );
		p = p ->next;
	}
	puts(""); //개행
}
void main()
{
	InitList();		
	// 삽입 
	//-----------------------------------------------------------------
	//  1) 맨뒤에 삽입하는 경우 
	//-----------------------------------------------------------------
	push_back( 10 );  
	push_back( 20 );  
	push_back( 30 );  
	Show();
	//-----------------------------------------------------------------	
	//  2) 맨앞에 삽입하는 경우  
	//-----------------------------------------------------------------
/*	push_front(100);
	push_front(200);
	Show();
	//-----------------------------------------------------------------
	//  3) 중간에 삽입하는 함수 
	//-----------------------------------------------------------------
	Insert( 10, 999);
	Show();
	Insert( 30, 888);
	Show();
	Insert( 888, 1888);
	Show();*/
	// 삭제 연산 
	//-----------------------------------------------------------------
	// 1) 맨뒤에서 삭제 
	//-----------------------------------------------------------------
		erase(30);
		Show();
		erase(10);
		Show();
		erase(20);
		Show();

//-----------------------------------------------------------------
// 2) 맨앞에서 삭제 
//-----------------------------------------------------------------
	// 3) 중간에서 삭제  
	//-----------------------------------------------------------------
}

#include 
#include 
//*******************************************************************
// 단일 연결리스트 구현  - head노드만 !! 
//*******************************************************************
struct Node
{
	int Data; // 데이타 저장소 
	Node * next;  //  다음 노드를 가르킬 포인터 
};
//*******************************************************************
Node * head; 
//*******************************************************************
// CreateNode : 노드 생성 
//*******************************************************************

Node * CreateNode( int data) 
{
	Node * NewNode = (Node*)malloc(sizeof(Node)); 
	NewNode->Data = data;
	NewNode->next =NULL;
	return NewNode; 
}
//*******************************************************************
// init
//*******************************************************************
void Init()
{
	head =  CreateNode(0);
	head->next = NULL; 
}

//*******************************************************************
void push_front(int data)
{
	Node * NewNode  = CreateNode(data);
	if( head->next == NULL)
	{
		head->next = NewNode;
	}
	else 
	{
		NewNode->next = head->next;
		head->next = NewNode; 
	}
}
//*******************************************************************
void push_back(int data) 
{
	Node * NewNode = CreateNode(data);
	Node * p =  head; 
	while( p->next != NULL)
	{
		p = p->next; 
	}
	NewNode->next = p->next;
	p->next = NewNode;
}
//*******************************************************************
void Insert(int key, int data)
{	
	Node * NewNode = CreateNode(data);

	Node * p = head->next; 
	while( p != NULL)
	{
		if( p->Data == key) 
		{
			NewNode->next = p->next; 
			p->next =  NewNode; 
			return;
		}
		else
		{
			p = p->next;
		}
	}
	free(NewNode);
	push_back(data);
}

//-----------------------------------------------------------------
// 맨뒤에서 삭제 
//-----------------------------------------------------------------
void pop_back() 
{
	Node * p, *s; 
	
	if( head->next == NULL) 
	{
		puts("list Empty ~ !!"); return; 
	}
	else 
	{
		p = head->next;
		s = head; 
		while( p->next != NULL)
		{
			s = p;
			p = p->next;
		}
		s->next = p->next; 
		free(p);
	}
}
//-----------------------------------------------------------------
//-----------------------------------------------------------------
//  중간에서 삭제 !! 
//-----------------------------------------------------------------
void erase( int key)
{	
	Node * p, *s; 
	if( head->next == NULL) 
	{
		puts("list empty !!");
	}
	else
	{
		s = head;
		p = head->next;
		while( p != NULL) 
		{
			if( p->Data == key) 
			{
				s->next = p->next;
				free(p); 
				return;
			}
			else
			{
				s = p;
				p = p->next;
			}
			
		}
	} 
}
// 전체 삭제
void clear()
{
	Node * p, * s;
	if(head->next ==NULL)
	{
		puts("List Empty~!!");
		free(head);
		puts("노드 없었던거.Disappeared !!");
		return;
	}
	else
	{
		while(head->next!= NULL)
		{
		
			p = head->next;
			s= head;
			while(p->next!=NULL)
			{
				s=p;
				p=p->next;
			}
			s->next = p->next;
			free(p);
		
		}
		free(head);
		puts("노드 있었던거.Disappeared !!");
		return;
	}
}

//to.위에 코드 짜신분
//  - 이건 어때여
//void clear()
//{
//	while(head->next != NULL)
//	{
//		pop_back();
//	}
//	printf("clear!");
//} // 전체 삭제 !!  


//void clear() // 전체삭제
//{
//	Node *p = head->next;
//	while(p!=NULL)
//	{
//		head->next = p->next;
//		free(p);
//		p = head->next;
//	}
//} 


void pop_front()
{	Node * p;
	if( head->next == NULL)
	{
		puts("list empty !! ");
	}
	else
	{
		p = head->next;
		head->next = p->next;
		free(p); 
	}
}

void Show()
{
	Node * p = head->next; 
	while( p != NULL) 
	{	
		printf("%d --> " ,  p->Data );
		p = p ->next;
	}
	puts(""); //개행
}
//*******************************************************************
void main()
{
	Init(); 

	push_front(10);
	push_front(20);
	push_front(30);
	Show();
	pop_front();
	Show();
	pop_front();
	Show();
	pop_front();
	Show();
	clear();


}

//**********************************************************
//  컨테이너 !! 
//**********************************************************
// STL에서 제공해 주는 자료구조 클래스  
// 1) 시퀀스 컨테이터 - ( 선형 자료구조 ) 
//	-- vector, list, deque, 
//**********************************************************
#include 
#include  
#include  
#include  

using namespace std; 

void main() 
{
	vector v1; 
	for( int i = 1; i<=10; i++) 
		v1.push_back(i);
	//기존의 벡터 객체로 새로운 벡터를 생성한다 !! 
	
	// 할당기를 이용해서 새로운 객체를 생성 !! 
	//vector v(v1.begin(), v1.end(), v1.get_allocator()); 
	// 타입만을 얻어와서 새로운 객체를 생성 !!
	//vector  v( v1.get_allocator());
	// 10개를 생성하고 10으로 초기화 해라 !! 
	//vector v( 10,10);
	//vector v(10, 10, v1.get_allocator());
	vector v(v1);
	
	// 이터레이터의 범위를 통해서 값을 삽입 한다 !! 
	//v.insert(v.begin(), v1.begin(),v1.end());
	//v.insert( v.begin(), 10, 5);
	//v.insert(  v.end(), 10);

	//v.erase( v.begin(), v.begin()+3);
	/*v.erase( find( v.begin(), v.end(), 3));
	
	list l;
	for( int i = 0; i < 10 ; i++) 
		l.push_back( i);
		

	l.erase( find( l.begin() , l.end(), 3));


	//cout << v.capacity() << endl;
	for( int i = 0; i < v.size() ; i++) 
		cout << v[i] << endl;
	*/
}






//**********************************************************
// 2) 아답타 컨테이너 - stack ,queue, 
// 3) 연관 컨테이너 : 트리형의 자료구조 !! 
//   -  map,  set,  multimap , multiset 
//**********************************************************

//********************************************************
//  stack :  선입 후출 
//********************************************************
#include 
#include 
#include  
using namespace std;

template  
class STACK 
{	
private: 
	list c;
public : 
	void push( T data)	{	c.push_back(data); 	}
	void pop(){ c.pop_back();  }
	T & top() { return c.back(); }
};







void main()
{
	stack  s; 
	s.push(10);
	s.push(20);
	s.push(30);

	cout << s.top() << endl; 	
}

//*****************************************************
// 연관 컨테이너 !! --> 트리 계층적인 구조의 자료구조 !! 
//*****************************************************
// set . map 

// set --> 데이타 자체가 key값을 이룬다 !! 
//      --> 중복된 값을 허용하지 않는다 !! 
//      --> 정렬된 위치에 삽입이 되기때문에 검색속도가 빠르다 !! 

#include 
#include  

using namespace std; 

void main()
{
	multiset  s; 
	s.insert( 1 );
	s.insert( 4 );
	s.insert( 8 );
	s.insert( 1 );
	s.insert( 9 );
	s.insert( 6 ); 

	multiset::iterator p; 
	
	for( p = s.begin(); p!=s.end(); p++) 
		cout <<  *p << " - "<< endl;

	multiset::iterator p1; 

	p1 = s.find( 4 );
	
	if(p1 != s.end() )
		cout <<   *p1 << endl;

}

//*******************************************************
// Queue !! : 선입선출 -> FIFO 
//*******************************************************
#include 
#include  

using namespace std;

void main()
{
	queue Q; 
	Q.push(10);
	Q.push(20); 
	Q.push(30); 
	// 가장먼저 들어간 놈( 맨앞자리) 
	cout << Q.front() << endl;
		
	cout << Q.back() << endl;
	Q.pop();
	cout << Q.front() << endl;
}

//map : 셋은 키값으로만 관리를 하지만 map 키와 값을 쌍으로 관리를 한다 !! 

// pair 구조체 :  map에는 항상 key, value가 쌍으로 들어가기때문에.. 
// 2개를 묶어줄 구조체가 필요 pair !! 

#include 
#include 
#include