栈（Stack）
又名堆栈，它是一种重要的数据结构。从数据结构角度看，栈也是线性表，其特殊性在于栈的基本操作是线性表操作的子集，它是操作受限的线性表，因此，可称为限定性的数据结构。限定它仅在表尾进行插入或删除操作。表尾称为栈顶，相应地，表头称为栈底。栈的基本操作除了在栈顶进行插入和删除外，还有栈的初始化，判空以及取栈顶元素等。
队列（Queue）
是一种先进先出（FIFO，First-In-First-Out）的线性表。
在具体应用中通常用链表或者数组来实现。队列只允许在后端（称为 rear）进行插入操作，在前端（称为 front）进行删除操作。
队列的操作方式和堆栈类似，唯一的区别在于队列只允许新数据在后端进行添加。
Queue接口与List、Set同一级别，都是继承了Collection接口。LinkedList实现了Queue接 口。
队列常用的方法有：add、remove、element、offer、poll、peek、put、take，方法解释：
- add
增加一个元索 如果队列已满，则抛出一个IIIegaISlabEepeplian异常 - remove
移除并返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常 - element
返回队列头部的元素 如果队列为空，则抛出一NoSuchElementException异常 - offer 添加一个元素并返回true 如果队列已满，则返回false
- poll 移除并返问队列头部的元素 如果队列为空，则返回null
- peek 返回队列头部的元素 如果队列为空，则返回null
- put 添加一个元素 如果队列满，则阻塞
- take 移除并返回队列头部的元素
面试题 03.04. 化栈为队
实现一个MyQueue类，该类用两个栈来实现一个队列。
示例：
MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false
题解：
/**
* 实现思路：
* 创建2个栈，栈1只负责入栈，栈2只负责出栈
* 存入几个元素到栈1后，如果此时栈2为空，则将栈1中的元素转移到栈2，从栈2出栈
* 如果此时栈2中不为空，则直接从栈2出栈
*/
class MyQueue {
Stack<Integer> stack1; //stack1只负责入栈
Stack<Integer> stack2; //stack2只负责出栈
/** Initialize your data structure here. */
public MyQueue() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}
/** Push element x to the back of queue. */
public void push(int x) {
stack1.push(x);
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
if (!stack2.isEmpty()) {
return stack2.pop();
} else {
//将stack1中所有元素转移到stack2
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
return stack2.pop();
}
}
/** Get the front element. */
public int peek() {
if (!stack2.isEmpty()) {
return stack2.peek();
} else {
//将stack1中所有元素转移到stack2
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
return stack2.peek();
}
}
/** Returns whether the queue is empty. */
public boolean empty() {
if (stack1.isEmpty() && stack2.isEmpty()) {
return true;
} else {
return false;
}
}
}
1047. 删除字符串中的所有相邻重复项
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例：
输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
题解：
/**
* 用栈的结构来维护没有重复项的字母序列:
* 循环从字符串中取出一个字符，与栈顶字符对比，如果不同，则放入栈；如果相同，则两个字符消掉，
* 即删除字符串中该字符，同时删除栈中该字符，最终栈中剩下来的字符数组为最终字符串
*
*/
class Solution {
public String removeDuplicates(String S) {
Stack<Character> stack = new Stack();
char[] chars = S.toCharArray();
for (char ch : chars) {
if (stack.isEmpty()) { //如果栈为空，则直接入栈
stack.push(ch);
} else { //如果栈不为空，则判断当前字符与栈顶字符是否相同，相同就从栈中弹出栈
if (ch != stack.peek()) {
stack.push(ch);
} else {
stack.pop();
}
}
}
StringBuilder stringBuilder = new StringBuilder();
for (Character ch : stack) {
stringBuilder.append(ch);
}
return stringBuilder.toString();
}
}
682. 棒球比赛
你现在是棒球比赛记录员。
给定一个字符串列表，每个字符串可以是以下四种类型之一：
1.整数（一轮的得分）：直接表示您在本轮中获得的积分数。
- "+"（一轮的得分）：表示本轮获得的得分是前两轮有效 回合得分的总和。
- "D"（一轮的得分）：表示本轮获得的得分是前一轮有效 回合得分的两倍。
- "C"（一个操作，这不是一个回合的分数）：表示您获得的最后一个有效 回合的分数是无效的，应该被移除。
每一轮的操作都是永久性的，可能会对前一轮和后一轮产生影响。
你需要返回你在所有回合中得分的总和。
示例 1:
输入: ["5","2","C","D","+"]
输出: 30
解释:
第1轮：你可以得到5分。总和是：5。
第2轮：你可以得到2分。总和是：7。
操作1：第2轮的数据无效。总和是：5。
第3轮：你可以得到10分（第2轮的数据已被删除）。总数是：15。
第4轮：你可以得到5 + 10 = 15分。总数是：30。
题解：
/**
* 思路：
* 用Stack来存储每一个轮的得分，最后累加得分。
* 根据每种字符规则，处理当前轮的得分
*/
class Solution {
public int calPoints(String[] ops) {
//stack为Integer类型，只存储每轮分数数值
Stack<Integer> stack = new Stack();
for (String op : ops) {
if (op.equals("+")) {
int last = stack.pop(); //上一轮分数
int cur = stack.peek() + last; //当前轮分数
stack.push(last);
stack.push(cur);
} else if (op.equals("C")) {
//移除上一轮得分
stack.pop();
} else if (op.equals("D")) {
//当前分数为上一轮的2倍
int score = stack.peek()*2;
stack.push(score);
} else {
//当前为数字，直接加入
stack.push(Integer.valueOf(op));
}
}
int totalScore = 0;
for (Integer score : stack) {
totalScore += score;
}
return totalScore;
}
}
933. 最近的请求次数
写一个 RecentCounter 类来计算最近的请求。
它只有一个方法：ping(int t)，其中 t 代表以毫秒为单位的某个时间。
返回从 3000 毫秒前到现在的 ping 数。
任何处于 [t - 3000, t] 时间范围之内的 ping 都将会被计算在内，包括当前（指 t 时刻）的 ping。
保证每次对 ping 的调用都使用比之前更大的 t 值。
示例：
输入：inputs = ["RecentCounter","ping","ping","ping","ping"], inputs = [[],[1],[100],[3001],[3002]]
输出：[null,1,2,3,3]
题解：
class RecentCounter {
Queue<Integer> queue;
public RecentCounter() {
queue = new LinkedList<>();
}
public int ping(int t) {
queue.add(t); //将当前时间入列
//遍历队列，判断当前元素是否是当前时间前3000的值，如果是，则从队列中移除
while (queue.peek() < t - 3000) {
queue.poll();
}
return queue.size();
}
}
剑指 Offer 59 - I. 滑动窗口的最大值
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
示例:
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
题解：
class Solution {
/**
* 思路：
* 从nums数组中取出前k个数，存入队列中
* 获取队列的最大值存储到集合中
* 然后队列移除头部，在尾部添加第k+1个数，获取队列中最大值存储到集合中
*
* @param nums
* @param k
* @return
*/
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums.length == 0) {
//如果数组为空，则返回空数组
return new int[0];
}
int[] result = new int[nums.length-k+1]; //总共需要输出的数组
Queue<Integer> queue = new LinkedList<>();
//首次添加前k个数到队列中作为初始队列
for (int j=0;j<k;j++) {
queue.add(nums[j]);
}
//遍历队列获取最大值
int maxNum = queue.peek();
for (Integer num : queue) {
if (num > maxNum) {
maxNum = num;
}
}
result[0] = maxNum;
for (int i=0;i<nums.length-k;i++) {
queue.poll(); //移除队列头部
queue.add(nums[i+k]); //添加数组下一个值到队列尾部
//遍历队列获取最大值
int max = queue.peek();
for (Integer num : queue) {
if (num > max) {
max = num;
}
}
result[i+1] = max;
}
return result;
}
}
网友评论