栈和队列
关于栈与队列
栈与队列是特殊的线性表。
访问，插入，删除等操作只能在栈顶进行；对于队列，元素只能从队尾插入，从队头删除和访问。
换句话说，栈和队列是有操作限制的线性表。
顺序存储的栈称为顺序栈；链式存储的栈称为链式栈。
基于数组实现栈
package com.company;
public class StackOperation<T> {
private T data[];
private int maxSize;
private int top;
//初始化栈
public StackOperation(int maxSize) {
this.maxSize=maxSize;
data=(T[])new Object[maxSize]; //泛型数组不能直接new创建，需要使用Object来创建
this.top=-1;
}
//判断栈是否为空
public boolean isEmpty() {
return (top==-1);
}
//判断栈是否已经满了
public boolean isFull() {
return (top==maxSize-1);
}
//压栈
public boolean push(T value) {
if(isFull()) {
return false;
}
top++;
data[top]=value;
return true;
}
//取出栈顶元素
public T pop() {
if(isEmpty()) {
return null;
}
T tmp=data[top];
data[top]=null;
top--;
return tmp;
}
//============测试代码============
public static void main(String[] args) {
StackOperation<String> stackOperation=new StackOperation<String>(10);
stackOperation.push("AAA");
stackOperation.push("BBB");
stackOperation.push("CCC");
stackOperation.push("DDD");
stackOperation.push("EEE");
stackOperation.push("XXX");
stackOperation.push("YYY");
stackOperation.push("ZZZ");
while(!stackOperation.isEmpty())
{
System.out.println(stackOperation.pop());
}
}
}基于链表实现栈
package com.company;
class Node<T>{
protected T data;//数据
private Node<T> next;//指向下一个节点的指针
//初始化链表
public Node(T data) {
this.data=data;
}
//获取下一个节点
public Node<T> getNext(){
return this.next;
}
//设置下一个节点
public void setNext(Node<T> n) {
this.next=n;
}
//获取节点数据
public T getData() {
return this.data;
}
//设置节点数据
public void setData(T d) {
this.data=d;
}
@Override
public String toString() {
return "Node{" +
"data=" + data +
", next=" + next +
'}';
}
}
public class NodeStack<T> {
private Node<T> top=null;//栈顶
public NodeStack() {
this.top=null;
}
//判断栈是否为空
public boolean isEmpty() {
if(top!=null) {
return false;
}
return true;
}
//压栈
public boolean push(T value) {
Node<T> node=new Node<T>(value);
node.setNext(top);
top=node;
return true;
}
//出栈
public T pop() {
if(top==null) {
return null;
}
T tmp=top.data;
top=top.getNext();
return tmp;
}
//取出栈顶的值
public T peek() {
if(isEmpty()) {
return null;
}
return top.data;
}
public static void main(String[] args) {
System.out.println("实例化一个栈：");
NodeStack<String> ns=new NodeStack<String>();
System.out.println("判断是否为空："+ns.isEmpty());
System.out.println();
System.out.println("开始压栈：");
ns.push("AAA");
ns.push("BBB");
ns.push("CCC");
ns.push("DDD");
System.out.println("判断是否为空："+ns.isEmpty());
System.out.println();
System.out.println("开始出栈：");
System.out.println(ns.pop());
System.out.println(ns.pop());
System.out.println(ns.pop());
System.out.println(ns.pop());
}
}基于数组实现队列
package com.company;
public class QueueOperation<T> {
private T data[];
private int front=0;//队列头
private int rear=0;//队列尾
private int size;//队列大小
public QueueOperation(int size) {
this.size = size;
data = (T[])new Object[size];
}
/**
* 是否为空队列
* @return
*/
public boolean isEmpty(){
return front == rear;
}
/**
* 入队
* @param value
*/
public void in(T value) throws Exception {
if(rear == size){
throw new Exception("队列已满异常");
}
data[rear ++] = value;
}
/**
* 出队
*/
public Object out() throws Exception {
if(isEmpty()){
throw new Exception("空队列异常");
}
T value = data[front];
data[front++] = null;
return value;
}
public static void main(String[] args) throws Exception {
QueueOperation<String> queueOperation= new QueueOperation<>(10);
queueOperation.in("AAA");
queueOperation.in("BBB");
queueOperation.in("CCC");
queueOperation.in("DDD");
queueOperation.in("EEE");
queueOperation.in("XXX");
queueOperation.in("YYY");
queueOperation.in("ZZZ");
while (!queueOperation.isEmpty())
{
System.out.println(queueOperation.out());
}
}
}基于链表实现队列
package com.company;
class Node<T> {
// 存储的数据
private T data;
// 下一个节点的引用
private Node<T> next;
public Node(T data) {
this.data = data;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public Node<T> getNext() {
return next;
}
public void setNext(Node<T> next) {
this.next = next;
}
}
public class LinkQueue<T> {
// 队头
private Node<T> front;
// 队尾
private Node<T> rear;
// 元素个数
private int size;
/**
* 初始化
*/
public LinkQueue() {
rear = front = null;
}
/**
* 入队
* @param data
*/
public void in(T data) {
Node<T> node = new Node<T>(data);
if (isEmputy()) {
front = rear = node;
} else {
rear.setNext(node);
rear = node;
}
size++;
}
/**
* 出队
*/
public T out() {
if (isEmputy()) {
throw new RuntimeException("队列为空");
}
Node<T> delete = front;
front = delete.getNext();
delete.setNext(null);;
size--;
if (size == 0) {
// 删除掉最后一个元素时，front值已经为null，但rear还是指向该节点，需要将rear置为null
// 最后一个结点front和rear两个引用都没指向它，帮助GC处理该节点对象
rear = front;
}
return (T) delete.getData();
}
/**
* 判断队列是否为空
* @return
*/
public boolean isEmputy() {
return (front == null && rear == null) ? true : false;
}
/**
* 获取队列的元素个数
* @return
*/
public int size() {
return this.size;
}
public static void main(String[] args) {
LinkQueue<String> linkQueue = new LinkQueue<>();
linkQueue.in("AAA");
linkQueue.in("BBB");
linkQueue.in("CCC");
linkQueue.in("DDD");
while (!linkQueue.isEmputy())
{
System.out.println(linkQueue.out());
}
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-10-08 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
相关产品与服务
对象存储
对象存储（Cloud Object Storage，COS）是由腾讯云推出的无目录层次结构、无数据格式限制，可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限，无需分区管理，适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。