数据结构与算法:栈与队列

简介: 数据结构与算法:栈与队列

栈(Stack)


📌 什么是栈 ?

 栈也是一种线性数据结构.

 例如在一个死胡同里, 有5辆汽车(1~5)依次停放, 但当汽车需要倒出时我们发现, 最先进去的汽车1需要等待汽车5~汽车2依次倒出后才能出来;由此我们可以得出栈的特点先进后出(后进先出)

  这里的死胡同其实就相当于我们的栈,汽车就是需要操作的数据,将数据存放到栈中的过程称为入栈(也称压栈push),拿出的过程称为出栈(也称弹栈pop) .

 栈的底部成为栈底,顶部也就是操作数据的入口称为栈顶 .

注意我们操作数据是在栈顶处操作


🎀 创建Stack接口,并实现功能

public interface Stack<T> {
    //压栈
    void push(T ele);
    //弹栈
    T pop();
    //查找栈顶元素
    T peek();
    //是否为空
    boolean isEmpty();
    //栈中元素个数
    int getSize();
}

🎀 创建一个类,对接口中的抽象方法进行重写,将功能具体化

import com.learn.study1.MyArray;
 
public class Arraystack<T> implements Stack<T>{
 
    private MyArray<T> date;
    private int size;
 
    //构造函数(初始化)
    public Arraystack(){
        this.size = 0;
        this.date = new MyArray() ;
    }
 
    @Override
    public void push(T ele) {
        this.date.addTail(ele);
        this.size++;
    }
 
    @Override
    public T pop() {
        if (isEmpty()) {
            throw new IllegalArgumentException("stack is null");
        }
        T ele = this.date.removeTail();
        this.size--;
        return ele;
    }
 
    @Override
    public T peek() {
        if (isEmpty()) {
            throw new IllegalArgumentException("stack is null");
        }
        return this.date.getLastElement();
    }
 
    @Override
    public boolean isEmpty() {
        return this.size==0;
    }
 
    @Override
    public int getSize() {
        return this.size;
    }
    
    @Override
    public String toString() {
        return this.date.toString();
    }
}

✎ 队列(Queue)


📌 什么是队列 ?

• 队列就是排队,例如我们排队打饭,我们从对尾排队,打完饭后从对首离开。

特点:先进先出 FILO(只能从对尾进,对首出)


🎀 创建Queue接口,并实现功能    

public interface Queue<T> {
    //入队
    void offer(T ele);
    //出队
    T poll();
    //判断是否为空
    boolean isEmpty();
    //获取元素个数(长度)
    int getSize();
    //获取对首元素
    T getFront();
}

🎀 创建一个类,对接口中的抽象方法进行重写,将功能具体化                                                      

import com.learn.study1.MyArray;
 
public class ArrayQueue<T> implements Queue<T> {
    //数据容器
    private MyArray<T> date;
    //元素个数
    private int size;
 
    //初始化(构造方法)
    public ArrayQueue() {
        this.size = 0;
        this.date = new MyArray<>(20);
    }
 
    @Override
    public void offer(T ele) {//入队
        this.date.addTail(ele);
        this.size++;
    }
 
    @Override
    public T poll() {//出队
        if (isEmpty()) {
            throw new IllegalArgumentException("queue is empty!");
        }
        T res = this.date.getFirstElement();
        this.size--;
        return res;
    }
 
    @Override
    public boolean isEmpty() {
        return this.size == 0;
    }
 
    @Override
    public int getSize() {
        return this.size;
    }
 
    @Override
    public T getFront() {
        if (isEmpty()) {
            throw new IllegalArgumentException("queue is empty!");
        }
        return this.date.getFirstElement();
    }
}
目录
打赏
0
0
0
0
22
分享
相关文章
|
1月前
|
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
145 77
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
内网监控管理软件:PHP 语言队列算法揭秘
在数字化办公环境中,内网监控管理软件对企业的稳定运行和信息安全至关重要。本文深入介绍PHP中的队列算法及其在内网监控软件中的应用,包括监控数据收集、任务调度和日志记录等场景,通过代码示例展示其实现方法。队列算法可提高性能、保证数据顺序并实现异步处理,为企业提供高效的安全保障。
16 1
|
1月前
|
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
48 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
1月前
|
【C++数据结构——栈与队列】链栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现链栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储整数,最大
48 9
|
1月前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
39 7
【算法】栈
栈相关算法题,供参考,附有链接地址及板书
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
101 5
|
3月前
|
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
354 9
|
3月前
|
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
56 1
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等