【数据结构】栈和队列

那我掉的头发算什么

发布于 2026-01-12 18:39:17

1290

前言

栈和队列是计算机科学中最基础且应用广泛的数据结构，它们的设计思想和操作特性在算法与系统开发中扮演着核心角色。以下从基础概念、实现方式、应用场景到实战案例，为你展开全面解析。

栈

概念

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。出栈：栈的删除操作叫做出栈。出数据在栈顶。

栈在现实生活中的例子：

先压入弹夹的子弹最后发射

栈的使用

栈中的方法很少，使用起来非常简单，我们可以像下面这样试着调用方法使用一下：

public static void main(String[] args) {
Stack<Integer> s = new Stack();
s.push(1);
s.push(2);
s.push(3);
s.push(4);
System.out.println(s.size()); // 获取栈中有效元素个数---> 4
System.out.println(s.peek()); // 获取栈顶元素---> 4
s.pop(); // 4出栈，栈中剩余1 2 3，栈顶元素为3
System.out.println(s.pop()); // 3出栈，栈中剩余1 2 栈顶元素为3
if(s.empty()){
System.out.println("栈空");
}else{
System.out.println(s.size());
}
}

不过为了以后使用栈时更加熟练，此外也更加熟悉的认识一下栈，我们仍然像前几章一样，自己动手实现一下。

栈的模拟实现

从上图中可以看到，Stack继承了Vector，Vector和ArrayList类似，都是动态的顺序表，不同的是Vector是线程安全的。

import java.util.Arrays;

public class Mystack {
     public int[] elem;
     public int usedsize;

    public Mystack() {
        elem = new int[10];
    }

    public void push(int val){
        if(isFull()){
            elem = Arrays.copyOf(elem,2*elem.length);
        }
    }
    private boolean isFull(){
        return elem.length == usedsize;
    }
    public int pop(){
        if(isEmpty()){
            throw new PopIndexException();
        }
        int val = elem[usedsize - 1];
        usedsize--;
        return val;
    }

    private boolean isEmpty(){
        return size() == 0;
    }
    public int peek(){
        if(isEmpty()){
            throw new PopIndexException();
        }
        return elem[usedsize - 1];
    }
    public int size(){
        return usedsize;
    }
}

使用起来和编译器定义的stack类差不多。

队列

概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear）出队列：进行删除操作的一端称为队头（Head/Front）

队列的使用

大家请先看这张图，这张图包括了我们学过的还有没学过的各个类和接口之间的关系。我们前几章提到的顺序表、链表、队等都是实际的类，但我们今天提到的队列（Queue）却是一个接口，所以一定要注意：

Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。

public static void main(String[] args) {
Queue<Integer> q = new LinkedList<>();
q.offer(1);
q.offer(2);
q.offer(3);
q.offer(4);
q.offer(5); // 从队尾入队列
System.out.println(q.size());
System.out.println(q.peek()); // 获取队头元素
q.poll();
System.out.println(q.poll()); // 从队头出队列，并将删除的元素返回
if(q.isEmpty()){
System.out.println("队列空");
}else{
System.out.println(q.size());
}
}

还是老样子，会用只是基础，会实现才是掌握了。

队列模拟实现

队列中既然可以存储元素，那底层肯定要有能够保存元素的空间，通过前面线性表的学习了解到常见的空间类型有两种：顺序结构和链式结构。同学们思考下：队列的实现使用顺序结构还是链式结构好？

其实，两种都可以实现，但顺序结构实现起来比较麻烦，我们后面会学习到，一般情况下，我们还是使用链式结构来实现。

那么有会有一个新的问题：我们学了单链表和双链表，那具体用哪个实现更好呢？？？

单链表使用的话只能像上图那样头出尾删，实际应用中还是使用双向链表。下面由我来具体模拟实现一下队列的“类”吧。

public class MyQueue {
    static class ListNode{
        public int val;
        public ListNode prev;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;
    public ListNode last;
    public int usedSize = 0;

    public void offer(int val){
        ListNode node = new ListNode(val);
        if(isEmpty()){
            head = last = node;
        }
        last.next = node;
        node.prev = last;
        last = node;
        usedSize++;
    }

    public int pull(){
        if(isEmpty()){
            throw new PopIndexException();
        }else{
            int val = head.val;
            head = head.next;
            if(head != null){
                head.prev = null;
            }
            usedSize--;
            return val;
        }

    }

    private boolean isEmpty(){
        return usedSize == 0;
    }

    public int peek(){
        return head.val;
    }
}

循环队列

实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。环形队列通常使用数组实现。

数组下标循环的小技巧

下标最后再往后(offset 小于 array.length): index = (index + offset) % array.length

下标最前再往前(offset 小于 array.length): index = (index + array.length - offset) % array.length

如何区分空与满

通过添加 size 属性记录
保留一个位置
使用标记

下面我将展示采用保留一个位置的方法来实现循环队列的操作：

class MyCircularQueue {
    public int front;
    public int rear;
    public int[] elem;

    public MyCircularQueue(int k) {
        elem = new int[k+1];
    }
    
    //入队列 
    public boolean enQueue(int value) {
        if(isFull()) {
            return false;
        }
        elem[rear] = value;
        rear = (rear+1)%elem.length;
        return true;
    }
    //出队列 
    public boolean deQueue() {
        if(isEmpty()) {
            return false;
        }
        front = (front+1)%elem.length;
        return true;
    }
    //得到队头元素 
    public int Front() {
        if(isEmpty()) {
            return -1;
        }
        return elem[front];
    }
    
    public int Rear() {
        if(isEmpty()) {
            return -1;
        }
        int index = (rear == 0) ? elem.length-1 : rear-1;
        return elem[index];
    }
    
    public boolean isEmpty() {
        return rear == front;
    }
    
    public boolean isFull() {
        return (rear+1)%elem.length == front;
    }
}

双端队列 (Deque)

双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。

Deque是一个接口，使用时必须创建LinkedList的对象。

在实际工程中，使用Deque接口是比较多的，栈和队列均可以使用该接口

Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现
Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现

面试题

1.使用队列实现栈用队列实现栈

import java.util.LinkedList;
import java.util.Queue;

class MyStackUseQueue {

    public Queue<Integer> qu1;
    public Queue<Integer> qu2;

    public MyStackUseQueue() {
        qu1 = new LinkedList<>();
        qu2 = new LinkedList<>();
    }
    
    public void push(int x) {
        if(!qu1.isEmpty()) {
            qu1.offer(x);
        }else if(!qu2.isEmpty()) {
            qu2.offer(x);
        }else {
            qu1.offer(x);
        }
    }
    
    public int pop() {
        if(empty()) {
            return -1;
        }
        if(!qu1.isEmpty()) {
            int size = qu1.size();
            for(int i = 0;i < size-1;i++) {
                qu2.offer( qu1.poll());
            }
            return qu1.poll();
        }else  {
            int size = qu2.size();
            for(int i = 0;i < size-1;i++) {
                qu1.offer( qu2.poll());
            }
            return qu2.poll();
        }
    }
    
    public int top() {
        if(empty()) {
            return -1;
        }
        if(!qu1.isEmpty()) {
            int size = qu1.size();
            int val = 0;
            for(int i = 0;i < size;i++) {
                val = qu1.poll();
                qu2.offer(val);
            }
            return val;
        }else  {
            int size = qu2.size();
             int val = 0;
            for(int i = 0;i < size;i++) {
                val = qu2.poll();
                qu1.offer(val);
            }
            return val;
        }
    }
    
    public boolean empty() {
        return qu1.isEmpty() && qu2.isEmpty();
    }
}

2.使用栈实现队列使用栈实现队列

import java.util.ArrayDeque;

class MyQueueUseStack {




    public ArrayDeque<Integer> stack1;
    public ArrayDeque<Integer> stack2;


    public MyQueueUseStack() {
        stack1 = new  ArrayDeque<>();
        stack2 = new  ArrayDeque<>();
    }
    
    public void push(int x) {
        stack1.push(x);
    }
    
    public int pop() {
        if(empty()) {
            return -1;
        }
        if(stack2.isEmpty()) {
           //第一个栈里面所有的元素 放到第二个栈当中 
           while(!stack1.isEmpty()) {
               stack2.push(stack1.pop());
           }
        }
        return stack2.pop();
    }
    
    public int peek() {
        if(empty()) {
            return -1;
        }
        if(stack2.isEmpty()) {
           //第一个栈里面所有的元素 放到第二个栈当中 
           while(!stack1.isEmpty()) {
               stack2.push(stack1.pop());
           }
        }
        return stack2.peek();
    }
    
    public boolean empty() {
        return stack1.isEmpty() && stack2.isEmpty();
    }
}