AI 助理
文档备案控制台
开发者社区 开发与运维 文章 正文

数据结构之栈与队列

2017-05-17 1481
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介：
一。栈
1。概念：栈（stack）是一种线性数据结构，只能访问它的一端来存储或者读取数据。栈是一种后进先出的结构（LIFO)
2。栈的主要操作：
.clear()——清栈
.isEmpty()——检查栈是否为空
.push(e)——压栈
.pop()——出栈
.topEl()——返回栈顶元素

3。栈的java实现：使用数组链表实现

/**
 * 
 */
package  com.sohu.blog.denns_zane.stackqueue;

 /**
 * @author dennis
 * 
 */
public   abstract   class  AbstractStack  {
    public abstract Object pop();

    public abstract void push(Object obj);

    public abstract Object topEl();

    public abstract boolean isEmpty();

    public abstract void clear();
}


/**
 * 
 */
package  com.sohu.blog.denns_zane.stackqueue;

 /**
 * @author dennis
 * 
 */
public   class  Stack  extends  AbstractStack  {
    private java.util.ArrayList pool = new java.util.ArrayList();

    public Stack() {
    }

    public Stack(int n) {
        pool.ensureCapacity(n);
    }

    public void clear() {
        pool.clear();
    }

    public boolean isEmpty() {
        return pool.isEmpty();
    }

    public Object topEl() {
        if (isEmpty())
            throw new java.util.EmptyStackException();
        return pool.get(pool.size() - 1);
    }

    public Object pop() {
        if (isEmpty())
            throw new java.util.EmptyStackException();
        return pool.remove(pool.size() - 1);
    }

    public void push(Object el) {
        pool.add(el);
    }

    public String toString() {
        return pool.toString();
    }
}

4。栈的应用：
1）程序中的匹配分割符，如(,[,{等符号
2）大数的运算，比如大数相加，转化为字符串，利用栈处理
3）回文字，例子：
/**
 * 
 */
package  com.sohu.blog.denns_zane.stackqueue;

 import  java.io.BufferedReader;
 import  java.io.IOException;
 import  java.io.InputStreamReader;

 /**
 * @author dennis
 * 
 */
public   class  HuiWen  {

    /**
     * @param args
     */
    public static void main(String[] args) {
        BufferedReader buffer = new BufferedReader(new InputStreamReader(
                System.in));
        try {
            String str = buffer.readLine();
            if (str != null)
                isHuiWen(str);

        } catch (IOException e) {
            e.printStackTrace();
        }
        // TODO Auto-generated method stub

    }

    public static void isHuiWen(String str) {
        int length = str.length();
        char[] ch = str.toCharArray();
        Stack stack = new Stack();
        if (length % 2 == 0) {
            for (int i = 0; i < length / 2; i++) {
                stack.push(ch[i]);
            }
            for (int i = length / 2; i < length - 1; i++) {
                if (ch[i] != ((Character) stack.pop()).charValue()) {
                    System.out.println("不是回文字！！");
                    return;
                }

            }

            System.out.println(str + "是回文字！！");
        } else {
            for (int i = 0; i < length / 2; i++) {
                stack.push(ch[i]);
            }
            for (int i = (length / 2 + 1); i < length - 1; i++) {
                if (ch[i] != ((Character) stack.pop()).charValue()) {
                    System.out.println("不是回文字！！");
                    return;
                }
            }
            System.out.println(str + "是回文字！！");
        }

    }

}

4）java虚拟机中的本地方法栈


二。队列（queue）
1。概念：队列也是线性结构，从尾部添加元素，从头部删除元素。与栈相反，队列是先入先出结构（FIFO）
2。队列主要操作：
.clear() ——清空队列
.isEmpty()——判断队列是否为空
.enqueue(el)——从尾部插入元素el
.dequeue()——从队列中起出第一个元素，并删除
.firstEl()——返回队列第一个元素，不删除。

3。队列的实现：
1）环形数组：需要考虑队列已满的两种情况，1，第一个元素在最后一个元素之后；2，第一个元素在第一单元，最后一个元素在最后单元。给出一个java实现：
/**
 * 
 */
package  com.sohu.blog.denns_zane.stackqueue;

 /**
 * @author dennis
 * 
 */
//  queue implemented as an array
public   class  ArrayQueue  {
    private int first, last, size;

    private Object[] storage;

    public ArrayQueue() {
        this(100);
    }

    public ArrayQueue(int n) {
        size = n;
        storage = new Object[size];
        first = last = -1;
    }

    public boolean isFull() {
        return first == 0 && last == size - 1 || first == last + 1;
    }

    public boolean isEmpty() {
        return first == -1;
    }

    public void enqueue(Object el) {
        if (last == size - 1 || last == -1) {
            storage[0] = el;
            last = 0;
            if (first == -1)
                first = 0;
        } else
            storage[++last] = el;
    }

    public Object dequeue() {
        Object tmp = storage[first];
        if (first == last)
            last = first = -1;
        else if (first == size - 1)
            first = 0;
        else
            first++;
        return tmp;
    }

    public void printAll() {
        for (int i = 0; i < size; i++)
            System.out.print(storage[i] + " ");
    }
}

2 ）更适合实现队列的双向链表：
 /**
 * 
 */
package  com.sohu.blog.denns_zane.stackqueue;

 /**
 * @author dennis
 * 
 */
public   class  Queue  {
    private java.util.LinkedList list = new java.util.LinkedList();

    public Queue() {
    }

    public void clear() {
        list.clear();
    }

    public boolean isEmpty() {
        return list.isEmpty();
    }

    public Object firstEl() {
        return list.getFirst();
    }

    public Object dequeue() {
        return list.removeFirst();
    }

    public void enqueue(Object el) {
        list.add(el);
    }

    public String toString() {
        return list.toString();
    }


}
文章转自庄周梦蝶  ，原文发布时间5.17

4。队列的应用：线性规划方面
文章标签：
云数据库 ClickHouse
Java
存储
boxti
目录
相关文章
大数据文摘
|
前端开发 Java
java实现队列数据结构代码详解
本文详细解析了Java中队列数据结构的实现，包括队列的基本概念、应用场景及代码实现。队列是一种遵循“先进先出”原则的线性结构，支持在队尾插入和队头删除操作。文章介绍了顺序队列与链式队列，并重点分析了循环队列的实现方式以解决溢出问题。通过具体代码示例（如`enqueue`入队和`dequeue`出队），展示了队列的操作逻辑，帮助读者深入理解其工作机制。
大数据文摘
855 1
RossyYan
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算（头歌实践教学平台习题）【合集】
本关任务：编写一个程序实现顺序栈的基本运算。开始你的任务吧，祝你成功！​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念：初始化栈是为栈的使用做准备，包括分配内存空间（如果是动态分配）和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈，通常需要定义一个数组来存储栈元素，并设置一个变量来记录栈顶位置；对于链式栈，需要定义节点结构，包含数据域和指针域，同时初始化栈顶指针。 示例（顺序栈）： 以下是一个简单的顺序栈初始化示例，假设用C语言实现，栈中存储
RossyYan
1386 77
hahaha无
|
编译器 C语言 C++
栈区的非法访问导致的死循环(x64)
这段内容主要分析了一段C语言代码在VS2022中形成死循环的原因，涉及栈区内存布局和数组越界问题。代码中`arr[15]`越界访问，修改了变量`i`的值，导致`for`循环条件始终为真，形成死循环。原因是VS2022栈区从低地址到高地址分配内存，`arr`数组与`i`相邻，`arr[15]`恰好覆盖`i`的地址。而在VS2019中，栈区先分配高地址再分配低地址，因此相同代码表现不同。这说明编译器对栈区内存分配顺序的实现差异会导致程序行为不一致，需避免数组越界以确保代码健壮性。
hahaha无
379 0
栈区的非法访问导致的死循环(x64)
RossyYan
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算（头歌实践教学平台习题）【合集】
【数据结构——栈与队列】环形队列的基本运算（头歌实践教学平台习题）【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务：编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧，祝你成功！(4)出队一个元素a。(4)出队一个元素x。
RossyYan
686 13
【C++数据结构——栈与队列】环形队列的基本运算（头歌实践教学平台习题）【合集】
游客beejssedmb2sq
232.用栈实现队列，225. 用队列实现栈
在232题中，通过两个栈（`stIn`和`stOut`）模拟队列的先入先出（FIFO）行为。`push`操作将元素压入`stIn`，`pop`和`peek`操作则通过将`stIn`的元素转移到`stOut`来实现队列的顺序访问。 225题则是利用单个队列（`que`）模拟栈的后入先出（LIFO）特性。通过多次调整队列头部元素的位置，确保弹出顺序符合栈的要求。`top`操作直接返回队列尾部元素，`empty`判断队列是否为空。 两题均仅使用基础数据结构操作，展示了栈与队列之间的转换逻辑。
游客beejssedmb2sq
362 0
蓝易云
|
算法 调度 C++
STL——栈和队列和优先队列
通过以上对栈、队列和优先队列的详细解释和示例，希望能帮助读者更好地理解和应用这些重要的数据结构。
蓝易云
461 11
羑悻的小杀马特
|
DataX
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法：用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下： 1. **用两个队列实现栈**： - 插入元素时，选择非空队列进行插入。 - 移除栈顶元素时，将非空队列中的元素依次转移到另一个队列，直到只剩下一个元素，然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**： - 插入元素时，选择非空栈进行插入。 - 移除队首元素时，将非空栈中的元素依次转移到另一个栈，再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
羑悻的小杀马特
675 14
RossyYan
|
C++
【C++数据结构——栈和队列】括号配对（头歌实践教学平台习题）【合集】
【数据结构——栈和队列】括号配对（头歌实践教学平台习题）【合集】（1）遇到左括号：进栈Push()（2）遇到右括号：若栈顶元素为左括号，则出栈Pop()；否则返回false。（3）当遍历表达式结束，且栈为空时，则返回true，否则返回false。本关任务：编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务，你需要掌握：栈对括号的处理。（1）遇到左括号：进栈Push()开始你的任务吧，祝你成功！测试输入：(()))
RossyYan
722 7
ephemerals__
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
1478 10
那年春天
|
存储 算法
非递归实现后序遍历时，如何避免栈溢出？
后序遍历的递归实现和非递归实现各有优缺点，在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
那年春天
555 59

热门文章

最新文章

  • 1
    数据结构学习笔记——图的遍历算法（深度优先搜索和广度优先搜索）
  • 2
    【数据结构入门】-堆的实现以及堆排序（2）
  • 3
    [数据结构] 数组与链表的优缺点和区别
  • 4
    数据结构六：图（DataWhale系列）
  • 5
    【📕分布式锁通关指南 12】源码剖析redisson如何利用Redis数据结构实现Semaphore和CountDownLatch
  • 6
    【C++数据结构——图】图的遍历（头歌教学实验平台习题） 【合集】
  • 7
    数据结构（严蔚敏版）第三章——栈和队列（二）【栈的表示和操作的实现】
  • 8
    【Redis】常用数据结构之List篇：从常用命令到典型使用场景
  • 9
    数据结构（1）：使用面向对象模拟数组
  • 10
    Python教程：一文了解10种数据结构在Python中的实现方法
  • 1
    （Pandas）Python做数据处理必选框架之一！（一）：介绍Pandas中的两个数据结构；刨析Series：如何访问数据；数据去重、取众数、总和、标准差、方差、平均值等；判断缺失值、获取索引...
    900
  • 2
    （Python基础）新时代语言！一起学习Python吧！（一）：认识Python、Py解释器作用；编写第一个Python程序；Python中的基本数据结构
    810
  • 3
    Redis数据结构：别小看这5把“瑞士军刀”，用好了性能飙升！
    927
  • 4
    软考中级软件设计师专项-数据结构与算法上篇
    1164
  • 5
    【Redis】常用数据结构之List篇：从常用命令到典型使用场景
    995
  • 6
    Redis基础命令与数据结构概览
    474
  • 7
    Redis各类数据结构详细介绍及其在Go语言Gin框架下实践应用
    672
  • 8
    【Redis】 常用数据结构之String篇：从SET/GET到INCR的超全教程
    1020
  • 9
    【📕分布式锁通关指南 12】源码剖析redisson如何利用Redis数据结构实现Semaphore和CountDownLatch
    1004
  • 10
    Redis核心数据结构与分布式锁实现详解
    1425

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    一条命令迁移，帮你实现 OpenClaw 与 Hermes Agent 记忆互通！