8355. Книжная полка

Мамед раскладывает свои книги на полку. Если на полке нет ни одной книги, он просто ставит её туда. Если книги уже стоят на полке, он ставит новую либо справа, либо слева от уже расположенных. Забирает книги он аналогично, снимая только с правого или левого края. По заданной информации необходимо смоделировать действия Мамеда и вывести номера книг, которые он будет снимать.

Вход. В первой строке содержится количество операций n (1 ≤ n ≤ 10⁴), которые выполнил Мамед. Далее в n строках содержится информация об операциях:

· Каждая операция постановки книги на полку описывается парой чисел. Первое число (1 или 2) указывает, с какого края ставится книга (слева или справа), второе число (от 0 до 10⁴) обозначает номер книги.

· Операции снятия книги с полки описываются одним числом: 3 или 4, указывающим, с какого края снимается книга (с левого или с правого).

Выход. Для каждой операции снятия книги с полки выведите номер снимаемой книги.

Пример входа	Пример выхода
10 1 1 2 2 1 3 2 7 2 9 3 4 3 3 4	3 9 1 2 7

РЕШЕНИЕ

очередь

Анализ алгоритма

Полка, на которую ставятся книги, представляет собой двустороннюю очередь. В задаче необходимо смоделировать следующие операции:

· push_front(x) – ставим книгу с номером x слева;

· push_back(x) – ставим книгу с номером x справа;

· pop_front() – снимаем книгу с левого края;

· pop_back() – снимаем книгу с правого края;

Пример

Рассмотрим порядок расстановки книг на полке.

Книги с полки извлекаются в следующем порядке:

· pop_front() – книга номер 3;

· pop_back() – книга номер 9;

· pop_front() – книга номер 1;

· pop_front() – книга номер 2;

· pop_back() – книга номер 7;

Реализация алгоритма

Объявим рабочую очередь.

deque<int> s;

Читаем количество операций n.

scanf("%d",&n);

Последовательно обрабатываем n операций.

for(i = 0; i < n; i++)

{

Читаем код операции cmd.

scanf("%d",&cmd);

if (cmd == 1)

{

Ставим книгу с номером val на полку с левого края.

scanf("%d",&val);

s.push_front(val);

} else

if (cmd == 2)

{

Ставим книгу с номером val на полку с правого края.

scanf("%d",&val);

s.push_back(val);

} else

if (cmd == 3)

{

Выводим номер книги с левого края и снимаем ее.

printf("%d\n",s.front());

s.pop_front();

} else

{

Выводим номер книги с правого края и снимаем ее.

printf("%d\n",s.back());

s.pop_back();

}

}

Java реализация – LinkedList

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

Deque<Integer> q = new LinkedList<Integer>();

int n = con.nextInt();

for (int i = 0; i < n; i++)

{

int cmd = con.nextInt();

if (cmd == 1)

{

int val = con.nextInt();

q.addFirst(val);

} else

if (cmd == 2)

{

int val = con.nextInt();

q.addLast(val);

} else

if (cmd == 3)

{

System.out.println(q.getFirst());

q.removeFirst();

} else

{

System.out.println(q.getLast());

q.removeLast();

}

}

con.close();

}

}

Java реализация – LinkedList class

import java.util.*;

class Node

{

int data;

Node next;

public Node()

{

data = 0;

next = null;

}

public Node(int data)

{

this.data = data;

this.next = null;

}

}

class LinkedList

{

Node head, tail;

public LinkedList()

{

head = null;

tail = null;

}

public boolean Empty()

{

return head == null;

}

public void addFirst(int val)

{

if (tail == null) // list is empty

head = tail = new Node(val);

else

{

Node temp = new Node(val);

temp.next = head;

head = temp;

}

}

public void addLast(int val)

{

if (tail != null) // list is not empty

{

tail.next = new Node(val);

tail = tail.next;

}

else head = tail = new Node(val);

}

public boolean removeFirst()

{

if (Empty()) return false;

if (head == tail) // only one node in a list

head = tail = null;

else head = head.next;

return true;

}

public boolean removeLast()

{

if (Empty()) return false;

if (head == tail) // only one node in a list

{

head = tail = null;

}

else // if more than one node in the list

{

Node temp;

// find the predecessor of tail

for(temp = head; temp.next != tail; temp = temp.next);

tail = temp; // the predecessor of tail becomes tail

tail.next = null;

}

return true;

}

public int getFirst()

{

return head.data;

}

public int getLast()

{

return tail.data;

}

}

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

LinkedList list = new LinkedList();

int n = con.nextInt();

for (int i = 0; i < n; i++)

{

int cmd = con.nextInt();

if (cmd == 1)

{

int val = con.nextInt();

list.addFirst(val);

} else

if (cmd == 2)

{

int val = con.nextInt();

list.addLast(val);

} else

if (cmd == 3)

{

System.out.println(list.getFirst());

list.removeFirst();

} else

{

System.out.println(list.getLast());

list.removeLast();

}

}

con.close();

}

}

Python реализация

Объявим рабочую очередь q.

from collections import deque

q = deque()

Читаем количество операций n.

n = int(input())

Последовательно выполняем n операций.

for i in range(n):

op, *lst = list(map(int, input().split()))

if op == 1:

Ставим книгу с номером lst[0] на полку с левого края.

q.appendleft(lst[0])

elif op == 2:

Ставим книгу с номером lst[0] на полку с правого края.

q.append(lst[0])

elif op == 3:

Выводим номер книги с левого края и снимаем ее.

print(q.popleft())

else:

Выводим номер книги с правого края и снимаем ее.

print(q.pop())