栈和队列


栈是先存进去的数据只能最后被取出来,是FILO(First In Last Out,先进后出)。

栈结构.png

用链表实现栈:

class Node<E>{
    Node<E> next = null;
    E data;
    public Node(E data) {this.data = data;}
}
public class Stack<E>{
    Node<E> top = null;
    public boolean isEmpty(){
      return top ==  null;
    }
    public void push(E data){
        Node<E> newNode = new Node<E>(data);
        newNode.next = top;
        top = newNode;
    }
    public E pop(){
        if(this.isEmpty()){
            return null;
        }
        E data = top.data;
        top = top.next;
        return data;
    }
    public E peek(){
        if(isEmpty()) {
            return null;
        }
        return top.data;
    }
}

队列是FIFO(First In First Out,先进先出),它保持进出顺序一致。

队列结构.png
class Node<E> {
    Node<E> next =null;
    E data;
    public Node(E data){
        this.data = data;
    }
}
public class MyQueue<E> {
    private Node<E> head = null;
    private Node<E> tail = null;
    public boolean isEmpty(){
      return head = tail;
    }
    public void put(E data){
        Node<E> newNode = new Node<E>(data);
        if(head == null && tail == null){
            head = tail = newNode;
        }else{
            tail.next = newNode;
            taile = newNode;
        }
    }
    public E pop(){
        if(this.isEmpty()){
            return null;
        }
        E data = head.data;
        head = head.next;
        return data;
    }
    public int size(){
        Node<E> tmp = head;
        int n = 0;
        while(tmp != null) {
            n++;
            tmp = tmp.next;
        }
        return n;
    }
    public static void main(String []args){
      MyQueue<Integer> q = new MyQueue<Integer>();
      q.put(1);
      q.put(2);
      q.put(3);
      System.out.println("队列长度:" + q.size());
      System.out.println("队列首元素:" + q.pop());
      System.out.println("队列首元素:" + q.pop());
    }
}

输出结果:

队列长度:3
队列首元素:1
队列首元素:2

注:
如果需要实现多线程安全,要对操作方法进行同步,用synchronized修饰方法

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 栈和队列是两种应用非常广泛的数据结构,它们都来自线性表数据结构,都是“操作受限”的线性表。 栈 栈(Stack):...
    karlsu阅读 689评论 0 1
  • 栈 栈的英文单词是Stack,它代表一种特殊的线性表,这种线性表只能在固定一端(通常认为是线性表的尾端)进行插入,...
    Jack921阅读 1,552评论 0 5
  • 一、队列的定义 【定义】:队列(queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。【特征】:...
    NotFunGuy阅读 658评论 0 3
  • 再过十几个小时,我又要离开这儿了,嗯,我又要和你相隔千里了,尽管虽然这段时间我们并没有什么交集,但至少想到你也在万...
    穿白衬衫的小狐狸阅读 310评论 0 0
  • 细细碎碎的夕阳落在往远处延伸的土路上, 眼前被这暖暖的金黄色包裹了,大路两旁的乡间草丛也打上了傍晚黄昏的金粉,透着...
    我及我阅读 317评论 0 1