<div class="iteye-blog-content-contain" style="font-size: 14px"></div>
今天我要来说说常用的两种数据结构:栈与队列。何为栈?简而言之,它具有“先进后出、后进先出”的特征。何为队列?就像我们日常生活中的排队,具有“先到先服务、先进先出”的特征。
一、基于数组的栈。
public class ArrayStack { private Object[] theArray; private int topOfStack; private static final int DEFAULT_CAPACITY=10; //初始化实例变量 public ArrayStack(){ theArray=new Object[DEFAULT_CAPACITY]; topOfStack=-1; } //判断是否为空栈 public boolean isEmpty(){ return topOfStack==-1; } //入栈 public void push(Object x){ //如果栈的容量不够,则扩展栈的容量 if (topOfStack+1==theArray.length) { doubleArray(); } theArray[++topOfStack]=x; } //出栈 public Object pop() throws Exception{ //如果栈为空,则抛出未找到异常 if (isEmpty()) { throw new Exception("UnderFlowExcption"); } return theArray[topOfStack--]; } //查看栈顶元素 public Object top() throws Exception{ if (isEmpty()) { throw new Exception("UnderFlowExcption"); } return theArray[topOfStack]; } //容量扩展的实现方式 private void doubleArray() { Object[] newArray=new Object[theArray.length*2+1]; for (int i = 0; i < theArray.length; i++) { newArray[i]=theArray[i]; } theArray=newArray; } }
二、基于数组的队列。
public class ArrayQueue { private Object[] theArray; //用来记录取值的位置 private int front; //用来记录添加值的位置 private int back; //存放当前数组已有多少个对象 private int currentSize; private static final int DEFAULT_CAPACITY=10; //初始化实例变量 public ArrayQueue() { theArray=new Object[DEFAULT_CAPACITY]; front=0; back=-1; currentSize=0; } //判断队列是否为空 public boolean isEmpty(){ return currentSize==0; } //入队 public void enqueue(Object x){ //如果当前已有对象的记录数等于数组长度,则扩容 if (currentSize==theArray.length) { doubleArray(); } //增加对象之后一定要记得改变实例变量的值 back=increment(back); theArray[back]=x; currentSize++; } //删除队列中的对象,即出队 public Object delQueue(){ //判断队列是否空之后,再操作 if (isEmpty()) { try { throw new Exception("underFlowException"); } catch (Exception e) { e.printStackTrace(); } } currentSize--; Object returnValue=theArray[front]; front=increment(front); return returnValue; } //获取队列中的第一个对象 public Object getFront(){ if (isEmpty()) { try { throw new Exception("underFlowException"); } catch (Exception e) { e.printStackTrace(); } } return theArray[front]; } //返回的值为参数+1或者为0 private int increment(int x) { if (++x==theArray.length) { x=0; } return x; } //扩容的方法 private void doubleArray() { Object[] newArray=new Object[theArray.length*2+1]; for (int i = 0; i < theArray.length; i++,front=increment(front)) { newArray[i]=theArray[front]; } front=0; theArray=newArray; back=currentSize-1; } }
我也是个菜鸟,说得不明白的地方,还请谅解与补充!今天就暂时到这里,明天再来说说,用链表实现栈与队列。
相关推荐
用C实现的栈与队列,可以加载使用。详见博文http://blog.csdn.net/pirateleo/article/details/7574598 共包含5个文件
栈与队列的基本操作与实现 数据结构 C语言
1. 掌握栈的先进后出的特点。 2. 掌握栈的初始化、进栈、退栈、取栈顶、判栈空等基本操作。 3. 运用栈的基本操作解决一些简单的实际问题。 4. 掌握队列的先进先出的特点。 5. 掌握队列的初始化、入队、出队、取队首...
栈和队列是两种重要的线性结构,定义,表示方法,代码实现
数据结构 (C语言版)上面的第三章栈与队列中的迷宫问题。
栈与队列,基本操作,可以直接运行,无需修改!
栈与队列的应用与区别
栈与队列的实现 c语言 包括顺序栈 链栈 和队列的实际应用
教学PPT数据结构 第三章 栈与队列 数据结构 第三章 栈与队列 数据结构 第三章 栈与队列 数据结构 第三章 栈与队列
栈和队列考试题 复习 栈和队列考试题 复习栈和队列考试题 复习
3.掌握栈和队列的逻辑结构特点、顺序存储结构、链式存储结构、顺序栈和链栈的结构体类型定义、循环队列和链队列的结构体类型定义、栈和队列在两种存储结构上的各种基本操作的实现算法。 4.将任意十进制数转换为三种...
第3章_栈与队列(java版).ppt
数据结构栈与队列实验报告
用模板类实现的线性表,栈与队列的数据存储,读出等相关操作
由于在停车场中间的车辆可以提出离开停车场,而且要求在离开车辆到停车场大门之间的车辆都必须先离开停车场,让此车离去,然后再让这些车辆依原来的次序进入停车场,因此在一个栈和一个队列的基础上,还需要有一个...
栈与队列的各种操作
本文件包含了数据结构栈与队列的几个练习源代码,让你轻松理解栈与队列
编写程序,建立容量为n(建议n=8)的循环队列,完成以下程序功能。输入字符#,执行一次出队操作,屏幕上显示出队字符;输入字符@,队列中所有字符依次出队并按出队次序在屏幕上显示各字符;输入其它字符,则输入的字符...
数据结构 java版,第三章ppt。栈与队列,课程资源
实验二 刘立嘉 石家庄铁道大学 算法与数据结构 栈与队列的应用