栈和队列是两种重要的数据结构。从栈与队列的逻辑结构上来说,它们也是线性结构,
与线性表不同的是它们所支持的基本操作是受到限制的,它们是操作受限的线性表,是一种
限定性的数据结构。
栈(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(); } }
相关推荐
PPT内容是数据结构中有关栈和队列的知识,非常适合正在学习数据结构基础的同学
### 数据结构之栈和队列知识点详解 #### 一、选择题知识点解析 1. **栈的操作原则** 栈是一种特殊的线性表,它只允许在一端进行插入和删除操作,这一端称为栈顶(top)。另一端称为栈底(bottom),不允许在其上进行...
### 数据结构栈和队列知识点解析 #### 一、栈的基本概念与操作 **栈**是一种特殊的线性表,只允许在一端进行插入和删除操作,这一端被称为栈顶,另一端被称为栈底。栈遵循先进后出(First In Last Out, FILO)的...
基于c语言数据结构中栈和队列思想的简单停车场管理系统,以栈模拟停车场,以队列模拟车场外的便道,按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项:汽车“到达”或“离去”信息、汽车...
栈和队列是两种基础且重要的数据结构,广泛应用于各种算法和程序设计中。本课件及课堂笔记将深入探讨这两种数据结构的概念、特性以及它们在实际问题中的应用。 栈(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++实战篇(数据结构)...
本文实例讲述了Python常见数据结构之栈与队列用法。分享给大家供大家参考,具体如下: Python常见数据结构之-栈 首先,栈是一种数据结构。具有后进先出特性。 #栈的实现 class Stack(): def __init__(self,size): ...
### 数据结构之栈和队列知识点详解 #### 一、基础知识概述 **栈(Stack)** 和 **队列(Queue)** 都是线性数据结构的重要组成部分,它们在算法设计和计算机科学中有广泛的应用。 1. **栈**:栈是一种只允许在一端...
在这个"数据结构试验2-栈和队列实验报告含源码"中,我们将深入探讨两个基本且至关重要的数据结构——栈和队列。 栈(Stack)是一种后进先出(LIFO,Last In First Out)的数据结构。想象一个堆叠的盘子,最后一个放...
在这个"数据结构之栈、队列全部代码"的压缩包中,我们将会深入探讨两种基本且重要的线性数据结构——栈和队列,以及它们在编程中的实际应用。 首先,栈(Stack)是一种后进先出(LIFO,Last In First Out)的数据...
Java 数据结构之栈与队列 Java 数据结构之栈与队列是计算机科学中的一种基本数据结构,它们都是用于存储和处理数据的集合。栈和队列都是线性数据结构,但是它们的实现方式和使用场景不同。 一、栈(Stack) 栈是...
本次实验的主题是“数据结构实验”,重点关注栈和队列这两种基本数据结构,并利用它们来实现一个回文判断的功能。回文是一种特殊的字符串,其正读和反读是一样的,比如“上海自来水来自海上”。 首先,我们来看栈...
3.掌握栈和队列的逻辑结构特点、顺序存储结构、链式存储结构、顺序栈和链栈的结构体类型定义、循环队列和链队列的结构体类型定义、栈和队列在两种存储结构上的各种基本操作的实现算法。 4.将任意十进制数转换为三种...
数据结构——栈和队列经典测试题 一、栈和队列的概念和特点 栈是一种特殊的线性表,允许插入和删除运算的一端称为栈顶,不允许插入和删除运算的一端称为栈底。栈的特点是后进先出(Last In First Out,LIFO),即...