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

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

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

Первое из них (1 или 2) показывает, книга ставится с левого края или с правого соответственно, второе целое число (от 0 до 10000) обозначает номер книги. Операции снятия книги с полки описывается одним числом – 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())