数据结构与算法---栈和队列

数据结构与算法—栈和队列

栈：是限制在表的一端进行插入和删除运算的线性表。栈又称后进先出简称LIFO表
队列：也是一种运算受限的线性表。它只允许在标的一端进行插入，而在另一端进行删除。队列亦称先进先出FIFO表

1. 栈与队列的区别
（1）队列先进先出，栈先进后出。
（2）对插入和删除操作的”限定”。 栈是限定只能在表的一端进行插入和删除操作的线性表。 队列是限定只能在表的一端进行插入和在另一端进行删除操作的线性表。 从”数据结构”的角度看，它们都是线性结构，即数据元素之间的关系相同。但它们是完全不同的数据类型。除了它们各自的基本操作集不同外，主要区别是对插入和删除操作的”限定”。 栈和队列是在程序设计中被广泛使用的两种线性数据结构，它们的特点在于基本操作的特殊性，栈必须按”后进先出”的规则进行操作，而队列必须按”先进先出” 的规则进行操作。和线性表相比，它们的插入和删除操作受更多的约束和限定，故又称为限定性的线性表结构。
（3）遍历数据速度不同。栈只能从头部取数据 也就最先放入的需要遍历整个栈最后才能取出来，而且在遍历数据的时候还得为数据开辟临时空间，保持数据在遍历前的一致性队列怎不同，他基于地址指针进行遍历，而且可以从头或尾部开始遍历，但不能同时遍历，无需开辟临时空间，因为在遍历的过程中不影像数据结构，速度要快的多
2. 栈
栈的主要机制可以用数组来实现，也可以用链表来实现，下面用数组来实现栈的基本操作，代码如下：

public class ArrayStack {
    private Object[] array;
    private int topOfStack;
    private static final int DEFAULT_CAPACITY=10;
    //初始化实例变量
    public ArrayStack(){
        array=new Object[DEFAULT_CAPACITY];
        topOfStack=-1;
    }
    //判断是否为空栈
    public boolean isEmpty(){
        return topOfStack==-1;
    }
    //入栈
    public void push(Object x){
        //如果栈的容量不够，则扩展栈的容量
        if (topOfStack+1==array.length) {
            doubleArray();
        }
        array[++topOfStack]=x;
    }
    //出栈
    public Object pop() throws Exception{
        //如果栈为空，则抛出未找到异常
        if (isEmpty()) {
            throw new Exception("UnderFlowExcption");
        }
        return array[topOfStack--];
    }
    //查看栈顶元素
    public Object top() throws Exception{
        if (isEmpty()) {
            throw new Exception("UnderFlowExcption");
        }
        return array[topOfStack];
    }
    //容量扩展的实现方式
    private void doubleArray() {
        Object[] newArray=new Object[array.length*2+1];
        for (int i = 0; i < array.length; i++) {
            newArray[i]=array[i];
        }
        array=newArray;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

数据项入栈和出栈的时间复杂度均为O(1)。这也就是说，栈操作所消耗的时间不依赖于栈中数据项的个数，因此操作时间很短。栈不需要比较和移动操作。
3. 队列
队列也可以用数组来实现，不过这里有个问题，当数组下标满了后就不能再添加了，但是数组前面由于已经删除队列头的数据了，此时为空。所以队列我们可以用循环数组来实现，见下面的代码：

public class ArrayQueue {
    private Object[] a;
    private int size;   //数组大小
    private int nItems; //实际存储数量
    private int front;  //头
    private int rear;   //尾

    public ArrayQueue(int maxSize) {
        this.size = maxSize;
        a = new Object[size];
        front = 0;
        rear = -1;
        nItems = 0;
    }

    public void enqueue(Object obj) {
        if(isFull()){
            System.out.println("队列已满");
            return;
        }
        rear = ++rear % size;
        a[rear] = obj; //尾指针满了就循环到0处,这句相当于下面注释内容
        nItems++;
/*      if(rear == size-1){
            rear = -1;
        }
        a[++rear] = value;
*/
    }

    public Object delQueue() {
        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.print(a[item++ % size] + " ");
        }
        System.out.println("");
    }

    public Object 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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72