덱 Double ended queue

• 원소의 추가 O(1)
• 원소의 제거 O(1)
• 제일 앞/뒤 원소 확인 O(1)
• 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능

 

연습 문제

 

1. 백준 10866 : https://www.acmicpc.net/problem/10866

StreamReader sr = new StreamReader(Console.OpenStandardInput());
StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

int n = int.Parse(sr.ReadLine());
LinkedList<int> deque = new LinkedList<int>();

for (int i = 0; i < n; i++)
{
    string[] s = sr.ReadLine().Split(" ");
    var a = s[0];
    int b = 0;
    if (s.Length >= 2)
    {
        b = int.Parse(s[1]);
    }

    if (s[0] == "push_front")
    {
        deque.AddFirst(b);
    }
    else if (s[0] == "push_back")
    {
        deque.AddLast(b);
    }
    else if (s[0] == "pop_front")
    {
        if (deque.Count == 0) sw.WriteLine(-1);
        else
        {
            sw.WriteLine(deque.First.Value);
            deque.RemoveFirst();
        }

    }
    else if (s[0] == "pop_back")
    {
        if (deque.Count == 0) sw.WriteLine(-1);
        else
        {
            sw.WriteLine(deque.Last.Value);
            deque.RemoveLast();
        }
    }
    else if (s[0] == "size")
    {
        sw.WriteLine(deque.Count);
    }
    else if (s[0] == "empty")
    {
        if (deque.Count == 0) sw.WriteLine(1);
        else sw.WriteLine(0);
    }
    else if (s[0] == "front")
    {
        if (deque.Count == 0) sw.WriteLine(-1);
        else
        {
            sw.WriteLine(deque.First.Value);
        }
    }
    else if (s[0] == "back")
    {
        if (deque.Count == 0) sw.WriteLine(-1);
        else
        {
            sw.WriteLine(deque.Last.Value);
        }
    }
}

sw.Flush();
sw.Close();
sr.Close();