本文主要讲栈和队列的实现方法,所以仅简单介绍栈和队列的概念,如果有疑问可以去查有关栈和队列的详细资料。
栈 Stack(LIFO线性表):
栈是一种特殊的线性表,满足后进先出,它限定仅可以在表尾进行删除和增加。push(), pop(), peek(),empty()是它的三个重要的方法。push()是往栈里压入一个元素;pop()是弹出栈顶元素,栈顶指针指向下一个元素;peek()是返回栈顶元素,但不删除栈顶元素;empty是判断栈是否为空。
队列 Queue(FIFO线性表):
队列也是一种特殊的线性表,与栈的规则相反,它满足先进先出原则,它限定只能在表尾添加元素,在表头删除元素。它的基本操作有offer(),poll(),peek()。offer()为在表尾添加一个元素,poll()为在表头删除一个元素,peek()为得到表头的元素,但不删除此元素。对于队列对应的还有三个操作 add(),remove(),element(),这三个操作可以完成相同的功能,但是如果后者操作失败会抛出异常,而前者返回具体的值(null,false等,要看具体的操作)。
***
不过请大家记住一点,不是所有的队列都是FIFO,比如优先队列,它是根据各元素的优先级来决定顺序的。
了解了栈和队列的基本操作,下面我们学习它们的具体实现。
1. Stack类的实现
JDK中写道,Stack类是继承了Vector类, Vector类在java中可以实现自动增长的动态数组。在这里我们用一个普通的对象数组来实现Stack类。代码如下:
public class Stack {
private int top;
private Object[] data;
//初始化堆栈
public Stack(int size){
data = new Object[size];
top = -1;
}
public boolean empty(){
return top == -1;
}
public void push(Object object) {
if(top == data.length-1){
System.out.println("栈满");
}
data[++top] = object;
}
public Object pop() {
if(top == -1){
System.out.println("栈空");
return null;
}
return data[top--];
}
public Object peek() {
if(data == null || data.length == 0)
return null;
return data[data.length-1];
}
}
这是堆栈最基本的实现,可能面试中可能会遇到其他问题,比如实现一个动态堆栈,当然在JDK中用vector类实现的堆栈本身就是动态堆栈,因为vector类可以实现可变长数组。对于普通对象数组长度是不可变的,上面的代码仅仅实现了一个固定长度的堆栈,如需改成动态堆栈,我们只需要改进push()方法,其他方法保持一致。改进后的push()方法:
public void push(Object object) {
if(top == data.length-1){
Object temp[] = new Object[data.length * 2]; // 把数组的容量增加一倍
for(int i=0; i<data.length; i++) temp[i] = data[i];
data = temp;
data[++top] = object;
}
data[++top] = object;
}
我们还可以用链表来实现堆栈,代码如下:
//首先定义一个链表类
class ListNode{
Object object;
ListNode next;
ListNode(Object object){
this.object = object;
}
}
public class Stack {
ListNode head;
public void push(Object object) {
ListNode node = new ListNode(object);
node.next = head;
head = node;
}
public Object pop() {
if(head != null) {
Object element = head.object;
head = head.next;
return element;
}
return null;
}
public Object peek() {
return head.object;
}
public boolean empty() {
return head == null;
}
}
2. 队列的实现
首先我们要搞清楚,队列是接口不是类,它不可以实例化,也就是不可以new queue(),接口的使用必须依赖于实现它的类,对于接口的引用,采用的是实例化实现该接口的类。下面我们用链表来实现一个队列。
class ListNode{
Object object;
ListNode next;
ListNode(Object object){
this.object = object;
}
}
public class QueueDemo {
ListNode head;
ListNode tail;
public void offer(Object object) {
if(head == null){
tail = new ListNode(object);
head = tail;
} else {
tail.next = new ListNode(object);
tail=tail.next;
}
}
public Object poll() {
if(head != null) {
Object element = head.object;
head = head.next;
if(head == null) tail = null;
return element;
}
return null;
}
public Object peek() {
if(head == null)
return null;
return head.object;
}
}
总结:我们用数组实现了固定长度的堆栈和动态堆栈,然后用链表分别实现了堆栈和队列。堆栈和队列之间也可以相互实现,只要记住队列是先进先出,只可以在队尾添加元素,在对头删除元素;堆栈是后进先出,只可以在表尾添加或删除元素。
以上只是个人总结,希望朋友们多多交流,共同进步!
分享到:
相关推荐
用栈和队列实现停车场管理,以栈模拟停车场,以队列模拟车场外的便道。
利用C++栈和队列实现回文判断 可以自行输入
运用栈和队列实现魔王语言 英文字母对应转换成中文意思
实现魔王语言的解释,输入一段魔王语言,使用栈和队列实现其翻译。有利于学习栈和队列的使用方法顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶
主要介绍了C语言用栈和队列实现的回文检测功能,结合具体实例形式分析了C语言栈和队列的定义及使用栈和队列进行回文检测的操作技巧,需要的朋友可以参考下
用栈和队列实现数据结构课程实验中要求的停车场程序
用栈和队列实现的c语言停车场 数据结构停车场 车进站出站查询
1.项目代码功能经验证ok,确保稳定可靠运行。欢迎下载使用!在使用过程中,如有问题或建议,请及时私信沟通,帮助解答。...C++开发基于栈和队列实现的电梯模拟程序源码+exe可执行程序+详细注释+项目说明.zip
利用栈和队列实现后缀表达式转中缀表达式,win32+vs2013实现
本表达式求值代码是用栈和队列实现,浮点数可以参加运算
利用栈和队列实现的计算器的C语言 通过测试
数据结构栈和队列的课程指导上几实验代码 相抵部分
通过栈和队列两种不同的方法来实现迷宫问题,队列方法求出的迷宫路径是最短路径
分别用栈和队列实现走迷宫的算法,电子工业出版社,叶核亚版的数据结构(java)课后习题,希望对大家有用。
使用栈和队列实现: 设停车场内只有一个可停放n辆汽车的狭长通道,且只有一个大门可供汽车进出;汽车在停车场内按车辆到达时间的先后顺序,依次由北向南排列(大门在最南端,最先到达的第一辆车停放在车场的最北端...
栈实现 队列实现 双栈实现队列 双队列实现栈 栈实现O(n)求当前栈最大值 http://blog.csdn.net/ssuchange/article/details/17398007
栈和队列的基本操作及其应用 1、掌握栈和队列的顺序存储结构和链式存储结构,以便在实际中灵活应用。...3、掌握栈和队列的基本运算,如:入栈与出栈,入队与出队等运算在顺序存储结构和链式存储结构上的实现。 回文判断
1、熟练掌握栈和队列的基本操作在两种存储结构上的实现。 2、会用栈和队列解决简单的实际问题。 二、实验内容 题目:试写一个算法,判断依次读入的一个以@为结束符的字符序列,是否为回文。所谓“回文“是指正向读...
C++语言实现带小数的任意进制转换,使用了数据结构中的栈和队列,在VC++6.0上编译运行通过。对于学习C++和数据结构有一定的参考意义!
数据结构P50.改栈用来队列实现迷宫。输出从开始到终点的路径。 绝对原创。