8355. Book shelf
Mamed puts
his books on the shelf. If there is no books on the shelf, he simply puts it
there. If there is, then he puts the book either to the right or to the left of
the books already arranged. He removes the books the same way, that is, he
removes only from the right or from the left edge. By the given information you
need to simulate the Mamed's actions and print the numbers of books that he
will take out.
Input. The first line contains
the number n (1 ≤ n ≤ 10000) – the number of operations performed by Mamed. The
information about operations is given in the next n lines. Each operation of putting the book on the shelf is
described by a pair of numbers.
The first
number (1 or 2) shows that the book is placed from the left or from the right
edge, respectively, second number (from 0 to 10000) denotes the book number.
The operation of removing a book from the shelf is described by one number – 3
or 4, from the left or from the right edge respectively.
Output. For each operation of
removing the book from the shelf, print out the number of the book to be taken.
|
Sample input |
Sample output |
|
10 1 1 2 2 1 3 2 7 2 9 3 4 3 3 4 |
3 9 1 2 7 |
SOLUTION
deque
Algorithm analysis
The shelf where the books are placed represents itself a double ended queue. In this
problem you must simulate the next
operations:
push_front(x) – put the book
number x from the left side;
push_back(x) – put the book
number x from the right side;
pop_front() – remove the book from left side;
pop_back() – remove the book from right side;
Example
Consider
the order in which the books are
placed 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
realization
Declare the double ended queue.
deque<int> s;
Read the number of operations n.
scanf("%d",&n);
Sequentially
process n operations.
for(i = 0; i < n; i++)
{
Read the code cmd of operation.
scanf("%d",&cmd);
if (cmd == 1)
{
Put the book number val on the shelf from the left side.
scanf("%d",&val);
s.push_front(val);
} else
if (cmd == 2)
{
Put the book number val on the shelf from the right side.
scanf("%d",&val);
s.push_back(val);
} else
if (cmd == 3)
{
Print the book number from
the left side and remove it.
printf("%d\n",s.front());
s.pop_front();
} else
{
Print the book number from
the right side and remove it.
printf("%d\n",s.back());
s.pop_back();
}
}
Java realization – 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 realization – 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 realization
Declare the double ended queue q.
from collections import deque
q = deque()
Read the number of operations n.
n = int(input())
Sequentially
process n operations.
for i in range(n):
op, *lst = list(map(int, input().split()))
if op == 1:
Put the book number lst[0] on the shelf from the left side.
q.appendleft(lst[0])
elif op == 2:
Put the book number lst[0] on the shelf from the right side.
q.append(lst[0])
elif op == 3:
Print the book number from
the left side and remove it.
print(q.popleft())
else:
Print the book number from
the right side and remove it.
print(q.pop())