`
何以-追梦
  • 浏览: 3253 次
  • 性别: Icon_minigender_1
  • 来自: 南京
最近访客 更多访客>>
社区版块
存档分类
最新评论

栈与队列

阅读更多

<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;
	}
}

       我也是个菜鸟,说得不明白的地方,还请谅解与补充!今天就暂时到这里,明天再来说说,用链表实现栈与队列。

 

1
1
分享到:
评论

相关推荐

    C语言实现栈与队列

    在IT领域,数据结构是编程基础中的重要组成部分,而栈(Stack)和队列(Queue)是最基础且广泛使用的两种数据结构。本项目是用C语言实现的栈和队列,提供了可加载和使用的源代码,这对于理解这两种数据结构的工作...

    栈与队列的基本操作

    1. 掌握栈的先进后出的特点。 2. 掌握栈的初始化、进栈、退栈、取栈顶、判栈空等基本操作。 3. 运用栈的基本操作解决一些简单的实际问题。 4. 掌握队列的先进先出的特点。 5. 掌握队列的初始化、入队、出队、取队首...

    数据结构栈和队列试题及答案

    栈与队列均属于线性表的一种特殊形式,该说法正确。 7. **特定输出序列的可行性** 通过一个栈可以输出序列3, 2, 5, 6, 4, 1,这种序列是可行的,因此该说法正确。 8. **栈和队列的定义** 栈和队列都是线性...

    栈与队列。

    栈和队列是两种重要的线性结构,定义,表示方法,代码实现

    栈与队列的基本操作与实现

    栈和队列是两种基本且常用的数据结构,它们各自具有特定的操作和特性。 **栈(Stack)**,也被称为后进先出(Last In, First Out,简称LIFO)结构。栈的主要操作包括: 1. **压栈(Push)**:将一个元素添加到栈顶...

    栈和队列(基础知识,单项选择题,填空题,简答题,程序)

    #### 栈与队列的特性及作用 栈和队列作为两种基本的数据结构,在程序设计中扮演着至关重要的角色。**栈**遵循后进先出(Last In First Out,LIFO)的原则,类似于一叠盘子,你只能在最上面添加或移除盘子;而**队列...

    栈与队列操作

    栈与队列,基本操作,可以直接运行,无需修改!

    栈与队列的应用与区别

    栈与队列的应用与区别

    数据结构 第三章 栈与队列 数据结构 第三章 栈与队列

    数据结构中的栈与队列是两种非常基础且重要的数据结构,它们在计算机科学和编程中扮演着不可或缺的角色。本章将深入探讨这两个概念,以及如何在实际问题中运用它们。 首先,栈(Stack)是一种遵循“后进先出”...

    数据结构(C语言版) 栈与队列 迷宫问题

    在C语言版的数据结构课程中,第三章深入探讨了两种基础但非常重要的数据结构——栈和队列,并应用它们解决实际问题,如迷宫问题。 栈是一种后进先出(LIFO)的数据结构,类似于我们日常生活中的叠放物品。它主要...

    栈与队列ppt及代码

    本资料包“栈与队列ppt及代码”提供了关于这两种数据结构的深入理解,包括它们的概念、实现方式以及在实际问题中的应用,特别适合准备面试或提升编程技能的IT从业者。 首先,栈(Stack)是一种后进先出(LIFO,Last...

    自定义的栈与队列

    本文将深入探讨自定义的栈与队列的实现,以及如何利用这两个数据结构的特性来解决问题。 首先,栈(Stack)是一种后进先出(LIFO, Last In First Out)的数据结构。它遵循“先进后出”的原则,类似于现实生活中的堆...

    栈 与 队列 学习资料

    本文将深入探讨栈与队列的概念、特点、应用以及它们的实现方式。 首先,栈(Stack)是一种遵循“后进先出”(LIFO,Last In First Out)原则的数据结构。在栈中,元素的添加(入栈,Push)和移除(出栈,Pop)都只...

    栈与队列头文件

    标题“栈与队列头文件”提示我们,这个压缩包包含的是用于创建和操作栈和队列的头文件。这些头文件提供了基本的数据结构接口,允许程序员快速高效地使用栈和队列。 栈(Stack)是一种后进先出(LIFO)的数据结构,...

    线性表,栈与队列的基本程序

    线性表、栈和队列是计算机...对于压缩包中的"线性表、栈与队列"文件,很可能是包含了这些数据结构的具体实现代码,供学习和参考。通过阅读和分析这些代码,开发者可以深入理解如何在实际项目中应用这些基本数据结构。

    栈与队列显示器

    在这个“栈与队列显示器”项目中,我们主要关注如何利用这两种数据结构进行动态数据展示。 栈是一种后进先出(LIFO)的数据结构,它遵循“最后入栈的元素最先出栈”的原则。在实际应用中,栈常用于函数调用、表达式...

    数据结构栈与队列的源代码

    本资源"数据结构栈与队列的源代码"提供了相关的编程练习,旨在帮助学习者通过实际编码加深对这两种数据结构的理解。 栈(Stack)是一种后进先出(Last In, First Out, LIFO)的数据结构,类似于日常生活中的堆叠...

    栈与队列.zip

    在实际编程中,栈和队列常与其他数据结构结合使用,如栈与队列的组合可以实现优先队列,通过调整元素的入栈和出栈顺序来达到优先级的处理。此外,它们也是图论算法(如深度优先搜索DFS和广度优先搜索BFS)中的关键...

    栈和队列的基本操作

    "栈和队列的基本操作" 栈和队列是计算机科学中两个基本的数据结构,它们的基本操作包括进栈、出栈、进队、出队等。栈是一种后进先出的数据结构,即最后一个入栈的元素将是第一个出栈的元素。队列是一种先进先出的...

    C++数据结构实验二:栈与队列的应用

    3.掌握栈和队列的逻辑结构特点、顺序存储结构、链式存储结构、顺序栈和链栈的结构体类型定义、循环队列和链队列的结构体类型定义、栈和队列在两种存储结构上的各种基本操作的实现算法。 4.将任意十进制数转换为三种...

Global site tag (gtag.js) - Google Analytics