`
jaesonchen
  • 浏览: 311274 次
  • 来自: ...
社区版块
存档分类
最新评论

数据结构之栈与队列

 
阅读更多

 

 

    栈和队列是两种重要的数据结构。从栈与队列的逻辑结构上来说,它们也是线性结构,
与线性表不同的是它们所支持的基本操作是受到限制的,它们是操作受限的线性表,是一种
限定性的数据结构。

 

    栈(stack)又称堆栈,它是运算受限的线性表,其限制是仅允许在表的一端进行插入和删除操作,不允许在其他任何位置进行插入、查找、删除等操作。表中进行插入、删除操作的一端称为栈顶(top),栈顶保存的元素称为栈顶元素。相对的,表的另一端称为栈底(bottom)。
    当栈中没有数据元素时称为空栈;向一个栈插入元素又称为进栈或入栈;从一个栈中删除元素又称为出栈或退栈。由于栈的插入和删除操作仅在栈顶进行,后进栈的元素必定先出栈,所以又把堆栈称为后进先出表(Last In First Out,简称LIFO)。

 

public interface Stack {
	//返回堆栈的大小
	public int getSize();
	//判断堆栈是否为空
	public boolean isEmpty();
	//数据元素e 入栈
	public void push(Object e);
	//栈顶元素出栈
	public Object pop() throws StackEmptyException;
	//取栈顶元素
	public Object peek() throws StackEmptyException;
}
public class StackEmptyException extends RuntimeException{
	public StackEmptyException(String err) {
		super(err);
	}
}

 

     Stack 的顺序存储实现:

public class StackArray implements Stack {
	private final int LEN = 8; //数组的默认大小
	private Object[] elements; //数据元素数组
	private int top; //栈顶指针
	public StackArray() {
		top = -1;
		elements = new Object[LEN];
	}
	//返回堆栈的大小
	public int getSize() {
		return top + 1;
	}
	//判断堆栈是否为空
	public boolean isEmpty() {
		return top < 0;
	}
	//数据元素e 入栈
	public void push(Object e) {
		if (getSize() >= elements.length) 
			expandSpace();
		elements[++top] = e;
	}
	private void expandSpace(){
		Object[] a = new Object[elements.length * 2];
		for (int i = 0; i < elements.length; i++)
			a[i] = elements[i];
		elements = a;
	}
	//栈顶元素出栈
	public Object pop() throws StackEmptyException {
		if (getSize() < 1)
			throw new StackEmptyException("错误,堆栈为空。");
		Object obj = elements[top];
		elements[top--] = null;
		return obj;
	}
	//取栈顶元素
	public Object peek() throws StackEmptyException {
		if (getSize() < 1)
			throw new StackEmptyException("错误,堆栈为空。");
		return elements[top];
	}
}

     Stack 的链式存储实现:

public class StackSLinked implements Stack {
	private SLNode top; //链表首结点引用
	private int size; //栈的大小
	public StackSLinked() {
		top = null;
		size = 0;
	}
	//返回堆栈的大小
	public int getSize() {
		return size;
	}
	//判断堆栈是否为空
	public boolean isEmpty() {
		return size == 0;
	}
	//数据元素e 入栈
	public void push(Object e) {
		SLNode q = new SLNode(e, top);
		top = q;
		size++;
	}
	//栈顶元素出栈
	public Object pop() throws StackEmptyException {
		if (size < 1)
			throw new StackEmptyException("错误,堆栈为空。");
		Object obj = top.getData();
		top = top.getNext();
		size--;
		return obj;
	}
	//取栈顶元素
	public Object peek() throws StackEmptyException {
		if (size < 1)
			throw new StackEmptyException("错误,堆栈为空。");
		return top.getData();
	}
}

 

 

    队列:它同堆栈一样,也是一种运算受限的线性表,其限制是仅允许在表的一端进行插入,而在表的另一端进行删除。在队列中把插入数据元素的一端称为队尾(rear),删除数据元素的一端称为队首(front)。向队尾插入元素称为进队或入队,新元素入队后成为新的队尾元素;从队列中删除元素称为离队或出队,元素出队后,其后续元素成为新的队首元素。
    由于队列的插入和删除操作分别在队尾和队首进行,每个元素必然按照进入的次序离队,也就是说先进队的元素必然先离队,所以称队列为先进先出表(First In First Out,简称FIFO)。

 

public interface Queue {
	//返回队列的大小
	public int getSize();
	//判断队列是否为空
	public boolean isEmpty();
	//数据元素e 入队
	public void enqueue(Object e);
	//队首元素出队
	public Object dequeue() throws QueueEmptyException;
	//取队首元素
	public Object peek() throws QueueEmptyException;
}
public class QueueEmptyException extends RuntimeException {
	public QueueEmptyException(String err) {
		super(err);
	}
}

 

 

     Queue 的顺序存储实现:

public class QueueArray implements Queue {
	private static final int CAP = 7;//队列默认大小
	private Object[] elements; //数据元素数组
	private int capacity; //数组的大小elements.length
	private int front; //队首指针,指向队首
	private int rear; //队尾指针,指向队尾后一个位置
	public QueueArray() {
		this(CAP);
	}
	public QueueArray(int cap){
		capacity = cap + 1;
		elements = new Object[capacity];
		front = rear = 0;
	}
	//返回队列的大小
	public int getSize() {
		return (rear - front + capacity) % capacity;
	}
	//判断队列是否为空
	public boolean isEmpty() {
		return front == rear;
	}
	//数据元素e 入队
	public void enqueue(Object e) {
		if (getSize() == capacity - 1)
			expandSpace();
		elements[rear] = e;
		rear = (rear + 1) % capacity;
	}
	private void expandSpace(){
		Object[] a = new Object[elements.length * 2];
		int i = front;
		int j = 0;
		//将从front 开始到rear 前一个存储单元的元素复制到新数组
		while (i != rear){ 
			a[j++] = elements[i];
			i = (i + 1) % capacity;
		}
		elements = a;
		capacity = elements.length;
		front = 0;
		rear = j; //设置新的队首、队尾指针
	}
	//队首元素出队
	public Object dequeue() throws QueueEmptyException {
		if (isEmpty())
			throw new QueueEmptyException("错误:队列为空");
		Object obj = elements[front];
		elements[front] = null;
		front = (front + 1) % capacity;
		return obj;
	}
	//取队首元素
	public Object peek() throws QueueEmptyException {
		if (isEmpty())
			throw new QueueEmptyException("错误:队列为空");
		return elements[front];
	}
}

 

 

     Queue 的链式存储实现:

public class QueueSLinked implements Queue {
	private SLNode front;
	private SLNode rear;
	private int size;
	public QueueSLinked() {
		front = new SLNode();
		rear = front;
		size = 0;
	}
	//返回队列的大小
	public int getSize() {
		return size;
	}
	//判断队列是否为空
	public boolean isEmpty() {
		return size == 0;
	}
	//数据元素e 入队
	public void enqueue(Object e) {
		SLNode p = new SLNode(e, null);
		rear.setNext(p);
		rear = p;
		size++;
	}
	//队首元素出队
	public Object dequeue() throws QueueEmptyException {
		if (size < 1)
			throw new QueueEmptyException("错误:队列为空");
		SLNode p = front.getNext();
		front.setNext(p.getNext());
		size--;
		if (size < 1) 
			rear = front; //如果队列为空,rear 指向头结点
		return p.getData();
	}
	//取队首元素
	public Object peek() throws QueueEmptyException {
		if (size < 1)
			throw new QueueEmptyException("错误:队列为空");
		return front.getNext().getData();
	}
}

 

 

 

 

  • 大小: 26.1 KB
  • 大小: 18.3 KB
  • 大小: 21.6 KB
分享到:
评论

相关推荐

    数据结构中的栈和队列

    PPT内容是数据结构中有关栈和队列的知识,非常适合正在学习数据结构基础的同学

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

    ### 数据结构之栈和队列知识点详解 #### 一、选择题知识点解析 1. **栈的操作原则** 栈是一种特殊的线性表,它只允许在一端进行插入和删除操作,这一端称为栈顶(top)。另一端称为栈底(bottom),不允许在其上进行...

    数据结构栈和队列(参考代码)

    ### 数据结构栈和队列知识点解析 #### 一、栈的基本概念与操作 **栈**是一种特殊的线性表,只允许在一端进行插入和删除操作,这一端被称为栈顶,另一端被称为栈底。栈遵循先进后出(First In Last Out, FILO)的...

    数据结构中栈和队列思想的停车场管理系统

    基于c语言数据结构中栈和队列思想的简单停车场管理系统,以栈模拟停车场,以队列模拟车场外的便道,按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项:汽车“到达”或“离去”信息、汽车...

    数据结构 栈和队列PPT

    栈和队列是两种基础且重要的数据结构,广泛应用于各种算法和程序设计中。本课件及课堂笔记将深入探讨这两种数据结构的概念、特性以及它们在实际问题中的应用。 栈(Stack)是一种后进先出(LIFO,Last In First Out...

    数据结构之栈和队列基本操作及实践

    在实际编程中,我们经常会遇到需要利用栈和队列解决问题的情况,因此掌握这些基本数据结构及其应用是每个程序员的基础技能之一。 在提供的压缩包文件“栈和队列”中,可能包含了关于这两种数据结构的实例代码、练习...

    数据结构(栈和队列)

    这是数据结构的栈和队列一章的课件。栈和队列在数据结构中很重要

    数据结构实验报告《二、栈和队列的运用》

    其中,栈(Stack)和队列(Queue)是最基本的数据结构之一,分别基于“后进先出”(LIFO, Last In, First Out)和“先进先出”(FIFO, First In, First Out)的原则工作。 **栈**是一种线性数据结构,只允许在一端...

    数据结构栈和队列解决迷宫问题

    数据结构栈和队列解决迷宫问题 本文档详细介绍了利用栈和队列解决迷宫问题的步骤,对于初学者学习数据结构能很好的进行辅导。本文档主要涉及到数据结构的两个重要概念:栈和队列,并介绍了如何使用这两个数据结构来...

    数据结构实验栈和队列详细实验报告

    【栈和队列的基本概念】 栈是一种特殊的线性表,具有“后进先出”(LIFO,Last In First Out)...通过这个实验,学生不仅能深入理解栈和队列的数据结构,还能锻炼编程和问题解决能力,为后续的算法学习打下坚实基础。

    C++实战篇(数据结构):栈、队列

    C++实战篇(数据结构):栈、队列 C++实战篇(数据结构):栈、队列 C++实战篇(数据结构):栈、队列 C++实战篇(数据结构):栈、队列 C++实战篇(数据结构):栈、队列 C++实战篇(数据结构):栈、队列 C++实战篇(数据结构)...

    Python常见数据结构之栈与队列用法示例

    本文实例讲述了Python常见数据结构之栈与队列用法。分享给大家供大家参考,具体如下: Python常见数据结构之-栈 首先,栈是一种数据结构。具有后进先出特性。 #栈的实现 class Stack(): def __init__(self,size): ...

    《数据结构》栈和队列答案

    ### 数据结构之栈和队列知识点详解 #### 一、基础知识概述 **栈(Stack)** 和 **队列(Queue)** 都是线性数据结构的重要组成部分,它们在算法设计和计算机科学中有广泛的应用。 1. **栈**:栈是一种只允许在一端...

    数据结构试验2-栈和队列实验报告含源码

    在这个"数据结构试验2-栈和队列实验报告含源码"中,我们将深入探讨两个基本且至关重要的数据结构——栈和队列。 栈(Stack)是一种后进先出(LIFO,Last In First Out)的数据结构。想象一个堆叠的盘子,最后一个放...

    清华严蔚敏《数据结构》栈和队列

    从数据结构的角度来看,栈和队列与线性表具有相似性,因为它们都是一种特殊的线性数据结构。然而,在数据类型的角度上,它们与线性表有着明显的区别,主要体现在对元素的访问和操作方式上。 #### 2. 基本操作对比 -...

    数据结构之栈、队列全部代码

    在这个"数据结构之栈、队列全部代码"的压缩包中,我们将会深入探讨两种基本且重要的线性数据结构——栈和队列,以及它们在编程中的实际应用。 首先,栈(Stack)是一种后进先出(LIFO,Last In First Out)的数据...

    java 数据结构之栈与队列

    Java 数据结构之栈与队列 Java 数据结构之栈与队列是计算机科学中的一种基本数据结构,它们都是用于存储和处理数据的集合。栈和队列都是线性数据结构,但是它们的实现方式和使用场景不同。 一、栈(Stack) 栈是...

    数据结构实验 栈和队列 回文判断

    本次实验的主题是“数据结构实验”,重点关注栈和队列这两种基本数据结构,并利用它们来实现一个回文判断的功能。回文是一种特殊的字符串,其正读和反读是一样的,比如“上海自来水来自海上”。 首先,我们来看栈...

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

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

    数据结构——栈和队列经典测试题

    数据结构——栈和队列经典测试题 一、栈和队列的概念和特点 栈是一种特殊的线性表,允许插入和删除运算的一端称为栈顶,不允许插入和删除运算的一端称为栈底。栈的特点是后进先出(Last In First Out,LIFO),即...

Global site tag (gtag.js) - Google Analytics