线性结构-队列

WuShF

发布于 2023-07-08 15:47:02

1830

发布于 2023-07-08 15:47:02

文章被收录于专栏：笔记分享

队列是一种先进先出First In Fisrt Out,FIFO的线性表。与一般的数组和链表不同，队列要求所有的数据只能从一端进入，从另一端离开。输入进入的一端叫队尾rear，数据离开的一端叫队头front。

数据只能从队尾进入队列，从队头离开队列。队列的具体实现并无一定之规，既可以使用数组，也可以使用链表。接下来将介绍用链表实现的链队列。

队列的定义

队列的定义与普通的链表定义很相似，需要先定义队列的节点类，在定义队列类。队列的节点类可以用Java语言描述如下：

class MyQueueNode {
    int data; // 数据域，变量类型为int
    MyQueueNode next; // 指针域，指向下一个结点

    public MyQueueNode(int data) {
        // 构造方法，在构造结点对象时将data赋值给this .data成员
        this.data = data;
    }
}

MyQueueNode是队列节点类型，与链表节点类Node相似。该类中包含两个成员变量：

data：数据域成员变量
next：指针域成员变量

public MyQueueNode(int data)是队列节点类的构造函数，用来初始化队列节点实例。

接下来定义队列类：

因为数据必须从队尾进入队列，从队头离开队列。所以队列类中要包含队头和队尾两个指针，用来进行数据的入队列操作和出队列操作。

public class MyQueue {
    private MyQueueNode front; // 队列头
    private MyQueueNode rear; // 队列尾

    private int ERROR_ELEM_VALUE = -111;

    public MyQueue() {
        // 构造方法
        front = null;
        rear = null;
    }
    //更多操作
}

该类中包含两个MyQueueNode类型的成员变量：front和rear。

front表示队头，指向队头结点。
rear表示队尾，指向队列的尾节点。

函数MyQueue()是MyQueue类的构造函数，用来初始化MyQueue类的对象。在构造函数中将成员变量front和rear都初始化为null，表示当前队列中没有任何元素，也就是队列为空。

队列的基本操作

入队列操作

入队列操作是让指定元素从队列的尾部进入队列的操作。元素进入队列后，队尾指针rear要修改，而队头指针一般不变，除非最初的队列为空。

public void enQueue(int data) {
    // 入队列操作，将data存入队列中
    MyQueueNode node = new MyQueueNode(data); // 生成队列结点
    if (front == null && rear == null) {
        // 队列为空，将front和rear都指向node
        front = rear = node;
    } else {
        // 队列不为空，将node从队列尾部加入队列
        rear.next = node; // 将node结点连入队列尾部
        rear = node; // rear指向node结点
    }
}

由于我们的队列是用链表实现的，所以我们在队尾插入节点时，应执行rear.next = node;，并将队尾指针指向新的队尾节点rear = node。当front == null && rear == null时，说明当前队列为空。入队列操作直接将node赋值给front和rear即可。

出队列操作

出队列操作是将队头元素从队列中取出的操作。元素出队列后，队头指针front将指向原对头结点的后继节点。而队尾指针rear一般不变，除非出队列后队列变为空。

public int deQueue() {
    // 出队列操作，从队头取出数据元素并返回
    if (front == null) {
        // 队列为空，返回null
        return ERROR_ELEM_VALUE;
    }
    int data = front.data;
    front = front.next;
    if (front == null) {
        // 如果出队列后队列为空，则rear也要置为null
        rear = null;
    }
    return data;
}

deQueue()函数的作用是将队头元素取出。首先判断front是否为null，如果front为null，则说明该队列是一个空队列，直接返回无效值ERROR_ELEM_VALUE即可。如果队列不为空，则通过语句data = front.data将队头元素取出并赋值给data，稍后返回该值。执行front = front.next;操作将队头结点删除。在删除完队头节点后，要判断front是否等于null，如果front等于null，则说明删除队头节点后队列为空，此时**rear**也要置为**null**。否则队头节点会始终被**rear**引用而无法被回收释放。

获取长度与销毁队列

可以用遍历的方式获取队列长度：

public int getQueueLength() {
    // 获取队列的长度
    int length = 0;
    MyQueueNode p = front;
    while (p != null) {
        length++;
        p = p.next;
    }
    return length;
}

也可以用介绍链表那节中的方法：在队列类中声明成员变量length，入队和出队时修改length。需要时直接获取length求得长度。

public void destroyQueue() {
    // 销毁队列
    rear = null;
    front = null;
}

销毁一个队列与销毁一个链表的方法相似，只需要将队头指针front和队尾指针rear都置为null即可，Java的垃圾回收机制会将队列链表逐一回收并释放。

双端队列

双端队列集合了队列和栈的优点。从队列的两端都可以插入数据和删除数据。与普通队列相比，双端队列的操作更加灵活。虽然双端队列不及普通队列和栈应用广泛。但在某些场景下有其独特的优势。

来两道题

打印符号三角形

规定这样一种符号三角形：

+	+	-	+	-	+	+
 + - - - - +
	- + + + -
	 - + + -
  	- + -
    	+

该符号三角形的特点是，仅由'+'和'-'两种符号构成。同号下面是'+'，异号下面是'-'。因此第一行决定了整个符号三角形的'+'和'-'的数量以及排列状态。编写一个程序，输入任意符号三角形的第1行，打印出符合规则的符号三角形。

我们可以使用一个队列，并利用它的先进先出特性，先将第1行的n个符号入队列，再依次将符号取出。在取出第i个符号时，要判断它是否跟第i-1个符号相同。

如果相同，则将'+'入队列
如果不同，则将'-'入队列

在第一行的n个符号全部出队列并打印出来后，第二行的n-1个符号也已全部进入队列。重复上述操作，一共打印n行，即可打印出完整的符号三角形。

public static void printCharacterTriangle(String firstLine) {
    // 创建队列实例，将字符逐一取出加入队列
    MyQueue queue = new MyQueue();
    int count = firstLine.length();
    for (int i = 0; i < count; i++) {
        queue.enQueue(firstLine.charAt(i));
    }
    // 逐行操作
    for (int i = 0; i < count; i++) {
        // 输出三角形左侧的空格
        for (int j = 0; j < i; j++) {
            System.out.print(" ");
        }
        // 每行第一个元素需要单独拿出
        char a = queue.deQueue();
        System.out.print(a + " ");
        // 依次向右取出元素，根据a和b的关系控制字符入队
        // 入队之后修正a的值为b
        for (int j = 0; j < count - i - 1; j++) {
            char b = queue.deQueue();
            System.out.print(b + " ");
            if (a == b) {
                queue.enQueue('+');
            } else {
                queue.enQueue('-');
            }
            a = b;
        }
        System.out.println();
    }
}

函数printCharacterTriangle(String firstLine)的参数是一个字符串，它指定了符号三角形中第1行的符号。外层循环的作用是控制三角形输出的行数。符号三角形的行数也就是第1行符号的数量。也就是说，如果第一行的符号数量为count，则该三角形的行数也是count。内存循环包括两个for循环。第1个for循环的作用是在每行的开始位置打印空格，其目的是控制符号三角形的输出形状。第2个for循环的作用是打印符号三角形中某一行的符号。

用两个栈实现一个队列

请用两个栈实现一个队列的以下操作：

入队列：enQueue(int elem)
出队列：int deQueue()
判断队列是否为空：boolean inEmptyQueue()
获取队列中元素的数量：int getCount()

跟前面介绍的链队列不同，本题要求用两个栈实现一个队列的功能，所以需要重新设计。要用栈实现队列的功能，必须通过一种方式将先进后出FILO转化为先进先出FIFO，从而模拟队列的逻辑特性。

一个栈stack1用来存放数据，另一个栈stack2作为缓冲区。在入队列时，将元素压入stack1。在出队列时，将stack1中的元素逐个弹出并压入stack2。然后将stack2的栈顶元素取出作为出队元素。

有一个问题就是如果stack1中存在元素，应该何时压入stack2？

解决方法很简单：入队列时，将元素压入stack1。出队列时，判断stack2是否为空，如果不为空，则直接取出栈顶元素；如果为空则将stack1中的元素逐一弹出并压入stack2，然后再取出stack2的栈顶元素。

public class StackQueue {
    MyStack stack1 = new MyStack(5);
    MyStack stack2 = new MyStack(5);

    public void enQueue(int elem) {
        stack1.push(elem);
    }

    public int deQueue() {
        if (!stack2.isEmpty()) {
            return stack2.pop();
        } else {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
            return stack2.pop();
        }
    }

    public boolean inEmptyQueue() {
        if (stack1.isEmpty() && stack2.isEmpty()) {
            return true;
        }
        return false;
    }

    public int getCount() {
        return stack1.getCount() + stack2.getCount();
    }

    public static void main(String[] args) {
        StackQueue queue = new StackQueue();
        queue.enQueue(1);
        queue.enQueue(2);
        queue.enQueue(3);
        queue.enQueue(4);
        queue.enQueue(5);
        System.out.println("The elements count in this queue is " + queue.getCount());
        System.out.println(queue.deQueue());
        System.out.println(queue.deQueue());
        System.out.println("The elements count in this queue is " + queue.getCount());
        System.out.println(queue.deQueue());
        System.out.println(queue.deQueue());
        System.out.println(queue.deQueue());
        System.out.println("The elements count in this queue is " + queue.getCount());
        System.out.println("The queue is " + (queue.inEmptyQueue() ? "empty" : "not empty"));
    }
}

栈队列由栈组成。我们也需要根据这次的需求，在之前栈的基础上进行一些修改。

public class MyStack {
	int[] stack; // 用数组实现一个栈
	int top; // 栈顶索引，实际上就是栈顶位置的数组下标
	int capacity; // 栈的容量
	public static final int ERROR_ELEM_VALUE = -111;

	public MyStack(int capacity) {
		stack = new int[capacity]; // 动态初始化栈，长度为capacity
		top = 0; // 栈顶索引为0，说明此时是空栈
		this.capacity = capacity; // 初始化栈的容量
	}

	public void push(int elem) {
		// 入栈操作
		if (top == capacity) {
			// 达到栈容量上限，需要扩容
			increaseCapacity();
		}
		stack[top] = elem; // 将元素elem存放在stack[top]
		top++; // top指向栈顶元素的上一个空间，此时栈顶元素为stack[top-1]
	}

	public int pop() {
		// 出栈操作
		if (top == 0) {
			// 栈顶等于栈底，说明栈中没有数据
			// System.out.println("There are no elements in stack");
			return ERROR_ELEM_VALUE;
		}
		return stack[--top];
	}

	public int getCount() {
		return top; // 因为top指向栈顶元素的上一个空间，所以top值即为栈中元素个数
	}

	public boolean isEmpty() {
		if (top == 0) {
			return true; // 当top等于0是栈为空
		}
		return false;
	}

	public void increaseCapacity() {
		// 增加栈的容量
		// 初始化一个新栈，容量是原stack容量的2倍
		int[] stackTmp = new int[stack.length * 2];
		System.arraycopy(stack, 0, stackTmp, 0, stack.length);
		stack = stackTmp;
	}
}

我们这次有两个需求：