ITPub博客

首页 > 应用开发 > IT综合 > 栈与队列简介

栈与队列简介

原创 IT综合 作者:zmy爱吃炸鸡 时间:2020-11-07 11:32:36 0 删除 编辑
栈与队列和数组、链表、树这几种数据结构不太一样。栈与队列主要是做为程序员的工具来使用,它们主要做为构思算法的辅助工具,而不是完全的数据存储工具。
它们的生命周期比数组那些要短得多,在程序执行期间它们才会被创建,任务执行完就会被销毁。
一 栈
栈是一种只能在一端进行插入和删除数据的数据结构,这一端被称为栈顶(top)。其特点简单来讲就是先进后出。栈的主要机制可以用数组来实现,当然也可以用链表来实现。
用数组实现栈,并完成常用操作——出栈、入栈、查看元素(只能查看栈顶元素)、判断栈是否为空等操作。
public class StackTest {
private long[] arr;
// 栈顶
private int top;
public StackTest(){
    arr = new long[10];
    top = -1;
}
public StackTest(int maxsize){
    arr = new long[maxsize];
    top = -1;
}
/**
 * 添加数据
 * @param value
 */
public void push(int value){
    arr[++top] = value;
}
/**
 * 移除数据
 * @return
 */
public long pop() {
    return arr[top--];
}
/**
 * 查看数据
 * @return
 */
public long peek(){
    return arr[top];
}
public boolean isEmpty(){
    return top == -1;
}
/***
 * 判断是否满了
 * @return
 */
public boolean isFull(){
    return top == arr.length-1;
}
}
栈的所有操作复杂度都为O(1),栈的操作不依赖栈中元素大小,栈不需要移动和比较操作。
二 队列
队列的特点是先进先出。队列也是用数组来实现。
用数组实现队列,并完成常用操作——出队、入队、查看元素、判断队列是否为空等操作。
public class QueueTest {
private long[] arr;
// 有效数据的大小
private int elements;
// 队头
private int front;
// 队尾
private int end;
public QueueTest(){
    arr = new long[10];
    elements = 0;
    front = 0;
    end = -1;
}
public QueueTest(int maxsize){
    arr = new long[maxsize];
    elements = 0;
    front = 0;
    end = -1;
}
/**
 * 插入数据
 * @param value
 */
public void insert(long value){
    arr[++end] = value;
    elements++;
}
/**
 * 删除数据
 * @return
 */
public long remove(){
    elements--;
    return arr[front++];
}
/**
 * 查看数据,从对头查看
 * @return
 */
public long peek(){
    return arr[front];
}
/**
 * 判断是否为空
 * @return
 */
public boolean isEmpty(){
    return elements == 0;
}
public boolean isFull(){
    return elements == arr.length;
}
}
队列的插入、删除等操作的复杂度都为O(1)。
三 优先级队列
优先级队列和普通队列一样,也是一个队头,一个队尾,从队头移除元素,优先级队列中,数据项是有序的,这样插入数据的时候就会根据某种规则去比较,然后插入到队列合适的位置。因此,优先级队列插入的复杂度为O(N),删除和查看元素的复杂度为O(1)。
用数组实现优先级队列,并完成常用操作——出队、入队、查看元素、判断队列是否为空等操作。
public class FirstQueueTest {
private long[] arr;
// 有效数据的大小
private int elements;
// 队头
private int front;
// 队尾
private int end;
public FirstQueueTest(){
    arr = new long[10];
    elements = 0;
    front = 0;
    end = -1;
}
public FirstQueueTest(int maxsize){
    arr = new long[maxsize];
    elements = 0;
    front = 0;
    end = -1;
}
/**
 * 插入数据
 * @param value
 */
public void inser(long value){
    if(elements == 0){
        arr[++end] = value;
        elements++;
    }else{
        // 按某种规则进行比较,这里使用value的大小比较,按从小到大排序
        for(int i = elements-1;i>=0;i--){
            if(value<arr[i]){
                arr[i+1] = arr[i];
                arr[i] = value;
            }else{
                arr[i+1] = value;
                break;
            }
        }
        elements++;
        end++;
    }
}
/**
 * 删除数据
 * @return
 */
public long remove(){
    elements--;
    return arr[front++];
}
/**
 * 查看数据,从对头查看
 * @return
 */
public long peek(){
    return arr[front];
}
/**
 * 判断是否为空
 * @return
 */
public boolean isEmpty(){
    return elements == 0;
}
public boolean isFull(){
    return elements == arr.length;
}
}
四 总结
1.栈的特点是先进后出,栈只能查看栈顶的一个元素
2.队列的特点是先进先出,只能查看队头的一个元素
3.优先级队列插入一条元素,平均需要移动2/N个元素,因此插入的复杂度为O(N)
4.栈和队列,可以用数组实现,也可以用其他数据结构实现
栈和队列是为了完成某些工作,手动构造的数据结构


来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/69983768/viewspace-2732771/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论

注册时间:2020-09-14

  • 博文量
    32
  • 访问量
    13951