局域网多网站建设,网络市场调研,网站关键词突然搜不到,最好免费观看高清视频韩国题目详细思路来自于:代码随想录 (programmercarl.com) 栈和队列都是大家不陌生的数据结构,我们之前的栈和队列一般是用数组或链表来实现的 , 这里我们给出实现方式,用于帮助更好的理解. 1.用链表实现栈
/* 基于链表实现的栈 */
class LinkedListStack {
private ListNode sta… 题目详细思路来自于:代码随想录 (programmercarl.com) 栈和队列都是大家不陌生的数据结构,我们之前的栈和队列一般是用数组或链表来实现的 , 这里我们给出实现方式,用于帮助更好的理解. 1.用链表实现栈
/* 基于链表实现的栈 */
class LinkedListStack {
private ListNode stackPeek; // 将头节点作为栈顶private int stkSize 0; // 栈的长度
public LinkedListStack() {stackPeek null;
}
/* 获取栈的长度 */
public int size() {return stkSize;
}
/* 判断栈是否为空 */
public boolean isEmpty() {return size() 0;
}
/* 入栈 */
public void push(int num) {ListNode node new ListNode(num);node.next stackPeek;stackPeek node;stkSize;
}
/* 出栈 */
public int pop() {int num peek();stackPeek stackPeek.next;stkSize--;return num;
}
/* 访问栈顶元素 */
public int peek() {if (size() 0)throw new IndexOutOfBoundsException();return stackPeek.val;
}
/* 将 List 转化为 Array 并返回 */
public int[] toArray() {ListNode node stackPeek;int[] res new int[size()];for (int i res.length - 1; i 0; i--) {res[i] node.val;node node.next;}return res;}
} 2.用数组实现栈
class ArrayStack {private ArrayListInteger stack;public ArrayStack() {
// 初始化列表动态数组stack new ArrayList();
}
/* 获取栈的长度 */
public int size() {return stack.size();
}
/* 判断栈是否为空 */
public boolean isEmpty() {return size() 0;
}
/* 入栈 */
public void push(int num) {stack.add(num);
}
/* 出栈 */
public int pop() {if (isEmpty())throw new IndexOutOfBoundsException();return stack.remove(size() - 1);
}
/* 访问栈顶元素 */
public int peek() {if (isEmpty())throw new IndexOutOfBoundsException();return stack.get(size() - 1);
}
/* 将 List 转化为 Array 并返回 */
public Object[] toArray() {return stack.toArray();}
} 3.两种实现的优缺点
3.1 用数组实现栈的优缺点 在基于数组的实现中入栈和出栈操作都是在预先分配好的连续内存中进行具有很好的缓存本地性因此效率较高。然而如果入栈时超出数组容量会触发扩容机制导致该次入栈操作的时间复杂度变为 (). 3.2 用链表实现栈的优缺点 在链表实现中链表的扩容非常灵活不存在上述数组扩容时效率降低的问题。但是入栈操作需要初始化节点对象并修改指针因此效率相对较低。不过如果入栈元素本身就是节点对象那么可以省去初始化步骤从而提高效率。 4. 用链表实现队列
class LinkedListQueue {private ListNode front, rear; // 头节点 front 尾节点 rearprivate int queSize 0;
public LinkedListQueue() {front null;rear null;
}
/* 获取队列的长度 */
public int size() {return queSize;
}
/* 判断队列是否为空 */
public boolean isEmpty() {return size() 0;
}
/* 入队 */
public void push(int num) {
// 尾节点后添加 numListNode node new ListNode(num);
// 如果队列为空则令头、尾节点都指向该节点if (front null) {front node;rear node;
// 如果队列不为空则将该节点添加到尾节点后} else {rear.next node;rear node;}queSize;
}
/* 出队 */
public int pop() {int num peek();
// 删除头节点front front.next;queSize--;return num;
}
/* 访问队首元素 */
public int peek() {if (size() 0)throw new IndexOutOfBoundsException();return front.val;
}
/* 将链表转化为 Array 并返回 */
public int[] toArray() {ListNode node front;int[] res new int[size()];for (int i 0; i res.length; i) {res[i] node.val;node node.next;}return res;}
}
5.用数组实现队列 你可能会发现一个问题在不断进行入队和出队的过程中 front 和 rear 都在向右移动 当它们到达数组尾部时就无法继续移动了。为解决此问题我们可以将数组视为首尾相接的“环形数组”。对于环形数组我们需要让 front 或 rear 在越过数组尾部时直接回到数组头部继续遍历。这种周期性规律可以通过“取余操作”来实现 /* 基于环形数组实现的队列 */
class ArrayQueue {private int[] nums; // 用于存储队列元素的数组private int front; // 队首指针指向队首元素private int queSize; // 队列长度
public ArrayQueue(int capacity) {nums new int[capacity];front queSize 0;
}
/* 获取队列的容量 */
public int capacity() {return nums.length;
}
/* 获取队列的长度 */
public int size() {return queSize;
}
/* 判断队列是否为空 */
public boolean isEmpty() {return queSize 0;
}
/* 入队 */
public void push(int num) {if (queSize capacity()) {System.out.println( 队列已满);return;
}
// 计算尾指针指向队尾索引 1
// 通过取余操作实现 rear 越过数组尾部后回到头部int rear (front queSize) % capacity();
// 将 num 添加至队尾nums[rear] num;queSize;
}
/* 出队 */
public int pop() {int num peek();
// 队首指针向后移动一位若越过尾部则返回到数组头部front (front 1) % capacity();queSize--;return num;
}
/* 访问队首元素 */
public int peek() {if (isEmpty())throw new IndexOutOfBoundsException();return nums[front];
}
/* 返回数组 */
public int[] toArray() {
// 仅转换有效长度范围内的列表元素int[] res new int[queSize];for (int i 0, j front; i queSize; i, j) {res[i] nums[j % capacity()];}return res;}
}
LeetCode T232 用栈实现队列
题目链接:
232. 用栈实现队列 - 力扣LeetCode 题目思路: 我们这里就要用两个栈来实现队列,一个是stackOut,一个是stackIn,in栈负责将要入队的添加进来,但是这时候我们发现出栈的话会和队列的出队顺序相反,所以我们再入栈一次,这样出栈的顺序就颠倒过来啦,也完美的实现队列的基本功能. 注:一定要将In栈的全部元素一起push进Out栈,否则顺序可能会发生变化,这样就影响了正常的出栈功能. 题目代码:
class MyQueue {StackInteger stackIn;StackInteger stackOut;public MyQueue() {stackIn new Stack();stackOut new Stack();}public void push(int x) {stackIn.push(x);}public int pop() {downStackIn();return stackOut.pop();}public int peek() {downStackIn();return stackOut.peek();}public boolean empty() {downStackIn();return stackOut.isEmpty();}public void downStackIn(){while(!stackOut.isEmpty()){return;}while(!stackIn.isEmpty()){stackOut.push(stackIn.pop());}}
}/*** Your MyQueue object will be instantiated and called as such:* MyQueue obj new MyQueue();* obj.push(x);* int param_2 obj.pop();* int param_3 obj.peek();* boolean param_4 obj.empty();*/
LeetCode T225 用队列实现栈
题目链接:225. 用队列实现栈 - 力扣LeetCode 题目思路: 这里我们同样可以用和上一题同样的思路实现,但是为了更有挑战性,我们决定用一个队列来实现栈,假设我们入队元素是123,此时我们需要的出队元素应该是3,那么我们该如何操作呢,其实,我们只需要让前两个元素重新入队,这样第一个出队的元素就是3了,其实就是前size()-1个元素重新入队,就实现了出栈的操作 这里我使用的是deque,这个类可以实现两天的操作,就是比queue多了两头操作的一些方法. 题目代码:
class MyStack {DequeInteger que1;public MyStack() {que1 new ArrayDeque();}public void push(int x) {que1.addLast(x);}public int pop() {int tmp que1.size()-1;while(tmp0){que1.addLast(que1.peekFirst());que1.pollFirst();tmp--;}return que1.pollFirst();}public int top() {return que1.peekLast();}public boolean empty() {return que1.isEmpty();}
}/*** Your MyStack object will be instantiated and called as such:* MyStack obj new MyStack();* obj.push(x);* int param_2 obj.pop();* int param_3 obj.top();* boolean param_4 obj.empty();*/
