연결리스트[큐]

큐를 연결리스트로 구현해보자 

기본문제를 통해 구현해봅시다~

 

 

연결리스트에 대한 강의를 듣고 구현해보는 것을 추천합니다

 

 

 

 

 

https://www.acmicpc.net/problem/10845

10845번: 큐

 

//리스트
//기본적인연산:삽입,삭제,검색 등
//리스트를 구현하는 방법:배열,연결
//배열단점: 크기가 고정, 중간에 데이터 삽입 및 삭제하려면 다수의 데이터를 옮겨얗ㅁ
//연결리스트:길이 제한 없음, 다른 데이터의 이동없이 중간에 삽입 및 삭제가능. 랜덤 액세스가 불가능
//배열은 시작주소를 통해 각 type에 의해 배열의 각 칸의 size가 동일하기때문에, 계산하여 임의의 데이터에 접근이 쉬움

//큐 연결리스트로 구현하기 
//불필요한 공간낭비를 줄일수있기때문에 배열 큐보단 연결이 더 유리한거같다.
//연결리스트에서 empty()구분법을 위한 구현법
#include<iostream>
#include<string>
using namespace std;

struct Node {
	int data;
	Node*next;//자기참조형 구조체
};
Node *head = 0, *tail = 0;
int _size = 0;
void push(int data)
{
	_size++;
	Node*temp = new Node();
	temp->data = data;
	if (head == 0)
	{
		head = tail = temp;
	}
	else
	{
		tail->next = temp;
		tail = temp;
	}
}
int front()
{
	if (_size == 0)return -1;
	else return head->data;
}
int back()
{
	if (_size == 0)return -1;
	else return tail->data;
}
void pop()
{
	if (_size == 0)return;
	_size--;
	Node *temp = head;
	head = head->next;

	delete temp;
}
int size()
{
	return _size;
}
int empty()
{
	if (_size == 0)return 1;
	else return 0;
}
void clear()
{
	while (_size)
	{
		Node *temp = head;
		head = head->next;
		_size--;
		delete temp;
	}
}
int main()
{
	int n = 0, data = 0;
	string input;
	cin >> n;
	while (n--)
	{
		cin >> input;
		if (input == "push")
		{
			cin >> data;
			push(data);
		}
		else if (input == "pop")
		{
			cout << front() << endl;
			pop();
		}
		else if (input == "size")
		{
			cout << size() << endl;
		}
		else if (input == "empty")
		{
			cout << empty() << endl;
		}
		else if (input == "front")
		{
			cout << front() << endl;
		}
		else if (input == "back")
		{
			cout << back() << endl;
		}
	}
}