`
啸笑天
  • 浏览: 3462227 次
  • 性别: Icon_minigender_1
  • 来自: China
社区版块
存档分类
最新评论

【code】java栈和队列实现

Java 
阅读更多

顺序栈的实现

import java.util.Arrays;
public class SequenceStack<T>
{
	private int DEFAULT_SIZE = 10;
	//保存数组的长度。
	private int capacity;
	//定义当底层数组容量不够时，程序每次增加的数组长度
	private int capacityIncrement = 0;
	//定义一个数组用于保存顺序栈的元素
	private Object[] elementData;
	//保存顺序栈中元素的当前个数
	private int size = 0;
	//以默认数组长度创建空顺序栈
	public SequenceStack()
	{
		capacity = DEFAULT_SIZE;
		elementData = new Object[capacity];
	}
	//以一个初始化元素来创建顺序栈
	public SequenceStack(T element)
	{
		this();
		elementData[0] = element;
		size++;
	}
	/**
	 * 以指定长度的数组来创建顺序栈
	 * @param element 指定顺序栈中第一个元素
	 * @param initSize 指定顺序栈底层数组的长度
	 */
	public SequenceStack(T element , int initSize)
	{
		this.capacity = initSize;
		elementData = new Object[capacity];
		elementData[0] = element;
		size++;
	}
	/**
	 * 以指定长度的数组来创建顺序栈
	 * @param element 指定顺序栈中第一个元素
	 * @param initSize 指定顺序栈底层数组的长度
	 * @param capacityIncrement 指定当顺序栈底层数组的长度不够时，底层数组每次增加的长度
	 */
	public SequenceStack(T element , int initSize
		, int capacityIncrement)
	{
		this.capacity = initSize;
		this.capacityIncrement = capacityIncrement;
		elementData = new Object[capacity];
		elementData[0] = element;
		size++;
	}
	//获取顺序栈的大小
	public int length()
	{
		return size;
	}
	//入栈
	public void push(T element)
	{
		ensureCapacity(size + 1);
		elementData[size++] = element;
	}
	//很麻烦，而且性能很差
	private void ensureCapacity(int minCapacity)
	{
		//如果数组的原有长度小于目前所需的长度
		if (minCapacity > capacity)
		{
			if (capacityIncrement > 0)
			{
				while (capacity < minCapacity)
				{
					//不断地将capacity长度加capacityIncrement，
					//直到capacity大于minCapacity为止
					capacity += capacityIncrement;
				}
			}
			else
			{
				//不断地将capacity * 2，直到capacity大于minCapacity为止
				while (capacity < minCapacity)
				{
					capacity <<= 1;
				}
			}
			elementData = Arrays.copyOf(elementData , capacity);
		}
	}
	//出栈
    public T pop()
	{
		T oldValue = (T)elementData[size - 1];
		//释放栈顶元素
		elementData[--size] = null; 
		return oldValue;
	}
	//返回栈顶元素，但不删除栈顶元素
    public T peek()
	{
		return (T)elementData[size - 1];
	}
	//判断顺序栈是否为空栈
	public boolean empty()
	{
		return size == 0;
	}
	//清空顺序栈
	public void clear()
	{
		//将底层数组所有元素赋为null
		Arrays.fill(elementData , null);
		size = 0;
	}
	public String toString()
	{
		if (size == 0)
		{
			return "[]";
		}
		else
		{
			StringBuilder sb = new StringBuilder("[");
			for (int i = size - 1  ; i > -1 ; i-- )
			{
				sb.append(elementData[i].toString() + ", ");
			}
			int len = sb.length();
			return sb.delete(len - 2 , len).append("]").toString();
		}
	}
	
	public static void main(String[] args) 
	{
		SequenceStack<String> stack =
			new SequenceStack<String>();
		//不断地入栈
		stack.push("aaaa");
		stack.push("bbbb");
		stack.push("cccc");
		stack.push("dddd");
		System.out.println(stack);
		//访问栈顶元素
		System.out.println("访问栈顶元素：" + stack.peek());
		//弹出一个元素
		System.out.println("第一次弹出栈顶元素：" + stack.pop());
		//再次弹出一个元素
		System.out.println("第二次弹出栈顶元素：" + stack.pop());
		System.out.println("两次pop之后的栈：" + stack);
	}
}

 

链式栈的实现

 

public class LinkStack<T>
{
	//定义一个内部类Node，Node实例代表链栈的节点。
	private class Node
	{
		//保存节点的数据
		private T data;
		//指向下个节点的引用
		private Node next;
		//无参数的构造器
		public Node()
		{
		}
		//初始化全部属性的构造器
		public Node(T data , Node next)
		{
			this.data = data;
			this.next = next;
		}
	}
	//保存该链栈的栈顶元素
	private Node top;
	//保存该链栈中已包含的节点数
	private int size;
	//创建空链栈
	public LinkStack()
	{
		//空链栈，top的值为null
		top = null;
	}
	//以指定数据元素来创建链栈，该链栈只有一个元素
	public LinkStack(T element)
	{
		top = new Node(element , null);
		size++;
	}
	//返回链栈的长度	
	public int length()
	{
		return size;
	}
	//进栈
	public void push(T element)
	{
		//让top指向新创建的元素，新元素的next引用指向原来的栈顶元素
		top = new Node(element , top);
		size++;
	}
	//出栈
    public T pop()
	{
		Node oldTop = top;
		//让top引用指向原栈顶元素的下一个元素
		top = top.next;
		//释放原栈顶元素的next引用
		oldTop.next = null;
		size--;
		return oldTop.data;
	}
	//访问栈顶元素，但不删除栈顶元素
	public T peek()
	{
		return top.data;
	}
	//判断链栈是否为空栈
	public boolean empty()
	{
		return size == 0;
	}
	//清空链栈
	public void clear()
	{
		//将底层数组所有元素赋为null
		top = null;
		size = 0;
	}
	public String toString()
	{
		//链栈为空链栈时
		if (empty())
		{
			return "[]";
		}
		else
		{
			StringBuilder sb = new StringBuilder("[");
			for (Node current = top ; current != null
				; current = current.next )
			{
				sb.append(current.data.toString() + ", ");
			}
			int len = sb.length();
			return sb.delete(len - 2 , len).append("]").toString();
		}
	}
	
	public static void main(String[] args) 
	{
		LinkStack<String> stack =
			new LinkStack<String>();
		//不断地入栈
		stack.push("aaaa");
		stack.push("bbbb");
		stack.push("cccc");
		stack.push("dddd");
		System.out.println(stack);
		//访问栈顶元素
		System.out.println("访问栈顶元素：" + stack.peek());
		//弹出一个元素
		System.out.println("第一次弹出栈顶元素：" + stack.pop());
		//再次弹出一个元素
		System.out.println("第二次弹出栈顶元素：" + stack.pop());
		System.out.println("两次pop之后的栈：" + stack);
	}
}

 

顺序队列的实现

 

import java.util.Arrays;
public class SequenceQueue<T>
{
	private int DEFAULT_SIZE = 10;
	//保存数组的长度。
	private int capacity;
	//定义一个数组用于保存顺序队列的元素
	private Object[] elementData;
	//保存顺序队列中元素的当前个数
	private int front = 0;
	private int rear = 0;
	//以默认数组长度创建空顺序队列
	public SequenceQueue()
	{
		capacity = DEFAULT_SIZE;
		elementData = new Object[capacity];
	}
	//以一个初始化元素来创建顺序队列
	public SequenceQueue(T element)
	{
		this();
		elementData[0] = element;
		rear++;
	}
	/**
	 * 以指定长度的数组来创建顺序队列
	 * @param element 指定顺序队列中第一个元素
	 * @param initSize 指定顺序队列底层数组的长度
	 */
	public SequenceQueue(T element , int initSize)
	{
		this.capacity = initSize;
		elementData = new Object[capacity];
		elementData[0] = element;
		rear++;
	}
	//获取顺序队列的大小
	public int length()
	{
		return rear - front;
	}
	//插入队列
	public void add(T element)
	{
		if (rear > capacity - 1)
		{
			throw new IndexOutOfBoundsException("队列已满的异常");
		}
		elementData[rear++] = element;
	}
	//移除队列
    public T remove()
	{
		if (empty())
		{
			throw new IndexOutOfBoundsException("空队列异常");
		}
		//保留队列的rear端的元素的值
		T oldValue = (T)elementData[front];
		//释放队列的rear端的元素
		elementData[front++] = null; 
		return oldValue;
	}
	//返回队列顶元素，但不删除队列顶元素
    public T element()
	{
		if (empty())
		{
			throw new IndexOutOfBoundsException("空队列异常");
		}
		return (T)elementData[front];
	}
	//判断顺序队列是否为空队列
	public boolean empty()
	{
		return rear == front;
	}
	//清空顺序队列
	public void clear()
	{
		//将底层数组所有元素赋为null
		Arrays.fill(elementData , null);
		front = 0;
		rear = 0;
	}
	public String toString()
	{
		if (empty())
		{
			return "[]";
		}
		else
		{
			StringBuilder sb = new StringBuilder("[");
			for (int i = front  ; i < rear ; i++ )
			{
				sb.append(elementData[i].toString() + ", ");
			}
			int len = sb.length();
			return sb.delete(len - 2 , len).append("]").toString();
		}
	}
	public static void main(String[] args)
	{
		SequenceQueue<String> queue = new SequenceQueue<String>();
		//依次将4个元素加入队列
		queue.add("aaaa");
		queue.add("bbbb");
		queue.add("cccc");
		queue.add("dddd");
		System.out.println(queue);
		System.out.println("访问队列的front端元素:" 
			+ queue.element());
		System.out.println("移除队列的front端元素:" 
			+ queue.remove());
		System.out.println("移除队列的front端元素:" 
			+ queue.remove());
		System.out.println("两次调用remove方法后的队列：" 
			+ queue);

	}
}

 

循环队列的实现

 

import java.util.Arrays;
public class LoopQueue<T>
{
	private int DEFAULT_SIZE = 10;
	//保存数组的长度。
	private int capacity;
	//定义一个数组用于保存循环队列的元素
	private Object[] elementData;
	//保存循环队列中元素的当前个数
	private int front = 0;
	private int rear = 0;
	//以默认数组长度创建空循环队列
	public LoopQueue()
	{
		capacity = DEFAULT_SIZE;
		elementData = new Object[capacity];
	}
	//以一个初始化元素来创建循环队列
	public LoopQueue(T element)
	{
		this();
		elementData[0] = element;
		rear++;
	}
	/**
	 * 以指定长度的数组来创建循环队列
	 * @param element 指定循环队列中第一个元素
	 * @param initSize 指定循环队列底层数组的长度
	 */
	public LoopQueue(T element , int initSize)
	{
		this.capacity = initSize;
		elementData = new Object[capacity];
		elementData[0] = element;
		rear++;
	}
	//获取循环队列的大小
	public int length()
	{
		if (empty())
		{
			return 0;
		}
		return rear > front ? rear - front 
			: capacity - (front - rear);
	}
	//插入队列
	public void add(T element)
	{
		if (rear == front 
			&& elementData[front] != null)
		{
			throw new IndexOutOfBoundsException("队列已满的异常");
		}
		elementData[rear++] = element;
		//如果rear已经到头，那就转头
		rear = rear == capacity ? 0 : rear;
	}
	//移除队列
	public T remove()
	{
		if (empty())
		{
			throw new IndexOutOfBoundsException("空队列异常");
		}
		//保留队列的rear端的元素的值
		T oldValue = (T)elementData[front];
		//释放队列的rear端的元素
		elementData[front++] = null; 
		//如果front已经到头，那就转头
		front = front == capacity ? 0 : front;
		return oldValue;
	}
	//返回队列顶元素，但不删除队列顶元素
	public T element()
	{
		if (empty())
		{
			throw new IndexOutOfBoundsException("空队列异常");
		}
		return (T)elementData[front];
	}
	//判断循环队列是否为空队列
	public boolean empty()
	{
		//rear==front且rear处的元素为null
		return rear == front 
			&& elementData[rear] == null;
	}
	//清空循环队列
	public void clear()
	{
		//将底层数组所有元素赋为null
		Arrays.fill(elementData , null);
		front = 0;
		rear = 0;
	}
	public String toString()
	{
		if (empty())
		{
			return "[]";
		}
		else
		{
			//如果front < rear，有效元素就是front到rear之间的元素
			if (front < rear)
			{
				StringBuilder sb = new StringBuilder("[");
				for (int i = front  ; i < rear ; i++ )
				{
					sb.append(elementData[i].toString() + ", ");
				}
				int len = sb.length();
				return sb.delete(len - 2 , len).append("]").toString();
			}
			//如果front >= rear，有效元素为front->capacity之间、0->front之间的
			else
			{
				StringBuilder sb = new StringBuilder("[");
				for (int i = front  ; i < capacity ; i++ )
				{
					sb.append(elementData[i].toString() + ", ");
				}
				for (int i = 0 ; i < rear ; i++)
				{
					sb.append(elementData[i].toString() + ", ");
				}
				int len = sb.length();
				return sb.delete(len - 2 , len).append("]").toString();
			}
		}
	}
	public static void main(String[] args)
	{
		LoopQueue<String> queue 
			= new LoopQueue<String>("aaaa" , 3);
		//添加两个元素
		queue.add("bbbb");
		queue.add("cccc");
		//此时队列已满
		System.out.println(queue);
		//删除一个元素后，队列可以再多加一个元素
		queue.remove();
		System.out.println("删除一个元素后的队列：" + queue);
		//再次添加一个元素，此时队列又满
		queue.add("dddd");
		System.out.println(queue);
		System.out.println("队列满时的长度：" + queue.length());
		//删除一个元素后，队列可以再多加一个元素
		queue.remove();
		//再次加入一个元素，此时队列又满
		queue.add("eeee");
		System.out.println(queue);
	}
}

 链式队列的实现

 

public class LinkQueue<T>
{
	//定义一个内部类Node，Node实例代表链队列的节点。
	private class Node
	{
		//保存节点的数据
		private T data;
		//指向下个节点的引用
		private Node next;
		//无参数的构造器
		public Node()
		{
		}
		//初始化全部属性的构造器
		public Node(T data ,  Node next)
		{
			this.data = data;
			this.next = next;
		}
	}
	//保存该链队列的头节点
	private Node front;
	//保存该链队列的尾节点
	private Node rear;
	//保存该链队列中已包含的节点数
	private int size;
	//创建空链队列
	public LinkQueue()
	{
		//空链队列，front和rear都是null
		front = null;
		rear = null;
	}
	//以指定数据元素来创建链队列，该链队列只有一个元素
	public LinkQueue(T element)
	{
		front = new Node(element , null);
		//只有一个节点，front、rear都指向该节点
		rear = front;
		size++;
	}
	//返回链队列的长度	
	public int length()
	{
		return size;
	}
	//将新元素加入队列
	public void add(T element)
	{
		//如果该链队列还是空链队列
		if (front == null)
		{
			front = new Node(element , null);
			//只有一个节点，front、rear都指向该节点
			rear = front;
		}
		else
		{
			//创建新节点
			Node newNode = new Node(element , null);
			//让尾节点的next指向新增的节点
			rear.next = newNode;
			//以新节点作为新的尾节点
			rear = newNode;
		}
		size++;
	}
	//删除队列front端的元素
	public T remove()
	{
		Node oldFront = front;
		front = front.next;
		oldFront.next = null;
		size--;
		return oldFront.data;
	}
	//访问链式队列中最后一个元素
	public T element()
	{
		return rear.data;
	}
	//判断链式队列是否为空队列
	public boolean empty()
	{
		return size == 0;
	}
	//清空链队列
	public void clear()
	{
		//将front、rear两个节点赋为null
		front = null;
		rear = null;
		size = 0;
	}
	public String toString()
	{
		//链队列为空链队列时
		if (empty())
		{
			return "[]";
		}
		else
		{
			StringBuilder sb = new StringBuilder("[");
			for (Node current = front ; current != null
				; current = current.next )
			{
				sb.append(current.data.toString() + ", ");
			}
			int len = sb.length();
			return sb.delete(len - 2 , len).append("]").toString();
		}
	}
	
	public static void main(String[] args) 
	{
		LinkQueue<String> queue 
			= new LinkQueue<String>("aaaa");
		//添加两个元素
		queue.add("bbbb");
		queue.add("cccc");
		System.out.println(queue);
		//删除一个元素后
		queue.remove();
		System.out.println("删除一个元素后的队列：" + queue);
		//再次添加一个元素
		queue.add("dddd");
		System.out.println("再次添加元素后的队列：" + queue);
		//删除一个元素后，队列可以再多加一个元素
		queue.remove();
		//再次加入一个元素
		queue.add("eeee");
		System.out.println(queue);
	}
}
  • 大小: 39.5 KB
  • 大小: 47.2 KB
分享到：
| 【code】java线性表实现
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    Java消息队列的简单实现代码

    在本文中，我们将实现一个简单的 Java 消息队列，使用 LinkedList 进行封装和实现。首先，我们定义一个栈类 MyStack，使用 LinkedList 存储元素，并提供 push、peek、pop 和 empty 等方法。 ```java public class ...

    java 数据结构code

    Java作为一种面向对象的语言，提供了多种内置数据结构，如数组、链表、栈、队列、集合、映射等，同时允许程序员自定义复杂的数据结构。 【描述】：“english version much code”表明这些代码可能是英文注释或说明...

    java算法练习代码code

    在Java中，我们可以使用各种数据结构（如数组、链表、栈、队列、树和图等）来辅助实现这些算法。 1. **排序算法**：Java代码可能会包含常见的排序算法，如冒泡排序、插入排序、选择排序、快速排序、归并排序和堆...

    队和栈类的封装

    `code_第四章`可能包含了使用某种编程语言（如C++、Java或Python）实现的队列和栈类的源代码。这些代码会展示如何创建类结构、定义成员变量以及实现上述的基本操作。 6. **性能分析**： - 栈和队列的时间复杂度...

    JAVA-GAME-SOURCE-CODE.rar_Java Game code

    "JAVA-GAME-SOURCE-CODE.rar" 提供了一个很好的学习资源，让初学者可以通过实际的代码来理解Java编程和游戏开发的基础知识。下面将详细探讨这个压缩包中可能包含的内容及其相关知识点。 1. **基础Java语法**：源...

    data structures with java source code

    Java的递归和队列可以用来实现这些算法。 本资料集中的"ch01"到"ch15"章节可能涵盖这些数据结构及其在Java中的实现，包括源代码示例，是学习和实践Java数据结构的理想资源。通过逐步阅读和实践，读者能够加深对数据...

    Classic-java-game-source-code.zip_JAVA小游戏

    - **数据结构和算法**：如数组、链表、栈和队列的应用，以及排序和查找算法。 - **事件处理和回调**：理解如何监听用户操作并做出相应。 - **错误处理和调试**：学习如何使用try-catch语句处理异常，并通过日志或...

    Java软件结构 设计和使用数据结构

    "ch06 Code"和"ch10 Code"可能涵盖了队列和堆的概念。队列是先进先出（FIFO）的数据结构，适用于任务调度和消息传递。堆是一种特殊的树形数据结构，常用于优先级队列的实现，可以快速找到最大或最小的元素。 在...

    Java-How to program 9th edition source code

    4. **数据结构**：数组、链表、栈、队列、树和图等数据结构在解决复杂问题时扮演着重要角色。书中可能有对应的实现和使用示例。 5. **输入/输出**：Java的IO流系统允许程序读取和写入文件，进行网络通信等。学习...

    java_code_of_algorithms.rar_MST code_dfs java_mst

    在给定的“java_code_of_algorithms.rar”压缩包中，包含了多个Java代码实现的数据结构和算法，重点涉及了最小生成树（Minimum Spanning Tree, MST）、深度优先搜索（Depth First Search, DFS）以及其他的排序算法。...

    PL/0编译器（java实现）

    通过阅读和理解这些代码，开发者可以深入学习编译器的工作原理，同时掌握Java编程技巧，例如处理字符串、构建数据结构（如栈和队列）、以及使用递归等。 此外，该项目还可以作为教育工具，帮助学生进行编译原理的...

    java实战项目code部分（15个项目）

    在本资源"java实战项目code部分（15个项目）"中，您将获得一系列Java编程的实际应用案例，这些案例涵盖了不同的领域和功能，旨在帮助Java开发者提升实战技能和项目经验。15个项目的代码提供了丰富的学习材料，让我们...

    Java 集成开发实例精解 Sour code1

    8. **数据结构与算法**：理解并熟练运用数组、链表、栈、队列、树等数据结构，以及排序、查找等基础算法，能有效提高代码效率。 9. **日志管理**：如Log4j、Logback等，用于记录程序运行过程中的信息，便于调试和...

    大二java 的卡内基课程SSD3所有作业答案

    2. 数据结构与算法：Java提供了丰富的内置数据结构，如数组、链表、栈、队列、树等。学习如何选择合适的数据结构以及编写高效的算法是Java学习的重要部分。 3. 异常处理：Java中的异常处理是程序健壮性的重要组成...

    数据结构与问题分析 java 源代码

    `Evaluator.java`可能涉及到表达式求值或解析，这需要理解和使用栈或队列等数据结构。 3. **实用工具**：`wutil.jar`和`wnonstandard.jar`很可能是包含通用工具函数和类的库，比如字符串处理、数学运算、I/O操作等...

    词法分析器和语法分析器java实现代码---

    3. **标记管理**：存储和管理生成的标记，通常是通过一个队列或栈来实现。 4. **语法规则**：定义源代码的语法规则，这通常以文法的形式表示。 5. **解析**：根据语法规则，语法分析器将标记转换为AST，这个过程可能...

    chatting-code-made-by-java.rar_made

    5. **数据结构和算法**：为了存储和管理聊天记录，开发者可能使用链表、队列、栈等数据结构，以及搜索、排序等算法。 6. **数据序列化**：如果需要将聊天记录持久化存储，Java的序列化机制可以将对象转化为可存储或...

    Cracking-the-code-interview-solution-java.rar_The Interview_crac

    CtCI涵盖了各种常见数据结构，如数组、链表、栈、队列、树（二叉树、平衡树如AVL和红黑树）、图等。理解它们的特性、操作时间复杂度以及如何在实际问题中应用是关键。例如，链表操作可以用于实现LRU缓存，二叉树可以...

    LLK_JAVA源码_

    - **数据结构和算法**：游戏逻辑可能涉及链表、队列、栈、图等数据结构，以及搜索、排序等算法。 通过对这个项目的源码进行研究，开发者可以学习如何在Java和Android环境中创建游戏，包括UI设计、游戏逻辑实现、...

    thinking in java 代码

    8. **容器与算法**：书中可能包含了一些基本的数据结构和算法实现，如栈、队列、排序和搜索等。 9. **异常处理**：学习如何使用try-catch-finally语句来捕获和处理运行时错误，以及如何自定义异常。 10. **网络...

Magicbox
Global site tag (gtag.js) - Google Analytics