首页 / 算法 / 数据结构与算法-栈和队列
数据结构与算法-栈和队列
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了数据结构与算法-栈和队列,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2022字,纯文字阅读大概需要3分钟。
内容图文
一、简介
众所周知,线性表是数据结构的基础,通常有两种实现方式:数组和链表。栈和队列是最常用的数据结构,它们基于线性表实现。
二、栈
定义:栈是限定仅在表尾进行插入和删除操作的线性表,即FILO。
栈被经常类比于弹夹,即先被压如弹夹的子弹最后被打出。根据线性表的实现方式得知,栈的实现方式有两种:数组实现和链表实现。
栈的数组实现:
package basic.data_structure.cha01; /** * 栈:先进后出(FILO),只允许在栈顶操作元素 * 栈的基本操作: * 初始化栈、弹栈、压栈、获取栈顶元素、判断是否为空 * * * 用数组实现栈。 * */ public class ArrayStack<T> { private T[] data; //数据容器privateint maxSize; //栈容量privateint top = -1; //栈顶指针public ArrayStack(){ this(10); } //初始化栈public ArrayStack(int capacity){ if(capacity > 0){ data = (T[])new Object[capacity]; maxSize = capacity; top = -1; }else{ thrownew RuntimeException("栈的初始化大小不能小于或等于0"); } } publicboolean isEmpty(){ return top == -1; } //压栈publicboolean push(T elem){ if(top == maxSize - 1){ thrownew RuntimeException("栈满"); } data[++top] = elem; returntrue; } //获取栈顶元素(不移除)public T peek(){ if(this.isEmpty()){ thrownew RuntimeException("空栈"); } return data[top]; } //弹栈public T pop(){ if(this.isEmpty()){ thrownew RuntimeException("空栈"); } return data[--top]; } }
很容易理解,都是实际上都是线性表的基本操作。
栈的链表实现:
package basic.data_structure.cha01; /** * 栈:先进后出 FILO,只允许在栈顶操作元素 * 栈的基本操作: * 初始化栈、压栈、弹栈、获取栈顶元素、当前栈大小 * * 栈的链表实现 * */ public class LinkedStack<T> { privateint currentSize;//当前栈大小(链表栈没有大小限制)private Node<T> top; //头节点 //初始化栈public LinkedStack(){ top = null; //头指针为空 } publicboolean isEmpty(){ return top == null; } publicint length(){ return currentSize; } //压栈publicboolean push(T elem){ Node<T> node = new Node<T>(elem, top); top = node; currentSize ++; returntrue; } //获取栈顶元素public T peek(){ if(this.isEmpty()){ thrownew RuntimeException("空栈"); } return top.data; } //弹栈public T pop(){ if(this.isEmpty()) { thrownew RuntimeException("空栈"); } Node<T> node = top; top = top.next; node.next = null; currentSize --; return node.data; } //节点(内部类)privatestaticclass Node<T>{ T data; //数据域 Node<T> next; //链域public Node(){} public Node(T data, Node<T> next){ this.data = data; this.next = next; } } }
原文:http://www.cnblogs.com/ddzhang/p/6696759.html
内容总结
以上是互联网集市为您收集整理的数据结构与算法-栈和队列全部内容,希望文章能够帮你解决数据结构与算法-栈和队列所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。