public static class Node<T>{
public T value;
public Node<T> last;
public Node<T> next;
public Node(T data){
value = data;
}
}
//雙向隊(duì)列
public static class DoubleEndsQueue<T>{
public Node<T> head;
public Node<T> tail;
//1.從頭部增加節(jié)點(diǎn)
public void addFromHead(T value){
Node<T> cur = new Node<>(value);
if(head == null){
head = cur;
tail = cur;
}else {
cur.next = head;
head.last = cur;
head = cur;
}
}
//2.從尾部增加節(jié)點(diǎn)
public void addFromTail(T value){
Node<T> cur = new Node<>(value);
if(head == null){
head = cur;
tail = cur;
}else {
tail.next = cur;
cur.last = tail;
tail = cur;
}
}
//3.從頭部刪除節(jié)點(diǎn),并返回刪除節(jié)點(diǎn)的值
public T deleteFromHead(){
//(1)判斷是否為空
if(head == null)
return null;
Node<T> cur = head;
//(2)判斷是否只有一個(gè)節(jié)點(diǎn)
if(head == tail){
head = null;
tail = null;
}else {
head = head.next;
cur.next = null;
head.last = null;
}
return cur.value;
}
//4.從尾部刪除節(jié)點(diǎn),并返回刪除節(jié)點(diǎn)的值
public T deleteFromTail(){
//(1)判斷是否為空
if(head == null)
return null;
Node<T> cur = head;
//(2)判斷是否只有一個(gè)節(jié)點(diǎn)
if(head == tail){
head = null;
tail = null;
}else {
tail = tail.last;
cur.last = null;
tail.next = null;
}
return cur.value;
}
public boolean isEmpty(){
return head == null;
}
}
2.棧的實(shí)現(xiàn)
頭部進(jìn),頭部出
private static class DoubleQueueStack<T>{
private DoubleEndsQueue<T> queue;
public DoubleQueueStack() {
queue = new DoubleEndsQueue<T>();
}
public void push(T value){
queue.addFromHead(value);
}
public T pop(){
return queue.deleteFromHead();
}
public boolean isEmpty(){
return queue.isEmpty();
}
}
3.隊(duì)列的實(shí)現(xiàn)
頭部進(jìn),尾部出
private static class DoubleQueue<T>{
private DoubleEndsQueue<T> queue;
public DoubleQueue(){
queue = new DoubleEndsQueue<T>();
}
public void push(T value){
queue.addFromHead(value);
}
public T pop(){
return queue.deleteFromTail();
}
public boolean isEmpty(){
return queue.isEmpty();
}
}