当前位置: 首页> 教育> 高考 > 阿拉营销网站_最早的c2c网站_云搜索app下载_付费推广平台有哪些

阿拉营销网站_最早的c2c网站_云搜索app下载_付费推广平台有哪些

时间:2025/7/11 23:24:52来源:https://blog.csdn.net/2301_81225368/article/details/144317013 浏览次数:1次
阿拉营销网站_最早的c2c网站_云搜索app下载_付费推广平台有哪些

1. 栈

栈是一种特殊的线性表,只允许在一端进行插入和删除元素操作。他的操作顺序是先进后出

栈顶:进行插入和删除元素操作的一端。

栈顶:不进行任何操作。

压栈:栈的插入操作。

出栈:栈的删除操作。

2. 栈的模拟实现

栈可以使用顺序表来实现,也可以使用链表来实现。

2.1 用顺序表实现的栈

2.1.1 栈的接口

public class MyStack {public int[] elem;public int usedSize;//构造方法public MyStack() {}//入栈public void push(int val) {}//出栈public int pop() {}//获取栈顶元素,但不删除public int peek() {}//判满private boolean isFull() {}//判空public boolean isEmpty() {}
}

2.1.2 栈的成员变量

用数组来表示栈,usedSize来表示栈中元素个数。

public int[] elem;
public int usedSize;

2.1.3 栈的构造方法

在构造方法中我们先开劈10个int空间。

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

2.1.4 入栈

思路:

        1. 首先判断数组是否已满,已满进行扩容。

        2. 进行元素插入,再usedSize++;

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

2.1.5 出栈

思路:

        1. 首先判断数组是否为空,为空异常。

        2. 再usedSize-- ,并返回usedSize下标的元素。 

public int pop() {if(isEmpty()) {throw new StackEmptyException();}usedSize--;return elem[usedSize];
}

2.1.6 获取栈顶元素,但不删除

思路:

        1. 判断判断数组是否为空,为空异常。

        2. 返回 usedSize-1下标的元素。

    public int peek() {if(isEmpty()) {throw new StackEmptyException();}return elem[usedSize-1];}

2.1.7 判满

判断数组 的长度是否等于usedSize。

    private boolean isFull() {return this.elem.length == usedSize;}

2.1.8 判空

判断usedSize是否等于零。

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

2.2 用链表实现栈

由于栈的先入后出的特性,如果我们使用单向链表,那么要拿到最后节点,它的时间复杂度为O(n),所以使用双向链表。

2.2.1 栈的接口

public class MyStack {static class ListNode {public ListNode next;public ListNode prev;public int val;public ListNode(int val) {this.val = val;}}public ListNode first;public ListNode last;//入栈public void push(int val) {}//出栈public int pop() {}//获取栈顶元素,但不删除public int peek() {}//判空public boolean isEmpty() {}
}

2.2.2 内部类

和双向连表差不多。

    static class ListNode {public ListNode next;public ListNode prev;public int val;public ListNode(int val) {this.val = val;}}

2.2.3 入栈

思路:

        1. 判断栈是否为空,为空头结点,尾结点同时指向node结点。

        2. 否则就进行尾插。

    public void push(int val) {ListNode node = new ListNode(val);if(isEmpty()) {first = last = node;}last.next = node;node.prev = last;last = node;}

2.2.4 出栈

思路:

       1. 判断栈是否为空,为空直接抛异常。

       2. 否则把尾结点删除。

       3. 最后返回删除之前尾结点的数值。 

    public int pop() {if(isEmpty()) {throw new StackEmptyException();}int val = last.val;last.prev.next = null;last = last.prev;return val;}

2.2.5 获取栈顶元素,但不删除

思路:

        1. 判断栈是否为空,为空直接抛异常。

        2. 返回尾结点的数值。

    public int peek() {if(isEmpty()) {throw new StackEmptyException();}int val = last.val;return val;}

2.2.6 判空

判断头节点是否为空。

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

3. JAVA中的栈

Stack继承了Vector,Vector和ArrayList类似,都是动态的顺序表。

实现了Serializable接口,可序列化

实现了Cloneable 接口,可克隆

实现了RandomAccess接口,可随机访问

3.1  栈的方法

     

关键字:阿拉营销网站_最早的c2c网站_云搜索app下载_付费推广平台有哪些

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: