선형리스트 : 데이터 삽입 삭제가 느림, 원소에 접근 빠름

연결리스트 : 데이터 삽입 삭제가 위치만 알면 빠름, 원소 접근은 비효율적

백준_큐 2_18258

값은 제대로 나오는데 시간 초과 뜨더라…

#include <iostream>
#include <string>
using namespace std;

// 저장 될 큐
int Que[2000001] = {};

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	// 1. 명령의 수 N
	int N = 0;
	cin >> N;

	// 1-1. 명령할 때 움직이는 count.
	int count = 0;
	int count2 = 0;

	// 2. 명령한다

	for (int i = 0; i < N; i++)
	{
		// 2=1. 명령어 입력
		string InputC;
		cin >> InputC;
		// 2-2. X 넣기
		int X = 0;

		// push X
		if (InputC == "push")
		{
			cin >> X;
			Que[count] = X;
			count++;
		}

		if (InputC == "pop")
		{
			if (Que[0] == NULL)
			{
				cout << "-1\\n";
			}

			else
			{
				// 가장 앞 정수를 출력한다.
				cout << Que[0] << "\\n";
				// 가장 앞 정수를 NULL값으로 바꾼다.
				Que[0] = NULL;

				count2 = count;
				// Que[1] 을 Que[0] 으로 바꿔 줘야 하므로 카운트 만큼 반복한다.
				for (int j = 0; j < count2; j++)
				{
					// 앞의 값에 다음 값을 넣어주고,
					Que[j] = Que[j + 1];
					// 다음 값을 NULL로 바꿔준다.
					Que[j + 1] = NULL;
					count--;
				}
				count = count2 - 1;
			}
		}

		if (InputC == "size")
		{
			cout << count << "\\n";
		}

		if (InputC == "empty")
		{
			if (Que[0] == NULL)
			{
				cout << "1\\n";
			}
			else
			{
				cout << "0\\n";
			}
		}

		if (InputC == "front")
		{
			if (Que[0] != NULL)
			{
				cout << Que[0] << "\\n";
			}
			else
			{
				cout << "-1\\n";
			}
		}

		if (InputC == "back")
		{
			if (Que[0] != NULL && count != 0)
			{
				cout << Que[count - 1] << "\\n";
			}
			else
			{
				cout << "-1\\n";
			}
		}
	}
	return 0;
}

백준_18258_큐 2

#include <iostream>
#include <string>
using namespace std;

// 저장 될 큐
int Que[2000001] = {};

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	// 1. 명령의 수 N
	int N = 0;
	cin >> N;

	// 1-1. 명령할 때 움직이는 count, 첫값 고정 first.
	int count = 0;
	int first = 0;

	// 2. 명령한다

	for (int i = 0; i < N; i++)
	{
		// 2=1. 명령어 입력
		string InputC;
		cin >> InputC;
		// 2-2. 정수 X 넣기
		int X = 0;

		// push X
		if (InputC == "push")
		{
			cin >> X;
			Que[count] = X;
			count++;
		}

		if (InputC == "pop")
		{
			if (Que[first] == NULL)
			{
				cout << "-1\\n";
			}

			else
			{
				// 가장 앞 정수를 출력한다.
				cout << Que[first] << "\\n";
				first++;
			}
		}

		if (InputC == "size")
		{
			cout << count - first << "\\n";
		}

		if (InputC == "empty")
		{
			if (Que[first] == NULL)
			{
				cout << "1\\n";
			}
			else
			{
				cout << "0\\n";
			}
		}

		if (InputC == "front")
		{
			if (Que[first] != NULL)
			{
				cout << Que[first] << "\\n";
			}
			else
			{
				cout << "-1\\n";
			}
		}

		if (InputC == "back")
		{
			if (Que[first] != 0 || Que[count] != 0) /
			{
				cout << Que[count - 1] << "\\n"; //여기서 에러 뜨는데, 맞긴 했음
			}
			else
			{
				cout << "-1\\n";
			}
		}
	}
	return 0;
}

백준_2164_카드2

#include <iostream>
#include <queue>
using namespace std;

// 1. N장의 카드가 있다
// 1-1. 카드는 1부터 N까지 번호가 붙어있다.
// 1-2. 1번 카드가 제일 위, N번 카드가 제일 아래다.
// 2. 제일 위 카드를 버리고, 현재 제일 위 카드를 제일 아래 카드 밑으로 옮긴다.
// 제일 마지막에 남게되는 카드를 구하는 문제

// ex) N = 4
// [1 2 3 4]
// [2 3 4] -> [3 4 2]
// [4 2] -> [4]

int main()
{
	// 카드 덱
	std::queue<int> cd;
	// 1. 명령 수
	int count = 1;
	int N;
	cin >> N;

	// 2. 카드 넣어주기
	for (int i = 1; i <= N; ++i)
	{
		cd.push(i);
	}
	// cd { 1, 2, 3, ... N }

	// 카드 하나가 남을 때 까지 
	while (cd.size() != 1)
	{
		//// 맨 윗 값을 없앤다
		cd.pop();
		// cd { 2, 3, ... N }
		
		//// 맨 윗 값을 제일 아래로 '옮긴다'
		cd.push(cd.front());
		// cd { 2, 3, ... N, 2 }
		cd.pop();
		// cd { 3, ... N, 2 }
	}
	cout << cd.front();
}