Book shelf (Editorial)

The shelf where the books are placed is represented as a double-ended queue. The task requires simulating the following operations:

• push_front$(x)$ — place a book with the number $x$ on the left;

• push_back$(x)$ — place a book with the number $x$ on the right;

• pop_front() — remove a book from the left edge;

• pop_back() — remove a book from the right edge;

Example

Let's consider the sequence of book placements on the shelf.

The books are removed from the shelf in the following order:

• pop\_front() — book number $3$;

• pop\_back() — book number $9$;

• pop\_front() — book number $1$;

• pop\_front() — book number $2$;

• pop\_back() — book number $7$;

Algorithm implementation

Declare a double ended queue.

deque<int> s;

Read the number of operations $n$.

scanf("%d",&n);

Process the $n$ operations sequentially.

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

Read the operation code $cmd$.

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

Place the book with the number $val$ on the left edge of the shelf.

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

Place the book with the number $val$ on the right edge of the shelf.

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

Print the number of the book from the left edge and remove it.

    printf("%d\n",s.front());
    s.pop_front();
  } else
  {

Print the number of the book from the right edge and remove it.

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

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

Python implementation

Declare a double ended queue $q$.

from collections import deque
q = deque()

Read the number of operations $n$.

n = int(input())

Process the $n$ operations sequentially.

for i in range(n):
  op, *lst = list(map(int, input().split()))

  if op == 1:

Place the book with the number $lst[0]$ on the left edge of the shelf.

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

Place the book with the number $lst[0]$ on the right edge of the shelf.

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

Print the number of the book from the left edge and remove it.

    print(q.popleft())
  else:

Print the number of the book from the right edge and remove it.

    print(q.pop())