栈
栈只允许访问一个数据项：即最后插入的数据。溢出这个数据才能访问倒数第二个插入的数据项。它是一种"后进先出"的数据结构。
栈最基本的操作是出栈(Pop)、入栈(Push)，还有其他扩展操作，如查看栈顶元素，判断栈是否为空、是否已满，读取栈的大小等。
/**
* 栈是先进后出
* 只能访问栈顶的数据
* @author dream
*
*/
/**
* 基于数组来实现栈的基本操作
* 数据项入栈和出栈的时间复杂度均为O(1)
* @author dream
*
*/
public class ArrayStack {
private long[] a;
private int size; //栈数组的大小
private int top; //栈顶
public ArrayStack(int maxSize){
this.size = maxSize;
this.a = new long[size];
this.top = -1; //表示空栈
}
public void push(long value){ //入栈
if(isFull()){
System.out.println("栈已满!");
return;
}
a[++top] = value;
}
public long peek(){ //返回栈顶内容，但不删除
if(isEmpty()){
System.out.println("栈中没有数据");
return 0;
}
return a[top];
}
public long pop(){ //弹出栈顶内容
if(isEmpty()){
System.out.println("栈中没有数据!");
return 0;
}
return a[top--];
}
public int size(){
return top + 1;
}
/**
* 判断是否满了
* @return
*/
public boolean isFull(){
return (top == size - 1);
}
/**
* 是否为空
* @return
*/
public boolean isEmpty(){
return (top == -1);
}
public void display(){
for (int i = top; i >= 0; i--) {
System.out.println(a[i] + " ");
}
System.out.println("");
}
}
队列
依然使用数组作为底层容器来实现一个队列的封装
/**
* 队列也可以用数组来实现，不过这里有个问题，当数组下标满了后就不能再添加了，
* 但是数组前面由于已经删除队列头的数据了，导致空。所以队列我们可以用循环数组来实现，
* @author dream
*
*/
public class RoundQueue {
private long[] a;
private int size; //数组大小
private int nItems; //实际存储数量
private int front; //头
private int rear; //尾
public RoundQueue(int maxSize){
this.size = maxSize;
a = new long[size];
front = 0;
rear = -1;
nItems = 0;
}
public void insert(long value){
if(isFull()){
System.out.println("队列已满");
return;
}
rear = ++rear % size;
a[rear] = value; //尾指针满了就循环到0处，这句相当于下面注释内容
nItems++;
}
public long remove(){
if(isEmpty()){
System.out.println("队列为空!");
return 0;
}
nItems--;
front = front % size;
return a[front++];
}
public void display(){
if(isEmpty()){
System.out.println("队列为空!");
return;
}
int item = front;
for(int i = 0;i < nItems; i++){
System.out.println(a[item++ % size] + " ");
}
System.out.println("");
}
public long peek(){
if(isEmpty()){
System.out.println("队列为空！");
return 0;
}
return a[front];
}
public boolean isFull(){
return (nItems == size);
}
public boolean isEmpty(){
return (nItems == 0);
}
public int size(){
return nItems;
}
}
和栈一样，队列中插入数据项和删除数据项的时间复杂度均为O(1)
还有个优先级队列，优先级队列是比栈和队列更专用的数据结构。优先级队列与上面普通的队列相比，主要区别在于队列中的元素是有序的，关键字最小（或者最大）的数据项总在队头。数据项插入的时候会按照顺序插入到合适的位置以确保队列的顺序。优先级队列的内部实现可以用数组或者一种特别的树——堆来实现。这里用数组实现优先级队列。
public class PriorityQueue {
private long[] a;
private int size;
private int nItems; //元素个数
public PriorityQueue(int maxSize){
size = maxSize;
nItems = 0;
a = new long[size];
}
public void insert(long value){
if(isFull()){
System.out.println("队列已满！");
return;
}
int j;
if(nItems == 0){ //空队列直接添加
a[nItems++] = value;
}else {
//将数组中的数字依照下标按照从大到小排列
for(j=nItems-1; j>=0; j--){
if(value > a[j]){
a[j+1] = a[j];
}
else {
break;
}
}
a[j+1] = value;
nItems++;
}
}
public long remove(){
if(isFull()){
System.out.println("队列为空!");
return 0;
}
return a[--nItems];
}
public long peekMin(){
return a[nItems - 1];
}
public boolean isFull(){
return (nItems == size);
}
public boolean isEmpty(){
return (nItems == 0);
}
public int size(){
return nItems;
}
public void display(){
for(int i = nItems - 1;i >= 0; i--){
System.out.println(a[i] + " ");
}
System.out.println(" ");
}
}
优先级队列中，插入操作需要O(N)的时间，而删除操作则需要O(1)的时间。
网友评论