/*

Alex Chen

Thomas Jefferson High School for Science and Technology

March 2010, Contest #4, Senior Division

ACSL STACKS AND QUEUES

*/

import java.util.*;

public class ACSLSTACKSANDQUEUES_AlexChen

{

public static void main(String[] alex)

{

System.out.println("ACSL STACKS AND QUEUES - Alex Chen\n");

System.out.println("Enter the inputs: ");

Scanner scanner = new Scanner(System.in);

for(int w = 1; w <= 5; w++)

{

System.out.print(w + ". ");

StringTokenizer line = new StringTokenizer(scanner.nextLine(), ", ");

SQ sq = new SQ(line.nextToken().toUpperCase());

while(line.hasMoreTokens())

{

try{

String command = line.nextToken().toUpperCase();

if(command.equals("POP"))

sq.pop(Integer.parseInt(line.nextToken()));

else if(command.equals("PSH"))

sq.push(line.nextToken());

else if(command.equals("DUP"))

sq.dup(Integer.parseInt(line.nextToken()));

else if(command.equals("SWP"))

sq.swap(Integer.parseInt(line.nextToken()));

else if(command.equals("SWH"))

sq.change();

else if(command.equals("CRC"))

sq.circ(Integer.parseInt(line.nextToken()));

else if(command.equals("INS"))

sq.insert(Integer.parseInt(line.nextToken()), line.nextToken());

else if(command.equals("PIN"))

sq.pin(line.nextToken());

else if(command.equals("SRT"))

sq.sort(line.nextToken().toLowerCase());

else if(command.equals("PRT"))

sq.print(Integer.parseInt(line.nextToken()));

}

catch(Exception e) {}

}

}

System.out.println("\nDone.");

}

public static class SQ

{

LinkedList<String> structure;

char what;

public SQ(String s)

{

structure = new LinkedList<String>();

what = (s.charAt(0) == 'S') ? 'S' : 'Q';

for(char c = 'A'; c <= 'E'; c++)

push(c + "");

}

public void pop(int x)

{

if(x > structure.size())

x = structure.size();

if(what == 'S')

for(int i = 0; i < x; i++)

structure.removeLast();

else

for(int i = 0; i < x; i++)

structure.removeFirst();

}

public void push(String n)

{

structure.addLast(n);

}

public void dup(int x)

{

if(x > structure.size())

x = structure.size();

ArrayList<String> dupthese = new ArrayList<String>();

Iterator<String> it = structure.iterator();

for( ; dupthese.size() < x; )

dupthese.add(it.next());

for(String n : dupthese)

push(n);

}

public void swap(int x)

{

if(x > structure.size() / 2)

x = structure.size() / 2;

Queue<String> front = new LinkedList<String>();

Queue<String> back = new LinkedList<String>();

for(int i = 0; i < x; i++)

{

front.offer(structure.removeFirst());

back.offer(structure.removeLast());

}

for(int i = 0; i < x; i++)

{

structure.addLast(front.poll());

structure.addFirst(back.poll());

}

}

public void change()

{

what = (what == 'S') ? 'Q' : 'S';

}

public void circ(int x)

{

if(what == 'S')

for(int i = 0; i < x; i++)

structure.addFirst(structure.removeLast());

else

for(int i = 0; i < x; i++)

structure.addLast(structure.removeFirst());

}

public void insert(int x, String n)

{

if(what == 'S')

structure.add(structure.size() - x + 1, n);

else

structure.add(x - 1, n);

}

public void pin(String n)

{

structure.addFirst(n);

}

public void sort(String ad)

{

String[] array = new String[structure.size()];

for(int i = 0; i < array.length; i++)

array[i] = structure.removeFirst();

Arrays.sort(array);

if(ad.charAt(0) == 'a')

for(int i = 0; i < array.length; i++)

structure.addLast(array[i]);

else

for(int i = array.length - 1; i >= 0; i--)

structure.addLast(array[i]);

}

public void print(int x)

{

if(x > structure.size())

x = structure.size();

Iterator<String> it = structure.iterator();

if(what == 'S')

for(int i = 0; i < structure.size() - x; i++)

it.next();

for(int i = 0; i < x; i++)

System.out.print((i == 0 ? "" : ", ") + it.next());

System.out.println();

}

}

}