JAVA 代码实现链表：https://blog.csdn.net/qq_40794973/article/details/101555091 
	
Java数组实现循环队列：https://mp.csdn.net/postedit/103112530



链表队列和循环队列的效率差别不大  


public interface Queue<E> {
    int getSize();
    boolean isEmpty();
    // 入队
    void enqueue(E e);
    // 出队
    E dequeue();
    // 返回对首元素
    E getFront();
}



 


从tail删除元素不容易
	
从head端删除元素，从tail端插入元素
	

	
由于没有 dummyHead，要注意链表为空的情况
	


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 e.toString();
        }
    }
    private Node head, tail;
    private int size;

    public LinkedListQueue() {
        head = null;
        tail = null;
        size = 0;
    }
    @Override
    public int getSize() {
        return size;
    }
    @Override
    public boolean isEmpty() {
        return size == 0;
    }
    @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++;
    }

    @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;
    }
    @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();
    }
}

//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);
//    }
//}


Queue: front 0<-NULL tail

Queue: front 0<-1<-NULL tail

Queue: front 0<-1<-2<-NULL tail

Queue: front 1<-2<-NULL tail

Queue: front 1<-2<-3<-NULL tail

Queue: front 1<-2<-3<-4<-NULL tail

Queue: front 1<-2<-3<-4<-5<-NULL tail

Queue: front 2<-3<-4<-5<-NULL tail

Queue: front 2<-3<-4<-5<-6<-NULL tail

Queue: front 2<-3<-4<-5<-6<-7<-NULL tail

Queue: front 2<-3<-4<-5<-6<-7<-8<-NULL tail

Queue: front 3<-4<-5<-6<-7<-8<-NULL tail

Queue: front 3<-4<-5<-6<-7<-8<-9<-NULL tail

双向链表实现栈和队列
前言
1. 双向链表
2. 栈 --》 双向链表 首部加 首部出 O(1)
3. 队列 --》 双向链表 首部加 尾部出 O(1)

前言

栈 --》 双向链表 首部加 首部出 O(1)

队列 --》 双向链表 首部加 尾部出 O(1)

1. 双向链表
	public static class Node<T> {
		public T value;
		public Node<T> last;
		public Node<T> next;

		public Node(T data) {
			value = data;
		}
	}

	//双向链表
	public static class DoubleEndsQueue<T> {
		public Node<T> head;
		public Node<T> tail;

		public void addFromHead(T value) {
			Node<T> cur = new Node<T>(value);
			if (head == null) {
				head = cur;
				tail = cur;
			} else {
				cur.next = head;
				head.last = cur;
				head = cur;
			}
		}

		public void addFromBottom(T value) {
			Node<T> cur = new Node<T>(value);
			if (head == null) {
				head = cur;
				tail = cur;
			} else {
				cur.last = tail;
				tail.next = cur;
				tail = cur;
			}
		}

		public T popFromHead() {
			if (head == null) {
				return null;
			}
			Node<T> cur = head;
			if (head == tail) {
				head = null;
				tail = null;
			} else {
				head = head.next;
				cur.next = null;
				head.last = null;
			}
			return cur.value;
		}

		public T popFromBottom() {
			if (head == null) {
				return null;
			}
			Node<T> cur = tail;
			if (head == tail) {
				head = null;
				tail = null;
			} else {
				tail = tail.last;
				tail.next = null;
				cur.last = null;
			}
			return cur.value;
		}

		public boolean isEmpty() {
			return head == null;
		}

	}

2. 栈 --》 双向链表 首部加 首部出 O(1)
public static class MyStack<T> {
		private DoubleEndsQueue<T> queue;

		public MyStack() {
			queue = new DoubleEndsQueue<T>();
		}

		public void push(T value) {
			queue.addFromHead(value);
		}

		public T pop() {
			return queue.popFromHead();
		}

		public boolean isEmpty() {
			return queue.isEmpty();
		}

	}

3. 队列 --》 双向链表 首部加 尾部出 O(1)
public static class MyQueue<T> {
		private DoubleEndsQueue<T> queue;

		public MyQueue() {
			queue = new DoubleEndsQueue<T>();
		}

		public void push(T value) {
			queue.addFromHead(value);
		}

		public T poll() {
			return queue.popFromBottom();
		}

		public boolean isEmpty() {
			return queue.isEmpty();
		}

	}

    所有的数据结构都可以大致分为两类，由连续单位构成或者由离散单位构成，具体到实体也就是数组实现或者链表实现。数组实现的数据结构方便查找和修改但不方便增删，链表实现的数据结构则刚好相反，适于增删却不便于查找。
      今天我们用链表来实现队列。

      我们需要实现的功能无非增删查改，这也是一般的数据结构都会具备的功能。

    一、关于Myqueue
      我们为这个队列设置一个Node类型的头结点head，这个头结点并不放数据，仅仅存一个指针，这样会更便于后面的插入和删除操作。然后再定义一个Node型的结点cur来表示当前结点，以及定义一个int 型的size记录队列的长度。

   二、关于Node
      我想实现的只是一个简单的单向队列，所以仅仅包含数据域data和指向下一个结点的“指针”next（Java中没有指针，只是类似一个索引），并且定义一个构造方法。(如果想实现双向队列可以定义front，next两个指针）代码如下：
public class Myqueque {
	public Node head;  //头结点，不存数据
	public Node cur;   //当前节点
	public int size;   //队列长度

	public class Node {
		public Object data;

		public Node next;

		public Node(Object data) {
			this.data = data;
			
		}
	}

三、增删查改
 增 ：增添操作给的参数是新加入的数据
      1.我们先创建一个新的节点来接受数据。
       2. 然后按照表是否为空表分讨论，因为两种情况的head指针位置是不同的。若为空表，则把新节点当作表头即可，让head           和cur都指向它；若不是空表，创建节点后让cur指向它。  
        代码如下：
// 增
	public void Add(Object input) {
		Node addnode = new Node(input);
		if(head==null) {  //如果头结点不存在

			head=addnode;
			head.next=null;
                       cur=head;//移动当前节点到头节点

		}
		 else  { 
                        //头节点存在，移动当前节点的位置
                        cur.next=addnode;

			cur=cur.next;

		}
		size++; //数组的大小++
		
}


删：删除操作给的参数是希望删除的位置。
     删除前也要问自己一个问题：表是不是空的？如果空了删个鬼哦；
    如果删的是表头，移动头指针就好了；
   如果删的是中间，则需要改变一下中间被删除节点的前一个节点，让其next绕过希望删除的节点temp；如果是删除表尾，则直接让cur.next=null。但是其实这两种情况可以合并为temp.next=temp.next.next;
  
	// 删
	public void Delete(int index) {
		//   Object retuNode;   如果希望取得想删除节点的值就创一个节点接收数据，最后返回。此处我不想返回它的值，可以自己灵活更改
		if (size <= 0) //数组的size必须大于0
			System.out.println("Error.");
		else {
			if(index==0){  //删头节点
			//   retuNode=head.data;
			   head=head.next;  //关键句
					   
			   }
			else if (index > 0 && index <= size) { //删除中间或表尾
				int count = 0;
				Node temp=head;
				while (count != index) {
                                temp=temp.next;
				count++;
				}
				retuNode=temp.next.data;
				temp.next=temp.next.next;   //关键句
				size--;
			}  
			else { //输入越界
				System.out.println("No such node.");

			}
		}

	}



 查：查找操作给的参数是被查找元素的位置index
       同样的，要考虑给的index是否合理，有没有越界；接下来定义一个节点temp接收数据，操作很简单了，不解释了  
//查
	public Object Search(int index) {
		int count = 0;
		Node temp=head;

		if (index >= 0 && index < this.Size()) {
			while (count<index) {
				temp = temp.next;
				count++;
			}
			return temp.data;
		} else { //如果要找的index越界
			System.out.println("No such node.");
			return null;
		}
	}


改：修改与查找十分相似，区别仅仅是参数除了修改的位置还多了个数据N，因为不知道N是什么类型的所以用Object；
         步骤就是先查找，再赋值。
	// 改
	public void Change(int index,Object N) {
		int count = 1;
		Node temp=head;

		if (index >= 0 && index <= this.Size()) {
			while (count != index) {
				temp = temp.next;
				count++;
			}
			temp.data=N;
		//	System.out.println(temp.data+"hhhhhhhhh已修改");  //调试用的
		} else {
			System.out.println("No such node.");
			
		}
	}


 好了现在队列创建好了，我们给它添加一个测试类看看对不对：
public class Test {

	public int number;
	public String name;
	
	public Test(int num,String s){
		number=num;
		name=s;
	}
	
	/*public String toString() {
		
        return getClass().getName() +;
    }*/
	
	
	public static void main(String[] args) {
		Test t1=new Test(1,"hhhhh");
		Test t2=new Test(2,"xxxxx");
		Test t3=new Test(3,"eeeee");
		Test t4=new Test(4,"aaaaa");
		
		Myqueque q=new Myqueque();
		q.Add(t1);
		q.Add(t2);
		q.Add(t3);
		q.Add(t4);
		
		Test test1=(Test)q.Search(0);
	//	Test test2=(Test)q.Change(3,"这是被修改的");
		System.out.println("sssssssssss+"+test1.number+":"+test1.name);
		//System.out.println("333333333333333+"+test2.number+":"+test2.name);
		q.Change(3,"这是被修改的");
		
		q.Delete(0);
		Test ts4=(Test)q.Search(0);
		System.out.println("shanchu"+ts4.number+":"+ts4.name);

		
		
	
		q.Change(3, "hahahhah");
		
	}

}

 测试的结果我就不放截图了（哈哈哈。。。）你可以自己试试哦

用单向链表实现元素进栈大概分为以下几个步骤；


创建节点


用链表的头部插入/删除元素


元素进栈


1.创建节点
_Node 类的构造函数是为了方便而设计，它允许为每个新创建的节点赋值。

由于 python 没有指针，因此一般使用类的结构实现指向关系。
例如：
class TreeNode:
    # 类的结构包含了指向关系
   def __init__(self,x):
        self.val = x
        self.next = None
  
# 创建实例
l1 = TreeNode(0)
l2 = TreeNode(1)
l3 = TreeNode(2)
  
# 引用表示指向关系
l1.next = l2
l2.next = l3

运行结果如下：
In [1]:l3
Out[1]: <__main__.TreeNode at 0x24d3e274908>
    
In [2]:l1.next.next
Out[2]: <__main__.TreeNode at 0x24d3e274908>
    
In [3]:l3.val
Out[3]: 2
    
In [4]:l1.next.next.val
Out[4]: 2

可以看出 l1.next.next 和 l3 指向同一个地址。
用单向链表实现元素压栈中，创建的节点为轻量级节点 _Node，为此定义了一个 __slots__对象，这是因为 python 中的命名空间均代表内置 dict 类的一个实例，即将范围内识别的名称与相关联的对象映射起来，这会导致额外内存使用量。

因此，这里使用__slots__声明，将所有实例成员分配给一个固定的字符串序列，利用一组元组来自动打包。
class _Node:
	# 赋值右边是一组元组
    __slot__='_element','_next'

创建节点的代码如下：
# 创建节点
class _Node:
    __slot__='_element','_next'
        
    def __init__(self,element,next):
        self._element = element
        self._next = next

2.在链表的头部插入/删除元素
只有在链表头部才能实现常熟时间内的有效插入和删除元素。为避免每次返回栈的大小时，必须遍历整个列表，因此定义一个变量 _size 持续追踪当前元素的数量。
def __init__(self):
    self._head = None
    self._size = 0

3.元素压栈
当栈顶插入新元素时，调用 _Node 类来完成链接结构的改变。
def push(self,e):
    self._head = self._Node(e,self._head)
    self._size += 1

每一个新元素进栈，将其赋予 _Node 类创建一个新节点，新节点的 _next 指针被设置为前一个栈顶的元素，头指针设置为新节点。即原栈顶后移，新元素成为栈顶。

这里可以创建一个实例更直观地了解一下。
#创建ls实例
ls=LinkedStack()
ls.push(1)
ls.push(2)

In [1]: ls._head._element
Out[1]: 2

In [2]:ls._head._next._element
Out[2]: 1

当第一次调用 ls.push(1) 的时候，栈顶为 1，当第二次调用 ls.push(2) 的时候， self._Node(e,self._head) 中 self._head 为 _element 为 1 的元素，调用 _Node 类的 self._next = next ，self._head 设置为 _next，实现原栈顶后移，同时 _head 设置为 2 的元素，新元素成为栈顶。
完整代码如下
class LinkedStack:
    
    # 创建节点
    class _Node:
        __slot__='_element','_next'
        
        def __init__(self,element,next):
            self._element = element
            self._next = next
        
    # 设置栈顶
    def __init__(self):
        self._head =None
        self._size = 0
        
    # 元素压栈
    def push(self,e):
        self._head = self._Node(e,self._head)
        self._size += 1



ls=LinkedStack()

ls.push(1)
ls.push(2)