一.使用链表实现栈
增，删，查只对链表头进行操作，时间复杂度都为O(1)
链表头作为栈顶
LinkedListStack<E> implements Stack<E>
public class LinkedListStack<E> implements Stack<E> {
private LinkedList<E> list;
public LinkedListStack(){
list = new LinkedList<>();
}
@Override
public int getSize() {
return list.getSize();
}
@Override
public boolean isEmpty() {
return list.isEmpty();
}
@Override
public void push(E e) {
list.addFirst(e);
}
@Override
public E pop() {
return list.removeFirst();
}
@Override
public E peek() {
return list.getFirst();
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append("Stack: top");
res.append(list);
return res.toString();
}
}
二.使用链表实现队列
从两端添加元素很容易
从tail端删除元素不容易
所以，从head端删除元素，从tail端插入元素
不使用虚拟头节点，因为不从中间插入元素
由于没有设置dummyHead，要注意链表为空的情况
以下来设计方法：
新建一个类LinkedListQueue<E> implements Queue<e>
1.内部类Node
public class LinkedListQueue<E> implements Queue<E>{
private class Node{
public E e;
public Node next;
public Node(E e, Node next){
this.e = e;
this.next = next;
}
public Node(E e){
this(e, null);
}
public Node(){
this(null,null);
}
@Override
public String toString() {
return super.toString();
}
}
2.基本成员变量
private Node head, tail;
private int size;
3.基本方法
public LinkedListQueue(){
head = null;
tail = null;
size = 0;
}
@Override
public int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
4.入队操作
a.先判断tail是否为空，直接有tail = new Node(e)，令head = tail。
b.否则有tail.next = new Node(e)，tail = tail.next。
c.最后维护size，size ++。
@Override
public void enqueue(E e) {
if(tail == null){
tail = new Node(e);
head = tail;
}else{
tail.next = new Node(e);
tail = tail.next;
}
size ++;
}
5.出队操作
a.先判断队列是否为空，若为空则抛出异常
b.先令头节点Node retNode = head;
让头节点指向原头节点的next，head = head.next
令retNode与链表断开，即retNode.next = null
c.如果原来队列里只有一个元素，此时head == null，则需要维护tail，使tail = null
d.最后维护size，size --，并返回retNode.e
@Override
public E dequeue() {
if(isEmpty())
throw new IllegalArgumentException("Cannot dequeue from an empty queue"); Node retNode = head;
head = head.next;
retNode.next = null; //原来只有一个元素
if(head == null){
tail = null;
}
size --;
return retNode.e;
}
6.查看队首元素
@Override
public E getFront() {
if(isEmpty())
throw new IllegalArgumentException("Cannot dequeue from an empty queue");
return head.e;
}
7.重写toString()方法
@Override
public String toString() {
StringBuilder res = new StringBuilder();
// Node cur = dummyhead.next;
// while(cur != null){
// res.append(cur+"->");
// cur = cur.next;
// }
res.append("Queue: front:");
for(Node cur = head ; cur != null ; cur = cur.next){
res.append(cur + "—>");
}
res.append("NULL tail");
return res.toString();
}