【知识框架】
栈
1 栈的定义
需要注意的是:
首先它是一个线性表,也就是说,栈元素具有线性关系,即前驱后继关系。只不过它是一种特殊的线性表而已。定义中说是在线性表的表尾进行插入和删除操作,这里表尾是指栈顶,而不是栈底。
它的特殊之处就在于限制了这个线性表的插入和删除位置,它始终只在栈顶进行。这也就使得:栈底是固定的,最先进栈的只能在栈底。
2 进栈出栈变化形式
看完定义,就会有同学发出质疑:那么最先进栈的元素,是不是就只能是以后出栈呢?
答案是不一定,要看是哪一种情况。栈对线性表的插入和删除的位置进行了限制,并没有对元素进出的时间进行限制,也就是说,在不是所有元素都进栈的情况下,事先进去的元素也可以出栈,只要保证是栈顶元素就可以。
举例来说,如果现在我们有3个整形数字元素1,2,3依次进栈,会有哪些出栈顺序呢?
第一种:1、2、3进,再3、2、1出。这是最简单、最好理解的一种,出栈次序为321。
第二种:1进,1出,2进,2出,3进,3出。也就是进一个出一个,出栈顺序为123。
第三种:1进,2进,2出,1出,3进,3出。出栈顺序为213。
第四种:1进,1出,2进,3进,3出,2出。出栈顺序为132。
第五种:1进,2进,2出,3进,3出,1出。出站顺序是231。
有没有可能是312这样的次序出栈呢?答案是肯定不会。因为3先出栈也就意味着3曾经进过栈,那既然3都进栈了,就意味着1和2已经进栈了,此时,2一定是在1的上面,就是说更接近栈顶,那么出栈顺序只能是321,不然不满足123一次进栈的要求,所以此时不会发生1比2先出栈的情况。
3 栈的基本操作
- InitStack(*S):初始化操作,建立一个空栈S。
- DestoryStack(*S):若栈存在,则摧毁它。
- ClearStack(*S):将栈清空。
- StackEmpty(*S):若栈为空,返回true,否则返回false。
- GetTop(S,*e):若栈存在且非空,用e返回S的栈顶元素。
- Push(*S,e):若栈存在,插入新元素e到栈S种并成为栈顶元素。
- Pop(*S,*e):删除栈S中栈顶元素,并用e返回其值。
- StackLength(S):返回栈S的元素个数。
栈的顺序存储结构及实现
1 栈的顺序存储结构
既然栈是线性表的特例,那么栈的顺序存储其实也是线性表顺序存储的简化,我我们简称为顺序栈。线性表是用数组来实现的;那么,对于栈这种只能一头插入删除的线性表来说,用数组哪一端来作为栈顶和栈底比较好呢?
没错,就是用下标为0的一端作为栈底比较好,因为首元素都存在栈底,变化最小。
我们定义一个top变量来指示栈顶元素在数组中的位置,这top就如同中学物理学过的游标卡尺的游标,如下图所示,他可以来回移动,意味着栈顶的top可以变大变小,但是无论如何游标不能超出尺的长度。同理,若存储栈的长度为StackSize,则栈顶位置top必须小于StackSize。当栈存在一个元素时,top等于0,因此通常把空栈的判定条件定为top=-1;
在Java中,可以使用java.util.Stack类来实现栈的功能,但是自从Java 1.0版本后,建议使用java.util.Vector类来实现栈的功能,因为Stack类的所有方法都是同步的,这使得Stack类的性能不如Vector。
以下是使用Vector类实现栈的一个简单示例:
import java.util.Vector;
public class StackExample {
private Vector stack = new Vector();
public void push(Object item) {
stack.addElement(item); // 添加元素到栈顶
}
从上图中可以看到, Stack 继承了 Vector , Vector 和 ArrayList 类似,都是动态的顺序表,不同的是 Vector 是线程安全的。
若现在有一个栈,StackSize是5,则栈普通情况、空栈和满栈的情况示意图如下图所示。
2 栈的进栈操作
对于栈的插入,即进栈操作,其实就是做了如下图所示的处理。
import java.util.Stack;
public class StackExample {
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
// 进栈操作
stack.push(1);
stack.push(2);
stack.push(3);
// 打印栈内元素
System.out.println("Stack elements: " + stack);
}
}
3 栈的出栈操作
/**
* 出栈
* @return
*/
public int pop() {
if(empty()) {
return -1;
}
if(!queue1.isEmpty()) {
int size = queue1.size();
for (int i = 0; i < size-1; i++) {
queue2.offer(queue1.poll());
}
return queue1.poll();
}else {
int size = queue2.size();
for (int i = 0; i < size-1; i++) {
queue1.offer(queue2.poll());
}
return queue2.poll();
}
}
栈的链式存储结构及实现
链式存储结构最大的好处就是没有空间的限制,可以通过指针指向将结点像以链式的形式把结点链接,我们熟悉的线性表就有链式存储结构。当然,栈同样有链式存储结构,栈的链式存储结构,简称链栈。
从图片可以看到,和单链表很像,拥有一个头指针top,又称作栈顶指针,所以此时就不再需要单链表里面的头结点了。
对于链栈来说,基本不存在栈满的情况,除非计算机内存已经没有了可使用的空间,如果真的存在,那么计算机系统面临着即将死机崩溃的情况,而不是这个链栈是否溢出的问题了。
对于空栈来说,链表的定义是头指针指向NULL,而链栈是top=NULL。
public class LinkedListStack<T> {
private Node<T> top;
public LinkedListStack() {
top = null;
}
1 链栈的结构定义
class Node<T> {
T data;
Node<T> next;
public Node(T data) {
this.data = data;
this.next = null;
}
}
2 进栈操作
public void push(T data) {
Node<T> newNode = new Node<>(data);
newNode.next = top;
top = newNode;
}
这里重新回忆一下参数传参的两种方式:传值、传地址。
传值:传值无非就是实参拷贝传递给形参,单向传递(实参->形参),二者中间做了一个拷贝动作,即两者的实际地址不同了,所以对任何一方的操作都不会影响到另一方。
传地址:形参和实参是同一个变量,即使用相同的内存空间,二者有相同的地址,修改任意一方都将相互影响。
3 出栈操作
队列
我们在使用电脑时或多或少都有经历过,机器有时候会处于疑似死机的状态,鼠标点什么似乎都没有什么用,双击任何快捷方式都不动弹。就当你将要失去耐心,决定reset的时候,突然它就像酒醒了一样,把你刚刚点击的所有操作全部都按照顺序执行了一遍。这其实是因为操作系统中的多个程序因需要通过一个通道输出,而按照先后次序排队等待造成的。
再比如像移动、联通、电信等客服电话,客服人员与客户相比总是少数,在所有的客服人员都占线的情况下,客户会被要求等待,直到有某个客服人员空下来,才能让最先等待的客户接通电话。这里也是将所有当前拨打客服电话的客户进行了排队处理。
操作系统和客服系统中,都是应用了一种数据结构来实现刚才的先进先出的排队功能,这就是队列。
概念
队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out)。
入队列:进行插入操作的一端称为队尾(Tail/Rear)。
出队列:进行删除操作的一端称为队头(Head/Front)。
队列的使用
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());
}
}
队列模拟实现
顺序结构(数组):优点是访问元素的时间复杂度为O(1),适合队列的插入和删除操作通常在队列的一端进行(即“先进先出”FIFO)。然而,当队列满时,添加新元素需要移动所有后续元素,空间效率较低,且不适合动态扩容。
链式结构(链表):链表则更灵活,能够动态地增加或减少容量,无需预先设定大小。对于频繁的插入和删除操作(尤其是中间位置),链表表现更好,因为只需要修改相邻节点的指针。但是,访问任意位置的元素时间复杂度为O(n)。
总的来说,如果队列的长度变化不大,且经常从队列前端进行操作,顺序结构可能是更好的选择;如果队列长度可能会增长并且有频繁的随机访问需求,或者频繁在队列中部插入和删除,那么链式结构会更有优势。
双向链表节点
public static class ListNode{
ListNode next;
ListNode prev;
int value;
ListNode(int value){
this.value = value;
}
}
ListNode first; // 队头
ListNode last; // 队尾
int size = 0;
public void offer(int e){
ListNode newNode = new ListNode(e);
if(first == null){
first = newNode;
// last = newNode;
}else{
last.next = newNode;
newNode.prev = last;
// last = newNode;
}
last = newNode;
size++;
}
public int poll(){
// 1. 队列为空
// 2. 队列中只有一个元素----链表中只有一个节点---直接删除
// 3. 队列中有多个元素---链表中有多个节点----将第一个节点删除
int value = 0;
if(first == null){
return null;
}else if(first == last){
last = null;
first = null;
}else{
value = first.value;
first = first.next;
first.prev.next = null;
first.prev = null;
}
--size;
return value;
}
public int peek(){
if(first == null){
return null;
}
return first.value;
}
public int size() {
return size;
}
public boolean isEmpty(){
return first == null;
}
}
循环队列
循环队列是一种特殊的线性表数据结构,它在队列的一端添加元素,在另一端删除元素。与普通的队列(先进先出,FIFO)不同的是,循环队列的最后一个位置之后紧跟着第一个位置,形成了一个首尾相连的闭环。当试图从队列尾部删除元素而队列为空时,不会引发错误,而是会自动跳转到队列头部开始。相反,当试图从队列头部添加元素而队列已满时,也不会溢出,而是会替换掉队尾的第一个元素。
循环队列的优势在于它能够有效地利用有限的空间,避免了普通数组在队列满时需要动态扩容的问题。但是,由于其内部逻辑相对复杂,可能会增加一些额外的操作开销,如判断队列是否满或空、元素移动等。
判断队列的空与满
判断队列是否为空或满通常涉及到队列的数据结构特性。在大多数队列数据结构中,如数组队列或链表队列,有以下几个常用的方法:
数组队列:如果队列是通过固定大小的数组实现的,你可以检查队列的起始位置(front)和结束位置(rear)。如果front等于rear(即指向数组的两个指针相等),说明队列是空的;如果(rear + 1)% 队列长度 == front,表示已满(因为数组索引从0开始,加1会超出范围并回到开头)。
链表队列:对于链表队列,你需要分别检查头节点(head)是否存在以及当前队列元素的数量(通常是通过一个计数器)。如果头节点为空,则队列为空;如果元素数量达到某个预设的最大值,则认为队列已满。
设计你的循环队列。循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
class MyCircularQueue {
public int[] elem;
public int first;
public int last;
public MyCircularQueue(int k) {
elem = new int[k];
}
public boolean enQueue(int value) {
if(isFull()) {
return false;
}
elem[last] = value;
last = (last+1)%elem.length;
return true;
}
public boolean deQueue() {
if(isEmpty()) {
return false;
}
first = (first+1)%elem.length;
return true;
}
//得到队头元素
public int Front() {
if(isEmpty()) {
return -1;
}
return elem[first];
}
public int Rear() {
if(isEmpty()) {
return -1;
}
int index = (last == 0) ?
elem.length-1 : last-1;
return elem[index];
}
public boolean isEmpty() {
return first == last;
}
public boolean isFull() {
return (last+1)%elem.length == first;
}
}
双端队列
Deque 是一个接口,使用时必须创建 LinkedList 的对象。
栈和队列相关例题
用队列实现栈
请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop和empty)
class MyStack {
Queue<Integer> queue1;
Queue<Integer> queue2;
/** Initialize your data structure here. */
public MyStack() {
queue1 = new LinkedList<Integer>();
queue2 = new LinkedList<Integer>();
}
/** Push element x onto stack. */
public void push(int x) {
queue2.offer(x);
while (!queue1.isEmpty()) {
queue2.offer(queue1.poll());
}
Queue<Integer> temp = queue1;
queue1 = queue2;
queue2 = temp;
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
return queue1.poll();
}
/** Get the top element. */
public int top() {
return queue1.peek();
}
/** Returns whether the stack is empty. */
public boolean empty() {
return queue1.isEmpty();
}
}
用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、top、pop和empty)
class MyQueue {
Deque<Integer> inStack;
Deque<Integer> outStack;
public MyQueue() {
inStack = new ArrayDeque<Integer>();
outStack = new ArrayDeque<Integer>();
}
public void push(int x) {
inStack.push(x);
}
public int pop() {
if (outStack.isEmpty()) {
in2out();
}
return outStack.pop();
}
public int peek() {
if (outStack.isEmpty()) {
in2out();
}
return outStack.peek();
}
public boolean empty() {
return inStack.isEmpty() && outStack.isEmpty();
}
private void in2out() {
while (!inStack.isEmpty()) {
outStack.push(inStack.pop());
}
}
}
括号匹配
给定一个只包括‘(’,‘)’,‘{’,‘}’,‘[’,‘]’的字符串 s ,判断字符串是否有效。
有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
class Solution {
public boolean isValid(String s) {
int n = s.length();
if (n % 2 == 1) {
return false;
}
Map<Character, Character> pairs = new HashMap<Character, Character>() {{
put(')', '(');
put(']', '[');
put('}', '{');
}};
Deque<Character> stack = new LinkedList<Character>();
for (int i = 0; i < n; i++) {
char ch = s.charAt(i);
if (pairs.containsKey(ch)) {
if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
return false;
}
stack.pop();
} else {
stack.push(ch);
}
}
return stack.isEmpty();
}
}
逆波兰表达式求值
给你一个字符串数组tokens,表示一个根据 逆波兰表示法 表示的算术表达式。请你计算该表达式。返回一个表示表达式值的整数。
class Solution {
public int evalRPN(String[] tokens) {
Deque<Integer> stack = new LinkedList<Integer>();
int n = tokens.length;
for (int i = 0; i < n; i++) {
String token = tokens[i];
if (isNumber(token)) {
stack.push(Integer.parseInt(token));
} else {
int num2 = stack.pop();
int num1 = stack.pop();
switch (token) {
case "+":
stack.push(num1 + num2);
break;
case "-":
stack.push(num1 - num2);
break;
case "*":
stack.push(num1 * num2);
break;
case "/":
stack.push(num1 / num2);
break;
default:
}
}
}
return stack.pop();
}
public boolean isNumber(String token) {
return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));
}
}
最小栈
设计一个支持 push,pop,top操作,并能在常数时间内检索到最小元素的栈。
实现MinStack 类:
- MinStack()初始化堆栈对象。
- void push(int val)将元素val推入堆栈。
- void pop()删除堆栈顶部的元素。
- int top()获取堆栈顶部的元素。
- int getMin()获取堆栈中的最小元素。
class MinStack {
Stack<Integer> stack;
Stack<Integer> minStack;
public MinStack() {
stack = new Stack<>();
minStack = new Stack<>();
}
public void push(int val) {
stack.push(val);
if(minStack.empty()) {
minStack.push(val);
}else {
Integer peekVal = minStack.peek();
if(val <= peekVal) {
minStack.push(val);
}
}
}
public void pop() {
if(stack.empty()) {
return;
}
int popVal = stack.pop();
if(popVal == minStack.peek()) {
minStack.pop();
}
}
public int top() {
if(stack.empty()) {
return -1;
}
return stack.peek();
}
public int getMin() {
if(minStack.empty()) {
return -1;
}
return minStack.peek();
}
}