- 浏览: 27086 次
- 性别:
- 来自: 福州
最新评论
所谓的栈,是一个含有至少两个基本操作的抽象数据类型:插入新的元素;删除最近时间插入的元素。遵循FILO(First in,last out,先进后出)的原则。
所谓的队列,也是一个含有至少两个基本操作的抽象数据类型:插入新的元素;删除最久时间插入的元素。遵循FIFO(First in,first out,先进先出)的原则。
关于栈和队列的具体实现,我们即可以借助于数组,也可以采用链表来实现。
1) 栈的数组实现方式
- public class MyStack<E> {
- public int count;
- public Object [] items;
- public boolean isEmpty(){
- return count==0;
- }
- public MyStack (){
- items=new Object[20];
- count=0;
- }
- public MyStack (int len){
- items=new Object[len];
- count=0;
- }
- /**
- 重新调整数组的大小
- **/
- private void resize(int size){
- Object [] newItems=new Object[size];
- for(int i=0;i<count;i++){
- newItems[i]=items[i];
- }
- items=newItems;
- }
- public void push(E e){
- if(count==items.length) resize(2*items.length);
- items[count++]=e;
- }
- public E pop(){
- if(count==0) return null;
- E item=(E)items[count-1];
- items[count-1]=null;
- count--;
- if(count>0&&count<=items.length/4) resize(items.length/2);
- return item;
- }
- public E peek(){
- if(count==0) return null;
- E item=(E)items[count-1];
- return item;
- }
- }
2) 栈的链式实现方式
- public class MyStack<E> {
- private class Node{
- E item;
- Node next;
- }
- Node head;
- public boolean isEmpty(){
- return head==null;
- }
- public void push(E t){
- Node node=new Node();
- node.item=t;
- node.next=head;
- head=node;
- }
- public E pop(){
- if(head==null)
- return null;
- E t=head.item;
- head=head.next;
- return t;
- }
- public E peek(){
- if(head==null)
- return null;
- else
- return head.item;
- }
- }
3) 队列的数组实现
- public class ArrayQueue<E> {
- private int front;
- private int rear;
- private int count;
- private int capacity;
- private int capacityIncrement;
- private Object[] itemArray;
- public ArrayQueue(){
- front=0;
- rear=0;
- count=0;
- capacity=10;
- capacityIncrement=5;
- itemArray=new Object[capacity];
- }
- public boolean empty(){
- return count==0;
- }
- public void insert(E e){
- if(count==capacity){
- capacity+=capacityIncrement;
- Object [] newArray=new Object[capacity];
- // for(int i=0;i<count;i++){
- // newArray[i]=itemArray[i];
- // }
- if(front<rear){
- //如果元素位于itemArray[front:rear-1]中
- for(int i=front;i<rear;i++){
- newArray[i]=itemArray[i];
- }
- }else{
- //否则,将元素分成两个区间
- //区间1:itemArray[0:rear-1]
- for(int i=0;i<rear;i++){
- newArray[i]=itemArray[i];
- }
- //区间2:itemArray[front:count-1]
- for(int i=front;i<count;i++){
- newArray[i]=itemArray[i];
- }
- front+=capacityIncrement;//然后,将front改为指向其新位置
- }
- itemArray=newArray;
- }
- itemArray[rear]=e;
- rear=(rear+1)%capacity;
- count++;
- }
- public E remove(){
- if(count==0){
- return null;
- }
- else{
- E temp=(E) itemArray[front];
- itemArray[front]=null;
- front=(front+1)%capacity;
- count--;
- return temp;
- }
- }
- }
数组的另一种更简单的实现方式:
- import java.util.NoSuchElementException;
- public class ArrayQueue {
- protected Object [] data;
- protected int size,
- head,
- tail;
- public ArrayQueue(){
- final int INITIAL_LENGTH=100;
- data=new Object[INITIAL_LENGTH];
- size=0;
- head=0;
- tail=-1;
- }
- public int size(){
- return size;
- }
- public boolean isEmpty(){
- return size==0;
- }
- public Object front(){
- if(size==0)
- throw new NoSuchElementException();
- return data[head];
- }
- public void enqueue(Object element){
- if(size==data.length){
- //double the length of data
- Object [] oldData=data;
- data=new Object[data.length*2];
- //copy oldData[head...OldData.length-1]
- //to data[0... OldData.length-1-head]
- System.arraycopy(oldData, head,data , 0, oldData.length-head);
- if(head>0)
- //copy oldData[0...tail] to data [head+1 .. oldlenght-1]
- System.arraycopy(oldData, 0, data, head+1, tail+1);
- head=0;
- tail=oldData.length-1;
- }
- tail=(tail+1)%data.length;
- size++;
- data[tail]=element;
- }
- public Object dequeue(){
- if(size--==0){
- throw new NoSuchElementException();
- }
- Object element=data[head];
- head=(head+1)%data.length;
- return element;
- }
- }
4) 队列的链式实现方式
- public class ListQueue<E> {
- private class Node<E>{
- E item;
- Node<E> link;
- }
- private Node<E> front,rear;
- private int count;
- public boolean empty(){
- return count==0;
- }
- public void insert(E e){
- //如果队列为空
- Node<E> newNode=new Node<E>();
- newNode.item=e;
- if(rear==null){
- front=rear=newNode;
- }else{
- rear.link=newNode;
- rear=newNode;
- }
- count++;
- }
- public E remove(){
- if(count==0){
- return null;
- }else{
- E e=front.item;
- front=front.link;
- if(front==null){
- rear=null;
- }
- count--;
- return e;
- }
- }
- public ListQueue<E> clone(){
- ListQueue<E> Q=new ListQueue<E>();
- for(Node<E> t=front;t!=null;t=t.link)
- Q.insert(t.item);
- return Q;
- }
- }
发表评论
-
基础数据结构——图
2010-09-20 15:49 875图(Graph)G由两个 ... -
基础数据结构——树
2010-09-20 15:48 790树:T={K,R}。K是包含n个结点的有穷集合(n ... -
基本数据结构——数组和链表
2010-09-20 15:38 1179数组的这个可 ... -
集合框架——Map
2010-09-20 15:28 781Map集合为映射 ... -
集合框架——Set
2010-09-20 15:19 821Set集合为集类型,集是最简单的一种集合,存放于集 ... -
集合框架——List
2010-09-20 15:16 1140List集合为列表类型,列表的主要特征是存放其中的 ... -
集合框架——Collection
2010-09-20 15:12 665Collection接口是List接口和Set接口 ... -
Object
2010-09-20 12:09 786java.lang.Object类是所有Java类的最高层次 ... -
Java的7个基础问题
2010-09-20 12:08 545问题一:我声明了什么! Java代码 ... -
堆和栈的区别
2010-09-20 12:06 615栈与堆都是Java用来在Ram中存放数据的地方。 与C++不同 ... -
Comparable和Comparator
2010-09-20 09:22 506public interface Comparable&l ... -
如何使用异常的原则(转)
2010-09-17 15:00 443作者:Bill Venners著,chenkw 译 摘要 ... -
异常的捕获与抛出原则(转)
2010-09-17 14:58 686在可能会出现exception的 ... -
J2EE系统异常的处理准则(转)
2010-09-17 11:43 611J2EE系统异常的处理准则 ... -
J2EE项目的异常处理(转)
2010-09-17 11:18 523为什么要在J2EE项目中谈 ... -
集合框架——简介
2010-09-16 14:46 728一、初识: 集合类是 Java基础技术中十分 ... -
异常那点事
2010-09-16 14:05 603一、概述 在Java程序设计语言中,异常对象都是派生自jav ... -
内部类详解
2010-09-16 13:11 635内部类详解 1、定义 ... -
优化JVM参数提高eclipse运行速度(转)
2010-09-16 12:59 573性能优化从身边做起。 首先建立评估体系,将workspac ... -
四个有害的java编码习惯
2010-09-15 19:16 589John O'Hanley 的这篇文章列举了四个有害的java ...
相关推荐
数据结构中栈和队列经典测试题
主要讲的是数据结构的栈和队列,相对于基础!
C++语言实现带小数的任意进制转换,使用了数据结构中的栈和队列,在VC++6.0上编译运行通过。对于学习C++和数据结构有一定的参考意义!
数据结构第三章笔记——栈和队列
数据结构(清华大学版)——栈和队列
不错的课件,很详细。计算机的基础,希望对你有用
北京师范大学数据结构教学资料第3章——栈与队列.ppt
数据结构实验报告
bilibili账号642257246,视频教程配套课件
东软数据结构实验报告——通过栈和队列来实现进制转换.doc
华中科技大学数据结构试验——栈和队列实验
NULL 博文链接:https://yuan.iteye.com/blog/305590
本章的基本内容是: 两种特殊的线性表——栈和队列 从数据结构角度看,栈和队列是操作受限的线性表,他们的逻辑结构相同。 从抽象数据类型角度看,栈和队列是两种重要的抽象数据类型。
软 件 学 院 上 机 实 验 报 告 课程名称: 数据结构 实验项目: 队列的应用 实 验 室: 耘 慧420 姓 名: 学 号 专业班级: 实验时间: 2016.11.17 "实验成绩 "评阅教师 " " " " "实验目的及要求 " "(一) 目的 " "1...
2015年考研数据结构核心考点命题思路解密的第3章栈和队列,由梦享论坛倾情力作,,免费不收积分提供给大家下载,是2015年计算机考研学生的绝佳资料,一定备受欢迎。
《数据结构——用C语言描述》以C语言为程序设计语言,采用系列式的叙述方式,引导读者循序渐进地掌握数组、链接表、栈和队列、树与森林、图和堆等不同的数据结构,并系统地介绍了查找和排序的各种实现方法。...
《数据结构——用C语言描述》+课后题答案包括顺序存储链式存储结构等 栈和队列推荐
栈和队列的应用—停车场管理系统