8355. Book shelf
Mamed
arranges his books on a shelf. If the shelf is empty, he simply places a book
there. If there are already books on the shelf, he places the new book either
to the left or to the right of the existing books. Similarly, he removes books
only from the left or right edge. Based on the given information, it is
necessary to simulate Mamed’s actions
and print the
numbers of the books he will remove.
Input. The first line contains the number of operations n (1 ≤ n ≤ 104) that
Mamed performed. The following n
lines contain the details of the operations:
·
Each operation of placing a book on the shelf is
described by a pair of numbers. The first number (1 or 2) indicates which edge
the book is placed on (left or right), and the second number (from 0 to 104)
represents the number of the book.
·
Operations of removing a book from the shelf are
described by a single number: 3 or 4, indicating which edge the book is removed
from (left or right).
Output. For each operation of removing a book from the shelf, print the number of the book being removed.
|
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 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();
}
}
Java implementation –
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 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())