如果让你手写个栈和队列，你还会写吗？

阅读本文大概需要6分钟

昨天跟一个CSDN上的朋友聊天，他说现在如果让他自己手写一个栈或者队列，估计都要写蛮久的，平时虽然都在用，但是都是别人封装好的集合。

确实，经典的数据结构，包括排序算法，虽然我们平时不用手写了，但是这些内功，作为开发人员来说是必须要掌握的。受此启发，我打算更一下经典数据结构和算法的系列文章。今天先从栈和队列说起。

这些东西，挤地铁时，吃饭排队时，等公交时，可以拿来看看，或者，就把它当作个下午茶吧~

我们知道，在数组中，若知道数据项的下标，便可立即访问该数据项，或者通过顺序搜索数据项，访问到数组中的各个数据项。但是栈和队列不同，它们的访问是受限制的，即在特定时刻只有一个数据项可以被读取或者被删除。众所周知，栈是先进后出，只能访问栈顶的数据，队列是先进先出，只能访问头部数据。这里不再赘述。

栈的主要机制可以用数组来实现，也可以用链表来实现，下面用数组来实现栈的基本操作：

1. class ArrayStack {

2.    private long[] a;

3.    private int size; //栈数组的大小

4.    private int top; //栈顶

5.    public ArrayStack(int maxSize) {

6.        this.size = maxSize;

7.        this.a = new long[size];

8.        this.top = -1; //表示空栈

9.    }

10.    public void push(long value) {//入栈

11.        if(isFull()) {

12.            System.out.println("栈已满！");

13.            return;

14.        }

15.        a[++top] = value;

16.    }

17.    public long peek() {//返回栈顶内容，但不删除

18.        if(isEmpty()) {

19.            System.out.println("栈中没有数据");

20.            return 0;

21.        }

22.        return a[top];

23.    }

24.    public long pop() { //弹出栈顶内容，删除

25.        if(isEmpty()) {

26.            System.out.println("栈中没有数据！");

27.            return 0;

28.        }

29.        return a[top--];        

30.    }

31.    public int size() {

32.        return top + 1;

33.    }

34.    public boolean isEmpty() {

35.        return (top == -1);

36.    }

37.    public boolean isFull() {

38.        return (top == size -1);

39.    }

40.    public void display() {

41.        for(int i = top; i >= 0; i--) {

42.            System.out.print(a[i] + " ");

43.        }

44.        System.out.println("");

45.    }

46. }

数据项入栈和出栈的时间复杂度均为O(1)。这也就是说，栈操作所消耗的时间不依赖于栈中数据项的个数，因此操作时间很短。栈不需要比较和移动操作。

队列也可以用数组来实现，不过这里有个问题，当数组下标满了后就不能再添加了，但是数组前面由于已经删除队列头的数据了，导致空。所以队列我们可以用循环数组来实现，见下面的代码：

1. public class RoundQueue {

2.    private long[] a;

3.    private int size;   //数组大小

4.    private int nItems; //实际存储数量

5.    private int front;  //头

6.    private int rear;   //尾

7.    public RoundQueue(int maxSize) {

8.        this.size = maxSize;

9.        a = new long[size];

10.        front = 0;

11.        rear = -1;

12.        nItems = 0;

13.    }

14.    public void insert(long value) {

15.        if(isFull()){

16.            System.out.println("队列已满");

17.            return;

18.        }

19.        rear = ++rear % size;

20.        a[rear] = value; //尾指针满了就循环到0处,这句相当于下面注释内容      

21.        nItems++;

22. /*        if(rear == size-1){

23.            rear = -1;

24.        }

25.        a[++rear] = value;

26. */

27.    }

28.    public long remove() {

29.        if(isEmpty()) {

30.            System.out.println("队列为空！");

31.            return 0;

32.        }

33.        nItems--;

34.        front = front % size;

35.        return a[front++];

36.    }

37.    public void display() {

38.        if(isEmpty()) {

39.            System.out.println("队列为空！");

40.            return;

41.        }

42.        int item = front;

43.        for(int i = 0; i < nItems; i++) {

44.            System.out.print(a[item++ % size] + " ");

45.        }

46.        System.out.println("");

47.    }

48.    public long peek() {

49.        if(isEmpty()) {

50.            System.out.println("队列为空！");

51.            return 0;

52.        }

53.        return a[front];

54.    }

55.    public boolean isFull() {

56.        return (nItems == size);

57.    }

58.    public boolean isEmpty() {

59.        return (nItems == 0);

60.    }

61.    public int size() {

62.        return nItems;

63.    }

64. }

和栈一样，队列中插入数据项和删除数据项的时间复杂度均为O(1)。

还有个优先级队列，优先级队列是比栈和队列更专用的数据结构。优先级队列与上面普通的队列相比，主要区别在于队列中的元素是有序的，关键字最小（或者最大）的数据项总在队头。数据项插入的时候会按照顺序插入到合适的位置以确保队列的顺序。优先级队列的内部实现可以用数组或者一种特别的树——堆来实现。

1. public class PriorityQueue {

2.    private long[] a;

3.    private int size;

4.    private int nItems;//元素个数

5.    public PriorityQueue(int maxSize) {

6.        size = maxSize;

7.        nItems = 0;

8.        a = new long[size];

9.    }

10.    public void insert(long value) {

11.        if(isFull()){

12.            System.out.println("队列已满！");

13.            return;

14.        }

15.        int j;

16.        if(nItems == 0) { //空队列直接添加

17.            a[nItems++] = value;

18.        }

19.        else{//将数组中的数字依照下标按照从大到小排列

20.            for(j = nItems-1; j >= 0; j--) {

21.                if(value > a[j]){

22.                    a[j+1] = a[j];

23.                }

24.                else {

25.                    break;

26.                }

27.            }

28.            a[j+1] = value;

29.            nItems++;

30.        }

31.    }

32.    public long remove() {

33.        if(isEmpty()){

34.            System.out.println("队列为空！");

35.            return 0;

36.        }

37.        return a[--nItems];

38.    }

39.    public long peekMin() {

40.        return a[nItems-1];

41.    }

42.    public boolean isFull() {

43.        return (nItems == size);

44.    }

45.    public boolean isEmpty() {

46.        return (nItems == 0);

47.    }

48.    public int size() {

49.        return nItems;

50.    }

51.    public void display() {

52.        for(int i = nItems-1; i >= 0; i--) {

53.            System.out.print(a[i] + " ");

54.        }

55.        System.out.println(" ");

56.    }

57. }

这里实现的优先级队列中，插入操作需要 O(N) 的时间，而删除操作则需要 O(1) 的时间。

程序员私房菜，这里不仅仅有技术