一、链表实现栈
1.链表代码
https://blog.csdn.net/u010886217/article/details/85014250中链表LinkedVirtualHeadList实现类
2.链表实现栈的java代码
(1)stack接口
public interface stack<E> {
int getSize(); //获得元素个数
boolean isEmpty(); //判断是否有元素
void push(E e); //进栈
E pop(); //出栈
E peek(); //查询最顶端值
}
(2)实现stack接口
public class LinkedListStack<E> implements stack<E> {
private LinkedVirtualHeadList<E> list;
//1.构造函数
public LinkedListStack(){
list=new LinkedVirtualHeadList<>();
}
//***********************************************************************
//2.获得基本信息
@Override
public int getSize() {
return list.getSize();
}
@Override
public boolean isEmpty() {
return list.isEmpty();
}
//***********************************************************************
//3.入栈
@Override
public void push(E e) {
list.addFirst(e);
}
//***********************************************************************
//4.出栈
@Override
public E pop() {
// return null;
return list.removeFirst();
}
//***********************************************************************
//5.查询栈顶元素
@Override
public E peek() {
return list.getFirst();
}
public String toString(){
StringBuilder res=new StringBuilder();
res.append("Stack:top");
res.append(list);
return res.toString();
}
}
二、链表实现队列
1.链表实现队列原理
链表声明队首head和队尾tail两个指针。链表的tail端作为队尾,负责入队;链表的head端作为队首,负责出队。
实现原理图:
2.实现代码
public class LinkedListQueue<E> implements queue<E> {
//节点数据结构Node
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 e.toString();
}
}
//***************************************************************************
//1.基本信息
private Node head, tail;
private int size;
//***************************************************************************
//2.构造函数
public LinkedListQueue(){
head = null;
tail = null;
size = 0;
}
//***************************************************************************
//3.获得基本信息
@Override
public int getSize(){
return size;
}
@Override
public boolean isEmpty(){
return size == 0;
}
//***************************************************************************
//4.入队:在链表尾部入队
@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.出队:在链表首部出队
@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("Queue is empty.");
return head.e;
}
@Override
public String toString(){
StringBuilder res = new StringBuilder();
res.append("Queue: front ");
Node cur = head;
while(cur != null) {
res.append(cur + "->");
cur = cur.next;
}
res.append("NULL tail");
return res.toString();
}
public static void main(String[] args){
LinkedListQueue<Integer> queue = new LinkedListQueue<>();
for(int i = 0 ; i < 10 ; i ++){
queue.enqueue(i);
System.out.println(queue);
if(i % 3 == 2){
queue.dequeue();
System.out.println(queue);
}
}
}
}