栈和队列

栈：

package com.nanjing.dataStruc;

/**
 * 后进先出（LIFO）,栈顶压入，栈顶压出，只允许访问最后一个插入的数据项，应用：单词逆序，分隔符匹配
 */
public class Stack {
    private int maxSize;
    private long[] stackArray;
    private int top;
    private int nItemes;

    public Stack(int s) {
        nItemes=0;
        maxSize = s;
        stackArray = new long[maxSize];
        top = -1;
    }

    public void push(long a) throws Exception {
        if (top >= maxSize-1)
            throw new Exception("Stack is full~");
        stackArray[++top] = a;
        nItemes++;
    }

    public long pop() {
        nItemes--;
        return stackArray[top--];

    }

    public long peek() {
        return stackArray[top];
    }

    public int getSize(){
        return nItemes;
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public boolean isFull() {
        return top == maxSize;
    }

    public static void main(String[] args) {
        Stack stack = new Stack(10);
        try {
            stack.push(23);
            stack.push(123);
            stack.push(4);
            stack.push(67);
            stack.push(45);
            stack.push(87);
            stack.push(65);
            stack.pop();
            System.out.println("一共"+stack.getSize()+"个元素");
            while (!stack.isEmpty()) {
                System.out.print(stack.pop() + "\t");
            }

        } catch (Exception e) {
            e.printStackTrace();
        } finally {
        }
    }
}

 

 

队列：

package com.nanjing.dataStruc;

/**
 * 先进先出（FIFO）,只允许访问第一个插入的数据项，可以在队尾插入数据，在队头移除数据，应用：解析算术表达式
 */
public class Queue {
    private long[] queueArray;
    private int tail;
    private int head;
    private int nItemes;
    private int maxSize;

    public Queue(int size) {
        queueArray = new long[size];
        maxSize = size;
        tail = 0;
        head = -1;
        nItemes = 0;
    }

    public void insert(long element) {
        if (head == maxSize - 1)
            throw new ArrayIndexOutOfBoundsException("队列越界,不能添加");
        queueArray[++head] = element;
        nItemes++;
    }

    public long remove() {
        if (tail == maxSize)
            throw new RuntimeException("队列越界,不能删除");
        long q = queueArray[tail++];
        nItemes--;
        return q;
    }

    public long getSize() {
        return nItemes;
    }

    public boolean isEmpty() {
        return nItemes == 0;
    }

    public boolean isFull() {
        return nItemes == maxSize;
    }

    public static void main(String[] args) {
        Queue queue = new Queue(10);
        queue.insert(23);
        queue.insert(54);
        queue.insert(76);
        queue.insert(87);
        queue.insert(65);
        queue.remove();
        queue.remove();
        queue.remove();
        queue.remove();
        queue.remove();


        queue.insert(878);
        queue.insert(455);
        queue.insert(343);
        while (!queue.isEmpty()) {
            System.out.println(queue.remove());
        }
    }
}

 

优先级队列：

package com.nanjing.dataStruc;

/**
 * 优先级队列，允许访问最小或者最大的数据项，可以有序的插入新数据项和移除关键字最小的数据项,最大的数据项先被处理
 */
public class PriorityQ {
    private long[] priArray;
    private int maxSize;
    private int nItemes;

    public PriorityQ(int maxSize) {
        this.priArray = new long[maxSize];
        this.maxSize = maxSize;
        nItemes = 0;
    }

    public void insert(long data) {
        int j;
        if (nItemes == 0) {
            priArray[nItemes++] = data;
        } else {
            for (j = nItemes - 1; j >= 0; j--) {
                if (data < priArray[j]) {
                    priArray[j + 1] = priArray[j];      //笔插入数据大的整体右移
                } else {
                    break;
                }
            }
            priArray[j + 1] = data;
            nItemes++;
        }
    }

    public long remove() {
        long q = priArray[--nItemes];
        return q;
    }

    public boolean isEmpty() {
        return nItemes == 0;
    }

    public boolean isFull() {
        return nItemes == maxSize;
    }

    public static void main(String[] args) {
        PriorityQ priorityQ = new PriorityQ(10);
        priorityQ.insert(23);
        priorityQ.insert(656);
        priorityQ.insert(134);
        priorityQ.insert(54);
        priorityQ.insert(12);
        long[] priarry = priorityQ.getPriArray();
        System.out.print("插入了：");
        for (int i = 0; i < priarry.length; i++) {
            System.out.print(+priarry[i] + "\t");
        }
        System.out.println();
        System.out.print("删除了：");
        while (!priorityQ.isEmpty()) {
            System.out.print(priorityQ.remove() + "\t");
        }
    }

    public long[] getPriArray() {
        return priArray;
    }

    public void setPriArray(long[] priArray) {
        this.priArray = priArray;
    }
}