数据结构与算法 - 栈队列

程序员文章站 2022-04-01 11:22:53

目录栈stack栈的接口设计动态数组实现栈练习题有效的括号队列队列的接口设计简单实现一个queue练习 - 用栈实现队列双端队列双端队列接口设计双端队列源码循环队列入队列出队列栈stack栈是一种特殊的线性表，只能在一端进行操作往栈中添加元素的操作，一般叫做push，入栈从栈中移除元素的操作，一般叫做pop，出栈后进先出的原则栈......

栈stack

栈的接口设计

栈stack

栈是一种特殊的线性表，只能在一端进行操作
往栈中添加元素的操作，一般叫做push，入栈
从栈中移除元素的操作，一般叫做pop，出栈
后进先出的原则

数据结构与算法 - 栈队列

栈的接口设计

int size(); // 元素的数量
boolean isEmpty(); // 是否为空
void push(E element); // 入栈
E pop(); // 出栈
E top(); // 获取栈顶元素
void clear(); // 清空

栈的内部实现是否可以直接利用以前学过的数据结构 ?

动态数组、链表

动态数组实现栈

public class Stack <E> {

	private List<E> list = new ArrayList<>();
	
	public void clear(){
		list.clear();
	}
	
	public boolean isEmpty(){
		return list.isEmpty();
	}
	
	public void push(E element){
		list.add(element);
	}
	
	public E pop(){
		return list.remove(list.size() - 1); 
	}
	
	public E top(){
		return list.get(list.size() - 1);
	}
	
}

练习题

有效的括号

数据结构与算法 - 栈队列

解法1：

public boolean isValid(String s) {
	while(s.contains("{}") || s.contains("[]") || s.contains("()")){
		s.replace("{}", "");
		s.replace("[]", "");
		s.replace("()", "");
	}
	return s.isEmpty();
}

解法2：

public boolean isValid2(String s){
	Stack<Character> stack = new Stack<>();
	int len = s.length();
	for(int i = 0; i < len; i++){
		char c = s.charAt(i);
		if(c == '(' || c == '[' || c == '{'){ // 左括号
			stack.push(s.charAt(i)); // 左字符入栈
		}else{ // 右括号
			if(stack.isEmpty()) return false; // 没有左括号, 却匹配到了右括号，false
			
			char left = stack.pop();
			if(left == '(' && c != ')') return false; // 左右括号不匹配
			if(left == '[' && c != ']') return false; // 左右括号不匹配
			if(left == '{' && c != '}') return false; // 左右括号不匹配
		}
	} // 扫描完毕
	return stack.isEmpty();
}

解法3：

static HashMap<Character, Character> map = new HashMap<>();
static {
	map.put('(', ')');
	map.put('[', ']');
	map.put('{', '}');
}
public boolean isValid(String s){
	Stack<Character> stack = new Stack<>();
	int len = s.length();
	for(int i = 0; i < len; i++){
		char c = s.charAt(i); 
		if(map.containsKey(c)){ // 左括号，哈希表中有该键则入栈
			stack.push(c);
		}else{ // 右括号
			if(stack.isEmpty()) return false;
			char left = stack.pop();
			if(c != map.get(left)) return false;
		}
	}
	return stack.isEmpty();
}

队列

队列是一种特殊的线性表，只能在头尾两端进行操作；

队尾：只能从队尾添加元素，入队
对头：只能从对头移除元素，出队
先进先出的原则，First In First Out，FIFO

数据结构与算法 - 栈队列

队列的接口设计

int size(); // 元素的数量
boolean isEmpty(); // 是否为空
void clear(); // 清空
void enQueue(E element); // 入队
E deQueue(); // 出队
E front(); // 获取队列的头元素

队列的内部实现是否可以直接利用以前学过的数据结构？

动态数组、链表
优先使用双向链表，因为队列主要是往头尾操作元素

简单实现一个queue

import java.util.LinkedList;
import java.util.List;

public class Queue<E> {

    private List<E> linkedList= new LinkedList<>();

    public int size() {
        return linkedList.size();
    }

    public boolean isEmpty() {
        return linkedList.isEmpty();
    }

    // 入队列
    public void enQueue(E element){
        linkedList.add(element);
    }

    // 出队列
    public E deQueue(){
        return linkedList.remove(0);
    }

    // 获取队列的头元素
    public E front(){
        return linkedList.get(0);
    }


    public static void main(String[] args) {
        Queue<Integer> queue = new Queue();
        queue.enQueue(1);
        queue.enQueue(2);
        queue.enQueue(3);
        queue.enQueue(4);
        queue.enQueue(5);

        while (!queue.isEmpty()){
            System.out.println("Queue.main:"+queue.deQueue());
        }
    }
}

练习 - 用栈实现队列

准备2个栈：instack、outstack
入队时，push到instack
出队时：如果outstack 为空，将instack所有元素逐一弹出，push到outstack，outstack弹出栈顶元素

如果outstack不为空，outstack弹出栈顶元素

数据结构与算法 - 栈队列



/**
 * 使用栈实现队列
 */
public class QueueStack {

    private java.util.Stack<Integer> integerStack = new java.util.Stack<>();

    private java.util.Stack<Integer> outStack = new java.util.Stack<>();

    /**
     * 入队
     *
     * @param x
     */
    public void push(int x) {
        integerStack.push(x);
    }

    /**
     * 出队
     *
     * @return
     */
    public int pop() {
        if (outStack.empty()) {
            while (!integerStack.empty()) {
                outStack.push(integerStack.pop());
            }
        }
        return outStack.pop();
    }

    /**
     * 获取队头元素
     *
     * @return
     */
    public int peek() {
        if (outStack.empty()) {
            while (!integerStack.empty()) {
                outStack.push(integerStack.pop());
            }
        }
        return outStack.peek();
    }

    /**
     * 是否为空
     *
     * @return
     */
    public boolean empty() {
        return integerStack.isEmpty() && outStack.isEmpty();
    }

    public static void main(String[] args) {

    }
}

双端队列

双端队列是能在头尾两端添加、删除的队列；

英文 deque 是 double ended queue 的简称；

双端队列接口设计

int size(); // 元素的数量
boolean isEmpty(); // 是否为空
void clear(); // 清空
void enQueueRear(E element); // 从队尾入队
E deQueueFront(); // 从队头出队
void enQueueFront(E element); // 从队头入队
E deQueueRear(); // 从队尾出队
E front(); // 获取队列的头元素
E rear(); // 获取队列的尾元素

双端队列源码

import java.util.LinkedList;
import java.util.List;

/**
 * 双端队列
 */
public class Deque<E> {

    private List<E> list = new LinkedList<E>();

    // 入队列 队尾
    public void enQueueRear(E element) {
        list.add(element);
    }

    // 入队列 队头
    public void enQueueFront(E element) {
        list.add(0, element);
    }

    // 出队列 队头
    public E deQueueFront() {
        return list.remove(0);
    }

    // 出队列 队尾
    public E deQueueRear() {
        return list.remove(list.size() - 1);
    }

    public boolean isEmpty() {
        return list.isEmpty();
    }

    // 获取队列的头元素
    public E front() {
        return list.get(0);
    }

    // 获取队列的头元素
    public E rear() {
        return list.get(list.size() - 1);
    }

    public static void main(String[] args) {
        Deque<Integer> deque = new Deque<>();
        deque.enQueueFront(1);
        deque.enQueueFront(2);
        deque.enQueueRear(3);
        deque.enQueueRear(4);
        while (!deque.isEmpty()){
            System.out.println("Queue.main:"+deque.deQueueRear());
        }
    }
}

循环队列

其实队列底层也可以使用动态数组实现，并且各项接口也可以优化到O(1)的时间复杂度。

循环队列底层用数组实现

数据结构与算法 - 栈队列

public class CircleQueue<E> {

    private int front;
    private int size;
    private E[] elements;
    private static final int DEFAULT_CAPACITY = 10;

    public CircleQueue() {
        elements = (E[]) new Object[DEFAULT_CAPACITY];
    }

    public int size() {
        return size;
    }

    // 入队列
    public void enQueue(E element) {
        // 扩容
		ensureCapacity(size + 1);
        elements[(front + size) % elements.length] = element;
        size++;
    }


    // 出队列
    public E deQueue() {
        E frontElement = elements[front];
        elements[front] = null;
        front = (front + 1) & elements.length;
        size--;
        return frontElement;
    }

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

    // 获取队列的头元素
    public E front() {
        return elements[front];
    }

    // 扩容
	private void ensureCapacity(int capacity) {
		int oldCapacity = elements.length;
		if (oldCapacity >= capacity)
			return;
		// 新容量为旧容量的 1.5 倍
		int newCapacity = oldCapacity + (oldCapacity >> 1);
		E[] newElements = (E[]) new Object[newCapacity];
		for (int i = 0; i < size; i++) { // 旧数组中元素移到新数组
			newElements[i] = elements[(i + front) % elements.length];
			// newElements[i] = elements[index(i)];
		}
		System.out.println("从" + oldCapacity + "扩容到" + newCapacity);
		elements = newElements;
		front = 0; // 重置front
	}


    public static void main(String[] args) {

    }
}

入队列

当我们往队列里添加元素时，通常往size位置添加元素； elements[size] = element;

数据结构与算法 - 栈队列

但是我们发现循环队列出队列时会把元素清除掉，队头位置后移，那么此时elements[size] = element; 就会覆盖44这个元素的值

数据结构与算法 - 栈队列

那么我们需要往队尾添加元素，其实就是 elements[front + size] = element; 但是如果此时队尾添加元素已经到达数组最大长度，继续往队尾添加元素，那么将会数组越界。

数据结构与算法 - 栈队列

于是我们 elements[(front + size) % elements.length] = element; 对数组长度取余

数据结构与算法 - 栈队列

出队列

出队时，需要取出队头数据，并将front 前移，size减一；E frontElement = elements[front];front++;size--; 但是如果下面情况 front++ 为7

数据结构与算法 - 栈队列

那么我们将 front = (front + 1) % elements.length;

数据结构与算法 - 栈队列

循环双端队列

可以进行两端添加、删除操作的循环队列

本文地址：https://blog.csdn.net/lm324114/article/details/107657154

数据结构与算法 - 栈队列

栈stack

栈的接口设计

动态数组实现栈

练习题

有效的括号

队列

队列的接口设计

简单实现一个queue

练习 - 用栈实现队列

双端队列

双端队列接口设计

双端队列源码

循环队列

入队列

出队列

C#数据结构与算法揭秘五栈和队列

C#栈和队列的简介,算法与应用简单实例

C#数据结构与算法揭秘三链表

C#数据结构与算法揭秘四双向链表

JS中数据结构与算法---排序算法(Sort Algorithm)实例详解

C#数据结构与算法揭秘二线性结构

C#数据结构与算法揭秘一

JavaScript数据结构学习之数组、栈与队列

算法与数据结构(算法简介及大O表示法)

栈和队列数据结构的基本概念及其相关的Python实现

数据结构与算法 - 栈 队列

栈stack

栈的接口设计

动态数组实现栈

练习题

有效的括号

队列

队列的接口设计

简单实现一个queue

练习 - 用栈实现队列

双端队列

双端队列接口设计

双端队列源码

循环队列

入队列

出队列

C#数据结构与算法揭秘五 栈和队列

C#栈和队列的简介,算法与应用简单实例

C#数据结构与算法揭秘三 链表

C#数据结构与算法揭秘四 双向链表

JS中数据结构与算法---排序算法(Sort Algorithm)实例详解

C#数据结构与算法揭秘二 线性结构

C#数据结构与算法揭秘一

JavaScript数据结构学习之数组、栈与队列

算法与数据结构(算法简介及大O表示法)

栈和队列数据结构的基本概念及其相关的Python实现

数据结构与算法 - 栈队列

C#数据结构与算法揭秘五栈和队列

C#数据结构与算法揭秘三链表

C#数据结构与算法揭秘四双向链表

C#数据结构与算法揭秘二线性结构