Книжкова полиця#8355

Книжкова полиця (Розбір)

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

push_front $(x)$ — ставимо книгу з номером $x$ зліва;
push_back $(x)$ — ставимо книгу з номером $x$ справа;
pop_front() — знімаємо книгу з лівого краю;
pop_back() — знімаємо книгу з правого краю;

Приклад

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

Книги з полиці вилучаються в наступному порядку:

$p o p_f r o n t ()$ pop\_front() — книга номер $3$ ;
$p o p_ba c k ()$ pop\_back() — книга номер $9$ ;
$p o p_f r o n t ()$ pop\_front() — книга номер $1$ ;
$p o p_f r o n t ()$ pop\_front() — книга номер $2$ ;
$p o p_ba c k ()$ pop\_back() — книга номер $7$ ;

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

Оголосимо робочу чергу.

deque<int> s;

Читаємо кількість операцій $n$ .

scanf("%d",&n);

Послідовно обробляємо $n$ операцій.

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

Читаємо код операції $c m d$ .

  scanf("%d",&cmd); 
  if (cmd == 1)
  {

Ставимо книгу з номером $v a l$ на полицю з лівого краю.

    scanf("%d",&val); 
    s.push_front(val);
  } else
  if (cmd == 2)
  {

Ставимо книгу з номером $v a l$ на полицю з правого краю.

    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();
 }
}

C++

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:

Ставимо книгу з номером $l s t [0]$ на полицю з лівого краю.

    q.appendleft(lst[0])
  elif op == 2:

Ставимо книгу з номером $l s t [0]$ на полицю з правого краю.

    q.append(lst[0])
  elif op == 3:

Виводимо номер книги з лівого краю і знімаємо її.

    print(q.popleft())
  else:

Виводимо номер книги з правого краю і знімаємо її.

    print(q.pop())