栈
后进先出 LIFO
两种实现方式
- 使用数组实现的叫静态栈
- 使用链表实现的叫动态栈
相关题目
简单难度
225. 用队列实现栈 https://leetcode.cn/problems/implement-stack-using-queues/
class MyStack {
private Queue<Integer> q1;
private Queue<Integer> q2;
public MyStack() {
q1 = new LinkedList<>();
q2 = new LinkedList<>();
}
public void push(int x) {
q2.offer(x);
while (!q1.isEmpty()) {
q2.offer(q1.poll());
}
Queue<Integer> temp = q1;
q1 = q2;
q2 = temp;
}
public int pop() {
return q1.poll();
}
public int top() {
return q1.peek();
}
public boolean empty() {
return q1.isEmpty();
}
}
中等难度
71. 简化路径 https://leetcode.cn/problems/simplify-path/
class Solution {
public String simplifyPath(String path) {
String[] names = path.split("/");
Deque<String> stack = new ArrayDeque<>();
for (String name : names) {
if ("..".equals(name)) {
if (!stack.isEmpty()) {
stack.pollLast();
}
} else if (name.length() > 0 && !".".equals(name)) {
stack.offerLast(name);
}
}
StringBuffer ans = new StringBuffer();
if (stack.isEmpty()) {
ans.append('/');
} else {
while (!stack.isEmpty()) {
ans.append('/');
ans.append(stack.pollFirst());
}
}
return ans.toString();
}
}
队列
先进先出 FIFO
相关题目
简单难度
933. 最近的请求次数 https://leetcode.cn/problems/number-of-recent-calls/
class RecentCounter {
Queue<Integer> q;
public RecentCounter() {
q = new LinkedList<>();
}
public int ping(int t) {
q.offer(t);
while (q.peek().intValue() < t - 3000) {
q.remove();
}
return q.size();
}
}
中等难度
641. 设计循环双端队列 https://leetcode.cn/problems/design-circular-deque/
class MyCircularDeque {
private int[] elements;
private int rear, front;
private int capacity;
public MyCircularDeque(int k) {
capacity = k + 1;
rear = front = 0;
elements = new int[k + 1];
}
public boolean insertFront(int value) {
if (isFull()) {
return false;
}
front = (front - 1 + capacity) % capacity;
elements[front] = value;
return true;
}
public boolean insertLast(int value) {
if (isFull()) {
return false;
}
elements[rear] = value;
rear = (rear + 1) % capacity;
return true;
}
public boolean deleteFront() {
if (isEmpty()) {
return false;
}
front = (front + 1) % capacity;
return true;
}
public boolean deleteLast() {
if (isEmpty()) {
return false;
}
rear = (rear - 1 + capacity) % capacity;
return true;
}
public int getFront() {
if (isEmpty()) {
return -1;
}
return elements[front];
}
public int getRear() {
if (isEmpty()) {
return -1;
}
return elements[(rear - 1 + capacity) % capacity];
}
public boolean isEmpty() {
return rear == front;
}
public boolean isFull() {
return (rear + 1) % capacity == front;
}
}
/**
* Your MyCircularDeque object will be instantiated and called as such:
* MyCircularDeque obj = new MyCircularDeque(k);
* boolean param_1 = obj.insertFront(value);
* boolean param_2 = obj.insertLast(value);
* boolean param_3 = obj.deleteFront();
* boolean param_4 = obj.deleteLast();
* int param_5 = obj.getFront();
* int param_6 = obj.getRear();
* boolean param_7 = obj.isEmpty();
* boolean param_8 = obj.isFull();
*/
标签:return,线性表,队列,int,boolean,isEmpty,capacity,public
From: https://www.cnblogs.com/understanding-friends/p/17988319