栈与队列

栈简介

栈先进者后出,栈是一种操作受限的线性表,只允许一段插入与删除数据。

当某个数据集合只涉及在一端插入和删除数据,并且满足后进先出、先进后出的特性,就可以选择栈这种数据结构。 用数组实现的栈称为顺序栈,用链表实现的栈称为链表栈 不管是顺序栈还是链式栈,存储数据只需要一个大小为 n 的数组就够了。在入栈和出栈过程中,只需要一两个临时变量存储空间,所以空间复杂度是 O(1)。并且入栈还是出栈只会涉及个别数据操作,空间复杂度也为O(1)

栈代码实现

/**
 * 基于链表实现的栈
 */
public class StackBaseLinkList {
    Node top = null;
    public void push(int value){
        Node nextNode  = new Node(value,null);
        //判断栈是否为空
        if(top==null){
            top = nextNode;
        }else {
            //nextNode的后继指针next 指向top栈,实现入栈
            nextNode.next = top;
            top = nextNode;
        }
    }
 
    //栈为空,返回-1
    public int pop(){
        if(top==null) return -1; 
        //一层一层取出入栈的值实现出栈
        int value = top.data;
        top = top.next;
        return value;
    }
    //打印栈数据
    private void printAll(){
        Node pNode = top;
        while(pNode!=null){
            System.out.print(pNode.getData()+"");
            pNode = pNode.next;
        }
        System.out.println(" ");
    }
}

队列

队列简介

先进先出,入队,放一个数据在尾部,出队,从头部取出数据,队列也是一种操作受限的线性表数据结构。用数组实现的队列叫顺序队列,用链表实现的队列叫链表队列 队列需要两个指针,一个head指针指向对头,一个tail指针指向队尾。

队列代码实现

/**
 * 基于链表实现的队列
 */
public class QueueBaseLinkList {
    private Node head = null;
    private Node tail = null;
    //入队
    public void equeue(String value){
        if(tail==null){
             Node newNode = new Node(value, null);
             head = newNode;
             tail = newNode;
        }else {
            tail.next = new Node(value, null);
            tail = tail.next;
        }
    }
    //出队
    public String dequeue(){
        if(head==null) return null;
        String value = head.data;
        head = head.next;
        if(head==null){
            tail=null;
        }
        return value;
    }
    private static class Node{
        private String data;
        private Node next;
        public Node(String data,Node next) {
            // TODO Auto-generated constructor stub
            this.data = data;
            this.next = next;
        }
        public String getData() {
            return data;
        }
    }
}

循环队列

循环队列是队列头部与尾部相连,也就是头指针与尾部指针链接在一起。

/**
 * 基于数组实现的循环队列
 *
 */
public class CircleQueue {
    private String[] items;
    private int n=0;
 
    private int head = 0;
    private int tail = 0;
 
    public CircleQueue(int capacity) {
        // TODO Auto-generated constructor stub
        items = new String[capacity];
        n = capacity;
    }
    private boolean equeue(String item){
        //队列满
        if((tail+1)%n==head) return false;
        items[tail] = item;
        tail = (tail+1)%n;
        return true;
    }
    private String dequeue(){
        //队列为空
        if(head == tail) return null;
        String value = items[head];
        head = (head+1)%n;
        return value;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Service 启动与绑定源码分析

    在Activity调用startService方法实质调用的是ContextWrapper中的startService方法。

    Yif
  • 数组与链表

    数组(Array)是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据。

    Yif
  • Activity 的 Window 创建过程

    Activity Window创建最终在ActivityThread 中的performLaunchActivity方法中,调用Activity的attach方...

    Yif
  • python cvs文件处理脚本 pyt

        最近有一个需求,需要讲csv文件通过http接口post方法导入到数据库,于是写了一个脚本,主要字符编码这一块踩了不少坑,最后终于完成了,可适用wind...

    py3study
  • 这位创造GitHub冠军项目的“老男人”,堪称10倍程序员本尊

    7月12日一款叫做TDengine的时序数据库项目在GitHub上开源了,这个项目一经发布就稳稳占据了GitHub排行榜的C位,目前TdEngine已经累积了5...

    AI科技大本营
  • 前端缓存最佳实践

    在介绍缓存的时候,我们习惯将缓存分为强缓存和协商缓存两种。两者的主要区别是使用本地缓存的时候,是否需要向服务器验证本地缓存是否依旧有效。顾名思义,协商缓存,就是...

    小生方勤
  • 【缓存】387- 前端缓存最佳实践

    在介绍缓存的时候,我们习惯将缓存分为强缓存和协商缓存两种。两者的主要区别是使用本地缓存的时候,是否需要向服务器验证本地缓存是否依旧有效。顾名思义,协商缓存,就是...

    pingan8787
  • 前端缓存最佳实践

    在介绍缓存的时候,我们习惯将缓存分为强缓存和协商缓存两种。两者的主要区别是使用本地缓存的时候,是否需要向服务器验证本地缓存是否依旧有效。顾名思义,协商缓存,就是...

    Nealyang
  • RabbitMQ如何解决各种情况下丢数据的问题

    如果想学习Java工程化、高性能及分布式、深入浅出。微服务、Spring,MyBatis,Netty源码分析的朋友可以加我的Java高级交流:854630135...

    java架构师
  • python简单学-----------

    2.对中文的支持 python2和python3不一样,python3默认支持,python2 需要加上

    py3study

扫码关注云+社区

领取腾讯云代金券