数据结构——栈和队列-创新互联

目录

成都创新互联公司长期为上1000家客户提供的网站建设服务，团队从业经验10年，关注不同地域、不同群体，并针对不同对象提供差异化的产品和服务；打造开放共赢平台，与合作伙伴共同营造健康的互联网生态环境。为通道企业提供专业的成都网站制作、成都网站设计，通道网站改版等技术服务。拥有10余年丰富建站经验和众多成功案例,为您定制开发。

一、栈（Stack）

1、定义

2、顺序结构模拟实现栈和常用方法

（1）.栈的顺序存储

（2）.基本方法

3、栈的链式结构与顺序结构对比

（1）.对比

4、区分概念

（1）.栈

（2）.虚拟机栈

（3）.栈帧

二、队列（Queue）

1、定义

2、链式结构模拟实现队列及常用方法

（1）.队列的链式结构初始化

（2）.常用方法

[1].入队

[2].出队

[3].获取队头元素

[4].获取有效元素个数

[5]. 检测是否为空

3、循环队列

（1）.循环队列的数组下标

（2）.区分空的循环队列和满的循环队列

4、链式结构队列和循环队列的比较

5、双端队列（Deque）

（1）.定义

（2）.Deque是一个接口，使用时必须创建LinkedList对象

（3）.Deque接口使用较多，栈和队列均可使用该接口

---

一、栈（Stack） 1、定义

栈是一种特殊的线性组，只允许在一端进行插入和删除元素（这一端称为 栈顶，另一端称为 栈底）。数据元素遵循 先进后出的原则。

入栈（压栈）：栈的元素插入操作

出栈：栈的元素删除操作

2、顺序结构模拟实现栈和常用方法 （1）.栈的顺序存储

该栈的底层逻辑是一组地址连续的存储单元，用来从栈底开始存放元素

（2）.基本方法

[1]. 构造一个空的栈。

public class MyStack {
    public int[] elem;
    public int usedSize;

    public MyStack(){
        this.elem=new int[10];
    }
}

[2].入栈

public void push(int val){
    if(isFull()){
        elem= Arrays.copyOf(elem,2*elem.length);
    }
    elem[usedSize++]=val;
}
public boolean isFull(){
    return usedSize==elem.length;
}

[3].出栈

public int pop(){
    if(isEmpty()){
        throw new EmptyException("栈为空！！！");
    }
    int val=elem[usedSize-1];
    usedSize--;
    return val;
}

[4].判空

public boolean isEmpty(){
    return usedSize==0;
}

[5].读取栈顶元素（不出栈）

public int peek(){
    if(isEmpty()){
        throw new EmptyException("栈为空！！！");
    }
    return elem[usedSize-1];
}

[6].获取个数

int size() 获取栈中有效元素个数

public int size(){
    return usedSize;
}

3、栈的链式结构与顺序结构对比 （1）.对比

相比于顺序结构的栈，链栈可以进行多个栈共享存储空间以提高内存利用率并且几乎不会存在栈满的情况。此外在时间复杂度上顺序栈和链栈相同均为O(1)。

在空间上顺序栈需要事先确定一个固定的长度，因此存取时很方便，但是可能会存在空间浪费。链式栈在空间上通过指针域连接下一个元素，虽然增加了一点内存的消耗但是栈的长度可以是无限的且不会存在空间浪费。

所以如果栈在使用过程中元素个数变化大,最好是用链栈。反之,如果元素个数的变化在一定范围内,建议使用顺序栈。

4、区分概念 （1）.栈

是一种数据元素先进后出的数据结构

（2）.虚拟机栈

具有特殊作用的一块内存空间。jvm为了对数据进行更好的管理，将内存按照不同的需求划分出来的结构。

栈区：线程私有的，栈区中存放的是函数调用相关的一些信息，主要是栈帧。

当栈区中内存空间不足时，会抛出StackOverflowException；当中的元素（栈帧）是按照数据结构中的栈的特性来实现的

（3）.栈帧

一种结构，这种结构与函数调用相关的，内部：局部变量表、操作数栈。

每个方法在运行时，jvm都会创建一个栈帧，然后将栈帧压入到虚拟机栈中。当方法调用结束时，该方法对应的栈帧会从虚拟机栈中出栈。

注意：每个方法的栈帧中结构都是一样，大小可能不同，但是栈帧的大小在程序编译时就已经确定好。

二、队列（Queue） 1、定义

只允许在一端进行数据插入（这一端称为 队尾Head/Front），在另一端进行数据删除（这一端称为 队尾Tail/Rear）的特殊线性表。数据元素 先进先出。

入队：队列的数据元素插入操作

出队：队列的数据元素删除操作

2、链式结构模拟实现队列及常用方法 （1）.队列的链式结构初始化

public class MyQueue {
    static class Node{
        public int val;
        public Node next;
        public Node(int val){
            this.val=val;
        }
    }
    public Node head;
    public Node last;
    public int usedSize;
}

注意：Queue是个接口，底层是通过链表实现的

（2）.常用方法

[1].入队

public void offer(int val){
    Node node=new Node(val);
    if(head==null){
        head=node;
        last=node;
    }else{
        last.next=node;
        last=node;
    }
    usedSize++;
}

[2].出队

public int poll(){
    if(empty()){
        throw new EmptyException("队列为空！！！");
    }
    int ret=head.val;
    head=head.next;
    if(head==null){
        last=null;
    }
    usedSize--;
    return ret;
}

[3].获取队头元素

public int peek(){
    if(empty()){
        throw new EmptyException("队列为空！！！");
    }
    return head.val;
}

[4].获取有效元素个数

public int getUsedSize() {
    return usedSize;
}

[5]. 检测是否为空

public boolean empty(){
    return first == null;
}

3、循环队列

循环队列通常使用数组实现,我们把队列的这种头尾相接的顺序存储结构称为循环队列。

当队头指针front = array.length-1后，再前进x个位置就自动到下一个循环，这可以利用除法取余实现。

初始时：front =rear=0。

判空：front=rear

判满：(rear+1)%array.length=front

队首指针退x：front = (front + array.length - x) % array.length

队尾指针进x：rear = (rear + x) % array.length

队列长度：len=(rear - front + array.length) % array.length

（1）.循环队列的数组下标

[1].下标在最后一个时再往后

index=(index+x)%arr.length

[2].下标在第一个时再往后

(index+arr.length-x)%arr.length

（2）.区分空的循环队列和满的循环队列

[1].添加usedSize属性

我们可以创建一个成员变量 usedSize，只有当 usedSize==队列长度时判满，当 usedSize==0 为空队列。

[2].使用标记

类型中增设flag数据成员，以区分是队满还是队空。

flag 等于0时，如果删除后 front = = rear ，则为队空；

flag 等于 1 时，如果插入后 front == rear ，则为队满。

[3].保留一个位置

为了区分队空和队满，我们保留最后一个位置。

如下图,当rear=front便认为是队空，当rear+1=front时认为是队满。

4、链式结构队列和循环队列的比较

在空间上：链式队列的数据存储是通过指针域连接的，会产生一些空间上的开销；而循环队列有一个固定的长度，所以在存储空间上存在浪费，因此链队更加的灵活。

在时间上：两者数据操作的时间复杂度都是O(1)。链式队列因为是通过指针域连接的，所以每次添加和删除结点都会存在一些时间消耗，而循环队列是先申请一个固定空间，使用时不释放，如果入队频繁，则两者还是有细微差异。

因此在确定队列大值时，使用循环队列；无法确定队列的长度时，则用链式队列。

5、双端队列（Deque） （1）.定义

双端队列（deque）是允许两端都可以入队和出队操作的队列（队头可以出队入队，队尾也可以出队入队）。deque 是 “double ended queue” 的简称。

（2）.Deque是一个接口，使用时必须创建LinkedList对象

（3）.Deque接口使用较多，栈和队列均可使用该接口

Dequestack = new ArrayDeque<>();//双端队列的线性实现
Dequequeue = new LinkedList<>();//双端队列的链式实现

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

标题名称：数据结构——栈和队列-创新互联
新闻来源：http://cqcxhl.com/article/ceoppg.html