provide code fragments that implement two methods. You do not need to provide anything other than those two methods.

Imagine using a doubly linked list to implement the stack ADT for values of a generic type. Skeleton code is provided below. Implement the push and pop methods. Instead of using the methods of the List ADT, manipulate the nodes directly. Make sure to handle any major error conditions by throwing a new RuntimeException. This doubly linked list uses sentinel nodes and you can assume that beginMarker and endMarker have already been initialized properly.

class LinkedListStack {

private static class Node { public Node(E d, Node p, Node n) {

data = d; prev = p; next = n; }

Node prev; Node next; E data;

}

Node beginMarker;

Node endMarker;

public void push(E x) { /* put the code for this in the file that you will upload */ }

public E pop() { /* put the code for this in the file that you will upload */ } }