前面讲到了如何用数组以及链表实现一个基本的堆栈和队列,这篇文章介绍如何实现一个可以在O(1)时间复杂度下得到最小元素的堆栈,以及用堆栈实现一个队列,用队列实现一个堆栈。
1,实现一个可以得到最小元素的堆栈, 要求pop(),push(),getMin()的时间复杂度都为O(1).
如果我们按照普通的思路,类中有两个成员变量,value和minValue,当pop一个元素后,我们就需要更新minValue, 从而要遍历堆栈里剩余的元素,时间复杂度为O(n),假设堆栈中有n个元素,因此这个方法不符合题意。
我们想到用每个元素都记录当前的最小元素,当push一个新的元素进来,这个新的元素连同最小元素都被记录在堆栈中,我们先不考虑pop,实现代码如下:
public class StackWithMin extends Stack<EleWithMin>{
public void push(int val) {
int min = Math.min(val, min());
super.push(new EleWithMin(val, min));
}
public int pop() {
/*
after we pop a element,
how can we update the min in
stack if this is the minimum value
*/
super.pop().value;
}
public int min(){
if(this.isEmpty()){
return Integer.MAX_VALUE;
} else {
return peek().min;
}
}
}
class EleWithMin {
public int value;
public int min;
public EleWithMin(int value, int min) {
this.value = value;
this.min = min;
}
}
他的确可以在O(1)的时间内得到最小元素,但是pop后,我们仍然需要更新最小值,时间复杂度大于O(n)。并且浪费空间,因为每个元素都要记录一个当前的最小元素。我们换另一种方法,用另外一个堆栈来记录最小元素。代码如下:
import java.util.Stack;
public class StackWithMin extends Stack<Integer> {
Stack<Integer> minStack;
public StackWithMin() {
minStack = new Stack<Integer>();
}
public void push(int val) {
super.push(val);
if(minStack.isEmpty() || minStack.peek() >= getMin()){
minStack.push(val);
}
}
public Integer pop(){
int value = super.pop();
if(value == getMin()){
minStack.pop();
}
return value;
}
public int getMin() {
if(minStack.isEmpty()) {
return Integer.MAX_VALUE;
} else {
return minStack.peek();
}
}
}
2,用队列实现一个堆栈
借用两个队列,实现堆栈后进先出的原理。代码如下:
import java.util.LinkedList;
import java.util.Queue;
public class MyStack {
Queue<Integer> q1 = new LinkedList<Integer>();
Queue<Integer> q2 = new LinkedList<Integer>();
public void push(int val) {
q1.offer(val);
}
public int pop() {
while(q1.size() > 1) q2.offer(q1.poll());
int result = q1.poll();
Queue<Integer> q = q1;
q1 = q2;
q2 = q1;
return result;
}
public int peek() {
while(q1.size() > 1) q2.offer(q1.poll());
int result = q1.poll();
q2.offer(result);
Queue<Integer> q = q1;
q1 = q2;
q2 = q;
return result;
}
public boolean isEmpty() {
if(q1.size() == 0) {
return true;
} else {
return false;
}
}
}
3,用堆栈实现队列
思路和上一题类似,这里用两个堆栈来实现队列先进先出的原理。代码如下:
import java.util.Stack;
public class MyQueue {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void offer(int val) {
stack1.push(val);
}
public int element() {
while(!stack1.isEmpty())
stack2.push(stack1.pop());
int result = stack2.pop(); //删除第一个元素
while(!stack2.isEmpty())
stack1.push(stack2.pop());
return result;
}
public int peek() {
while(!stack1.isEmpty())
stack2.push(stack1.pop());
int result = stack2.peek(); //不删除第一个的元素
while(!stack2.isEmpty())
stack1.push(stack2.pop());
return result;
}
public boolean empty() {
if(stack1.isEmpty())
return true;
return false;
}
}
分享到:
相关推荐
用链表实现栈和队列的操作,使链表操作更加成熟,熟练栈和队列的机制
PPT内容是数据结构中有关栈和队列的知识,非常适合正在学习数据结构基础的同学
把堆栈和队列的顺序存储(环队)和链表存储的数据进队、出队等运算其中一部分进行程序实现。可以实验一的结果自己实现数据输入、数据显示的函数。
栈和队列的基本操作实现及其应用(报告),这是我们学习数据结构的时候老师给的实验我写的实验报告,给大家参考一下!
内容和要求 单链表操作 和 栈、队列的... 4)定义一个顺序栈和循环队列,实现将队列中所有元素逆置。 实验数据:1)线性表为 6,2,11,5,2,4,2; 2)x=2; 3) k=5 或 k=10; 4)队列中的数据为 1,2,3,4,5,6
利用栈和队列实现的计算器的C语言 通过测试
东北大学数据结构课程实验2栈和队列,实验报告,有代码。
将近下课,体育老师一吹口哨大家立即集合,不过这次集合大家都站成了一排,然后老师说向右看齐,这时每个人只能看到右侧比自己矮的人头,如果突然出现一个高于或等于自己身高的同学,那么这名同学以及其右侧的同学将...
运用栈和队列设计一个表达式的求值,C++编写
数据结构实验:堆栈与队列; 包括3个代码和实验报告: 括号匹配完成、 利用栈队列逆置 、栈的操作
只用堆栈实现队列只用堆栈实现队列只用堆栈实现队列
使用栈和队列实现: 设停车场内只有一个可停放n辆汽车的狭长通道,且只有一个大门可供汽车进出;汽车在停车场内按车辆到达时间的先后顺序,依次由北向南排列(大门在最南端,最先到达的第一辆车停放在车场的最北端...
堆栈和队列基本操作的编程实现(2学时,验证型),掌握堆栈和队列的建立、进栈、出栈、进队、出队等基本操作的编程实现,存储结构可以在顺序结构或链接结构中任选,也可以全部实现。也鼓励学生利用基本操作进行一些...
用栈实现队列逆序输出,C语言代码,VC++编译器!
栈和队列的C++实现,采用类封装,包含基本队列的栈的操作,内含.h和.cpp实现文件。可重复使用。 栈和队列是一起的,兼顾两者的算法
栈(stack)又名堆栈,它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶,相对地,把另一端称为栈底。
该文件包括堆栈的头文件(Seq开头)和链表的头文件(Lin开头),另外还实现了十进制转化为八进制、对称串判断和带头结点的单循环链表实现链式队列
顺序存储的线性表和运算 链式存储的线性表和运算 顺序栈的实现和运算 链栈的实现和运算 顺序队列的实现和运算 链式队列的实现和运算 循环队列的实现和运算
实验五 堆栈和队列的应用 一、实验目的 掌握堆栈和队列的使用。 二、实验内容 1、计算数学表达式的值。 输入数学表达式,输出表达式的计算结果。数学表达式由单个数字和运算符“+”、“-”、“*”、“/”、“(、...
本文实例讲述了C语言用栈和队列实现的回文功能。分享给大家供大家参考,具体如下: #include #include<malloc>//内存分配头文件 #include<math.h>//在math.h中已定义OVERFLOW的值为3 #define SIZE 100 #...