【学习笔记】链表、栈、队列的实现方法 | 学习笔记 / 代码学习

链表（Linked List）、栈（Stack）、队列（Queue）是数据结构中最基础的三大结构（还有一个是数组）。熟悉并掌握数据结构和算法是合格程序员基本功之一，不同的结构在不同的应用场景中往往会带来不一样的处理效率。之前文章中已经介绍了链表，本文将介绍栈和队列，以及这三种结构的实现方法。

栈和队列

栈

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

栈示意图

栈，通俗地说，就像我们往一个杯子里面放东西一样，先放进去的放在最下面，只有把上面的东西拿出来后才能拿出下面压着的东西。

栈，具有很多用处，计算机中很多处理都是通过栈这种数据结构来进行的，比如算术运算，准备两个栈，一个栈存储数字，一个栈存储符号，从头开始依次把字符对应压入到这两个栈中，当所有字符都放入栈之后，依次从数字栈中取出两个元素，并从符号栈中取出一个元素，进行计算，结果压回数字栈，继续以此运行，直到符号栈为空，或者数字栈只剩下一个元素为止，弹出这个数字即为最后的结果。

这么说很抽象，后面以实际题目进行讲解。

实现方法

可以用数组（连续的内存空间，按索引取值）来实现栈。

栈的基本方法只有两个，分别为入栈（Push）元素和出栈（Pop）。

以 Lab3 作为例题，题目如下：

链表 UML 图

method

public Stack(int size)
- Creates an empty stack whose capacity is size（构造方法，初始化栈，参数 size 指定栈的大小。）
public boolean isEmpty()
- Returns true if the stack is empty and false otherwise （判断栈是否为空）
public boolean isFull()
- Returns true if the stack is full and false otherwise（判断栈是否已满）
public Double top()
- Returns the top element （获取栈顶元素）
- Returns null if the stack is empty （如果栈为空则返回 null）
public Double push(double x)
- Adds a new element with value x to the top of the stack （将新元素 x 压入栈顶）
- Returns the new element if the operation is successful and null otherwise （如果操作成功则返回新元素，否则返回 null）
public Double pop()
- Removes and returns the top element of the stack （弹出栈顶元素并返回该元素）
- Returns null if the operation fails （如果操作失败则返回 null）
public void displayStack()
- Displays all elements in the stack from top to bottom （从栈顶到栈底显示栈中所有元素）

这是老师给的模板，在此基础上进行实现：

public class Stack {

	/* YOUR CODE HERE*/ 
	
	public static void main(String[] args) {
		Stack myStack = new Stack(4);
		System.out.println(myStack.isEmpty());
		myStack.push(-3);
		myStack.push(5);
		System.out.println("The stack has 2 items:");
		myStack.displayStack();
		myStack.push(1);
		myStack.push(2);
		myStack.push(-1);
		System.out.println("The stack has 4 items:");
		myStack.displayStack();
		System.out.println("The top is: " + myStack.top());
		System.out.println(myStack.isFull());
		myStack.pop();
		myStack.pop();
		myStack.pop();
		myStack.pop();
		System.out.println("The stack is empty:");
		myStack.displayStack();
	}

}

我们定义一个 double 类型数组 values 来存储栈中的元素，一个整型变量 top 来表示栈顶元素在数组中的索引位置。初始时，栈为空，top 设置为 -1。

    private Double[] values;
	private int top;
	public Stack(int size) {
		this.values = new Double[size];
		top = -1;
	}

对于 isEmpty 方法，只需要检查 top 是否为 -1 即可：（注意 autolab 不允许使用中文注释）

    public boolean isEmpty() {
        return top == -1; //  或者 return this.top < 0; 
    }

对于 isFull 方法，需要检查 top 是否等于数组的最后一个索引位置，即 values.length - 1：

    public boolean isFull() {
        return top == values.length - 1;
    }

对于 top 方法，需要返回栈顶元素，如果栈为空则返回 null：

    public Double top() {
        if (isEmpty()) {
            return null;
        }
        return values[top];
    }

对于 push 方法，需要将新元素压入栈顶，如果栈已满则返回 null，否则将元素放入数组并更新 top：

    public Double push(double x) {
        if (isFull()) {
            return null;
        }
        values[++top] = x;
        return x;
    }

对于 pop 方法，需要弹出栈顶元素并返回它，如果栈为空则返回 null：

    public Double pop() {
        if (isEmpty()) {
            return null;
        }
        return values[top--];
    }

最后，对于 displayStack 方法，这个根据个人爱好实现即可，这里提供一种方法：

    public void displayStack() {
        System.out.print("top -->");
		for(int i = this.top; i >= 0; i --)
			System.out.println("\t|\t " + String.format("%, .4f", this.values[i].doubleValue()) + "\t|");
		System.out.println("\t+-----------------------+");
    }

最后将上面的方法整合到 Stack 类中即可，总的来说还是比较简单的。

队列

队列（queue）是只允许在一端进行插入操作，在另一端进行删除操作的线性表，队列的特点是先进先出（First In First Out），简称 FIFO。

允许插入的一端称为队尾（rear），允许删除的一端称为队头(front)。

向队列中插入新的数据元素称为入队。

从队列中删除队头元素称为出队。

和链表相比，队列更像是排队买票，先来的人先买到票，后来的只能在后面排队等待。

但是队列的实现相对复杂一些，因为队列的插入和删除操作分别在两端进行，如果使用普通的数组来实现队列，可能会出现数组前端有空闲空间但无法利用的情况。

我们可以利用一种思路：

当项目排队时，后索引会向前移动
当项目出队时，前索引也会向前移动一个元素

这样就将数组变成了循环数组（circular array），即当后索引到达数组末尾时，如果前索引不在数组起始位置，则可以将后索引重新指向数组起始位置，从而利用前端的空闲空间。

实现方法

与栈类似，队列可以用数组来实现队列。

队列的基本方法也只有两个，分别为入队（enqueue）元素和出队（dequeue）。

我们来看题目Lab4 题目如下：

队列 UML 图

method

public Queue(int size)
- Creates an empty queue whose capacity is size（构造方法，初始化队列，参数 size 指定队列的大小。）
public boolean isEmpty()
- Returns true if the queue is empty and false otherwise （判断队列是否为空）
public boolean isFull()
- Returns true if the queue is full and false otherwise（判断队列是否已满）
public Double enqueue(double x)
- Adds a new element with value x to the rear of the queue （将新元素 x 插入队尾）
- Returns the new element if the operation is successful and null otherwise （如果操作成功则返回新元素，否则返回 null）
public Double dequeue()
- Removes and returns the front element of the queue （弹出队头元素并返回该元素）
- Returns null if the operation fails （如果操作失败则返回 null）
public void displayQueue()

老师给的模板，在此基础上进行实现：

public class Queue {


	/*YOUR CODE HERE*/
	
	
	public static void main(String[] args) {
		Queue myQueue = new Queue(4);
		System.out.println(myQueue.isEmpty());
		myQueue.enqueue(-2);
		myQueue.enqueue(3);
		myQueue.enqueue(1);
		System.out.println("The queue has 3 items: -2, 3, 1");
		myQueue.displayQueue();
		myQueue.enqueue(8);
		myQueue.enqueue(6);
		System.out.println("The queue has 4 items: -2, 3, 1, 8");
		System.out.println(myQueue.isFull());
		myQueue.displayQueue();		
		myQueue.dequeue();
		myQueue.dequeue();
		System.out.println("The queue has 2 items: 1, 8");
		myQueue.displayQueue();
		myQueue.dequeue();
		myQueue.dequeue();
		myQueue.dequeue();
		System.out.println("The queue is empty:");
		myQueue.displayQueue();

	}
}

我们定义一个 integer 类型数组 values 来存储队列中的元素，两个整型变量 front 和 rear 分别表示队头和队尾在数组中的索引位置。初始时，队列为空，front 设置为 0， rear 设置为 -1。此外还需要一个整型变量 counter 来记录队列的当前大小。

    private Integer[] values;
	private int front, rear, counter;

	public CircularDeque(int size) {
		values = new Integer[size];
		front = 0;
		counter = 0;
		rear = -1;
	}

对于 isEmpty 方法，只需要检查 counter 是否为 0 即可：

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

对于 isFull 方法，需要检查 counter 是否等于数组的长度：

    public boolean isFull() {
        return counter == values.length;
    }

对于 enqueue 方法，需要将新元素插入队尾，如果队列已满则返回 null，否则将元素放入数组并更新 rear 和 counter：

    public Integer enqueue(double x) {
        if (isFull()) {
            return null;
        }
        rear = (rear + 1) % values.length; //这一步是实现循环队列的关键，当 rear 到达数组末尾时，重新指向数组起始位置
        values[rear] = x;
        counter++;
        return x;
    }

对于 dequeue 方法，需要弹出队头元素并返回它，如果队列为空则返回 null：

    public Integer dequeue() {
        if (isEmpty()) {
            return null;
        }
        Integer value = values[front];
        front = (front + 1) % values.length; // 同样实现循环队列
        counter--;
        return value;
    }

最后，对于 displayQueue 方法，这个根据个人爱好实现即可，这里依旧提供一种方法：

    public void displayQueue() {
        if (isEmpty()) {
			System.out.println("Empty queue!");
			return;
		}

		System.out.print("front-> ");
		for (int i = front; i <= rear; i++) {
			if (i != front)
				System.out.print("\t");
			if (i == values.length) { 
				i = 0;
			} else {
				System.out.printf("|\t%7.4f        |", values[i]);
				if (i != values.length - 1)
					System.out.print("\n"); 
			}
		}
		System.out.println("<-rear"); 
	}

最后将上面的方法整合到 Queue 类中即可，有了链表的基础，实现起来还是不难的。

本文当然不会只是介绍实现方法，有请 assignment 登场。

链表、栈、队列的进阶

链表的进阶

定义以下三个方法：

removeNodes
removeDuplicates
reverseList

其中

public int removeNodes(double x)
- Removes all the elements from a linked list that have value x. (从链表中删除所有值为 x 的元素)
- Returns the number of occurrences of x. (返回 x 出现的次数)
public void removeDuplicates()
- Remove duplicates from sorted list (you may assume that the node values in the list are in non-decremental order). (从排序链表中删除重复元素（你可以假设链表中的节点值是非递减顺序的）)
- Removes all nodes that have duplicate values, leaving only nodes with distinct values. (删除所有具有重复值的节点，只保留具有不同值的节点)
- Your implementation should finish the removing with SINGLE traversal of the whole list, which means you cannot simply invoke the removeNodes method for removing the duplicates. (你的实现应该在对整个列表进行单次遍历的情况下完成删除，这意味着你不能简单地调用 removeNodes 方法来删除重复项)
public void reverseList()
- Reverse the linked list WITHOUT using extra space. (反转链表不使用额外空间)
- Hint: Reverse the linked list can be performed by modifying the “next” pointer of current node from the original next node to its previous node. (提示：反转链表可以通过将当前节点的“下一个”指针从原始下一个节点修改为其前一个节点来执行)

这是老师给的模板，在此基础上进行实现：

public class List {

    private Node head;

    public List() {
        this.head = null;
    }

    public boolean isEmpty() {
        return this.head == null;
    }

    public Node insertNode(int index, double x) {
        if (index < 0)
            return null;
        int currIndex = 1;
        Node currNode = this.head;
        while (currNode != null && index > currIndex) {
            currNode = currNode.getNext();
            currIndex++;
        }
        if (index > 0 && currNode == null)
            return null;

        Node newNode = new Node(x);
        if (index == 0) {
            newNode.setNext(this.head);
            this.head = newNode;
        } else {
            newNode.setNext(currNode.getNext());
            currNode.setNext(newNode);
        }
        return newNode;
    }

    public Node findNode(double x) {
        for (Node currNode = head; currNode != null; currNode = currNode.getNext())
            if (currNode.getData() == x)
                return currNode;
        return null;
    }

    public Node removeNode(double x) {
        if (head == null)
            return null;
        Node currNode = head;
        if (head.getData() == x) {
            this.head = head.getNext();
            return currNode;
        }
        for (; currNode.getNext() != null; currNode = currNode.getNext())
            if (currNode.getNext().getData() == x) {
                Node matchNode = currNode.getNext();
                currNode.setNext(matchNode.getNext());
                return matchNode;
            }
        return null;
    }

    public void displayList() {
        Node currNode = head;
        if (currNode != null) {
            System.out.print(currNode.getData());
            for (currNode = currNode.getNext(); currNode != null; currNode = currNode.getNext()) {
                System.out.print(" -> " + currNode.getData());
            }
        }
        System.out.println();
    }

    public void removeDuplicates() {
        /*YOUR CODE HERE*/
    }

    public void reverseList() {
        /*YOUR CODE HERE*/
    }

    public int removeNodes(double x) {
        /*YOUR CODE HERE*/
    }

    public static void main(String[] args) {
        /*YOUR CODE HERE*/
    }
}

public class Node {
	private double data;
	private Node next;
	
	public Node(double data) {
		this.data = data;
		this.next = null;
	}
	
	public double getData() {
		return this.data;
	}
	
	public Node getNext() {
		return this.next;
	}
	
	public void setNext(Node next) {
		this.next = next;
	}

}

对于 removeNodes 方法，我们可以遍历链表，检查每个节点的值是否等于 x，如果是，则将该节点从链表中删除，并计数器加一。最后返回计数器的值：

    public int removeNodes(double x) {
        if (head == null)
			return null;
		Node currNode = head;
		if (head.getData() == x) {
			this.head = head.getNext();
			return currNode;
		}
		for (; currNode.getNext() != null; currNode = currNode.getNext())
			if (currNode.getNext().getData() == x) {
				Node matchNode = currNode.getNext();
				currNode.setNext(matchNode.getNext());
				return matchNode;
			}
		return null;
	}

对于 removeDuplicates 方法，由于链表是排序的（这是此题关键），我们可以使用了一个哑节点（dummy node）来简化边界情况的处理。pastNode 用于跟踪当前节点的前一个节点，currNode 用于遍历链表。当发现重复节点时，hasDuplicate 标志被设置为 true，直到遇到不同的值时，根据 hasDuplicate 的状态决定是否删除重复节点。

    public void removeDuplicates() {

		if (head == null) {
			return;
		} // define head and second node is null
		Node dummy = new Node(0);
		dummy.setNext(head);
		Node pastNode = dummy;
		Node currNode = head;
		boolean hasDuplicate = false;

		while (currNode != null) {// condition: when head is not null return null
			Node nextNode = currNode.getNext();
			if (nextNode != null && currNode.getData() == nextNode.getData()) {
				hasDuplicate = true;
				currNode = nextNode;
			} else {
				if (hasDuplicate) {
					pastNode.setNext(nextNode);
					hasDuplicate = false;
				} else { 
					pastNode = currNode;
				}
				currNode = nextNode;
			}
		}
		head = dummy.getNext();
	}

对于 reverseList 方法，我们可以使用三个指针来反转链表：pastNode 指向前一个节点，currNode 指向当前节点，nextNode 指向下一个节点。在遍历链表时，我们将当前节点的 next 指针指向前一个节点，然后更新指针以继续遍历。最后，将头节点更新为 prevNode，即新的头节点。

    public void reverseList() {
        Node currNode = head;
		Node pastNode = null;
		while (currNode != null) {
			Node nextNode = currNode.getNext(); 
			currNode.setNext(pastNode);
			pastNode = currNode;
			currNode = nextNode;
		}
		head = pastNode;
    }

这个方法也许不好想，但理解了其原理后实现起来还是比较简单的。核心代码就只有三行。

接着来看栈的进阶。

栈的进阶

只需要写一个 computePostfix 静态方法：

public static int computePostfix(String postfix)
- postfix is a string representing a valid postfix expression which contains only digits and ‘+’, ‘-’, ‘*’, ‘/’ operators, separated by ‘,’. (后缀表达式是一个字符串，表示一个有效的后缀表达式，只包含数字和‘+’，‘-’，‘*’，‘/’运算符，以‘，’分隔)
- You can assume the length of postfix will not exceed 50. (你可以假设后缀表达式的长度不会超过 50)
- Returns the evaluation result. (返回计算结果)
Consider the postfix expression evaluation algorithm introduced in Lec3:
- If the element is an operand, push it to stack. (如果元素是操作数，则将其压入栈中)
- If the element is an operator O, pop twice and get A and B respectively. Calculate BOA and push it back to stack. (如果元素是运算符 O，则弹出两次，分别获取 A 和 B。计算 BOA 并将其压回栈中)
- When the expression is ended, the value in the stack is the final answer. (当表达式结束时，栈中的值即为最终答案)

这个考验的是对栈的理解和应用能力。以及学习能力。老师给的模板如下：

public class Stack {
	private Integer[] values;
	private int top;
	public Stack(int size) {
		this.values = new Integer[size];
		top = -1;
	}
	public boolean isEmpty() {
		return this.top < 0;
	}
	public boolean isFull() {
		return this.top == this.values.length - 1;
	}
	public Integer top() {
		if(top < 0)
			return null;
		return this.values[top];
	}
	public Integer push(String x) {
		if(isFull())
			return null;
		this.values[++top] = Integer.valueOf(x);
		return top();
	}
	public Integer push(Integer x) {
		if(isFull())
			return null;
		this.values[++top] = x;
		return top();
	}
	public Integer pop() {
		if(top < 0)
			return null;
		return this.values[top --];
	}
	public void displayStack() {
		System.out.print("top -->");
		for(int i = this.top; i >= 0; i --)
			System.out.println("\t|\t " + this.values[i].intValue() + "\t|");
		System.out.println("\t+---------------+");
	}
	public static int computePostfix(String postfix) {
		/*YOUR CODE HERE*/
	}
	public static void main(String[] args) {
		/*YOUR CODE HERE*/
		
	}

}

首先得使用 split 函数按分隔符分割字符串

参考这个链接：

Java String split()

把这个学会，剩下的就是 switch 函数来判断是数字还是符号，然后进行相应的操作即可（注意题目要求的操作顺序）：

    public static int computePostfix(String postfix) {
		Stack stack = new Stack(50);
		String[] result = postfix.split(",");
		for (int count = 0; count < result.length; count++) {
			int answer = 0;
			if (result[count].equals("+") || result[count].equals("-") || result[count].equals("*")
					|| result[count].equals("/")) {
				int right = stack.pop();
				int left = stack.pop();
				switch (result[count]) {
					case "+":
						answer = left + right;
						break;
					case "-":
						answer = left - right;
						break;
					case "*":
						answer = left * right;
						break;
					case "/":
						answer = left / right;
						break;
				}
				stack.push(answer);
			} else {
				stack.push(result[count]);
			}
		}
		return stack.pop(); 
	}

这道题算是三道题里面最简单的了，最后就是队列了。

队列的进阶

之前介绍了循环队列的实现方法，这里则需要实现一个双端队列（Deque，Double-Ended Queue），需要允许在队列的两端进行插入和删除操作。

CircularDeque(int size) Initializes the deque with a maximum size of size. (使用最大大小为 size 初始化双端队列)
Integer insertFront() Adds an item at the front of Deque. Returns this item if the operation is successful, or Null otherwise. (在队列前端插入一个元素。如果操作成功，返回该元素，否则返回 Null。)
Integer insertLast() Adds an item at the rear of Deque. Returns this item if the operation is successful, or Null otherwise. (在队列后端插入一个元素。如果操作成功，返回该元素，否则返回 Null。)
Integer deleteFront() Deletes an item from the front of Deque. Returns this item if the operation is successful, or Null otherwise. (从队列前端删除一个元素。如果操作成功，返回该元素，否则返回 Null。)
Integer deleteLast() Deletes an item from the rear of Deque. Returns this item if the operation is successful, or Null otherwise. (从队列后端删除一个元素。如果操作成功，返回该元素，否则返回 Null。)
boolean isEmpty() Returns true if the deque is empty, or false otherwise. (如果双端队列为空，返回 true，否则返回 false。)
boolean isFull() Returns true if the deque is full, or false otherwise. (如果双端队列已满，返回 true，否则返回 false。)
Void displayCircularDeque(). (显示双端队列中的所有元素)

老师给的模板如下：


public class CircularDeque {
	private Integer[] values;
	private int front, rear, counter;
	
	public CircularDeque(int size) {
		/*YOUR CODE HERE*/
	}

	public boolean isEmpty() {
		/*YOUR CODE HERE*/
	}

	public boolean isFull() {
		/*YOUR CODE HERE*/
	}

	public Integer insertFront(int x) {
		/*YOUR CODE HERE*/
	}

	public Integer deleteFront() {
		/*YOUR CODE HERE*/
	}


	public Integer insertLast(int x) {
		/*YOUR CODE HERE*/
	}

	public Integer deleteLast() {
		/*YOUR CODE HERE*/
	}

	public void displayCircularDeque() {
		/*YOUR CODE HERE*/
	}
	
	public static void main(String[] args) {
		/*YOUR CODE HERE*/

	}

}

与之前实现的循环队列类似，我们需要维护一个数组 values 来存储双端队列的元素，两个指针 front 和 rear 分别指向队列的前端和后端，以及一个计数器 counter 来记录当前队列的大小。

    public CircularDeque(int size) {
		values = new Integer[size];
		front = 0;
		counter = 0;
		rear = -1;
	}

对于 isEmpty 和 isFull 方法，与之前的实现类似：

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

    public boolean isFull() {
        return counter == values.length;
    }

对于 insertFront 方法，我们需要在队列前端插入一个元素，如果队列已满则返回 null，否则将元素放入数组并更新 front 和 counter：

    public Integer insertFront(int x) {
        if (isFull()) {
            return null;
        } else {
            int temp = values[rear];
            front = (front - 1 + values.length) % values.length; //这一步和上文稍有出入
            values[front] = x;
            counter--;
            return temp;
        }
    }

解释代码：temp 用于存储当前队列后端的元素值，然后将 front 指针向前移动一个位置，并将新元素插入到 front 指向的位置。最后返回原后端元素的值。

对于 deleteFront 方法，我们需要从队列前端删除一个元素，如果队列为空则返回 null，否则将元素从数组中删除并更新 front 和 counter：

    public Integer deleteFront() {
		if (isEmpty()) {
			return null;
		} else {
			int temp = values[rear]; 
			front = (front + 1) % values.length;
			counter--;
			return temp;
		}
	}

与此类似，insertLast 和 deleteLast 方法分别在队列后端进行插入和删除操作：

    public Integer insertLast(int x) {
        if (isFull()) {
            return null;
        } else {
            rear = (rear + 1) % values.length;
            values[rear] = x;
            counter++;
            return x;
        }
    }

    public Integer deleteLast() {
        if (isEmpty()) {
            return null;
        } else {
            int temp = values[rear];
            rear = (rear - 1 + values.length) % values.length;
            counter--;
            return temp;
        }
    }

至此，双端队列的基本操作已经实现。至于 displayCircularDeque 方法，则可以参考或直接使用上文给的例子即可。

那么本文就介绍到这里，链表、栈、队列是数据结构中非常基础且重要的部分，掌握它们的实现方法和应用场景对于编程能力的提升非常有帮助。希望本文能对您有所帮助，祝您学习愉快！

这是我目前写过最长的一篇文章了，虽然不会有很多人看 QAQ，也算是我对所学知识的一次复习吧，本文所有题目全部是英文，为了严谨我照搬一遍，并加上我的翻译，如果有错误欢迎指正，我收到后会及时更正~