MENU

栈和队列的相关问题

August 7, 2018 • Read: 3024 • 算法阅读设置

用数组实现栈展开目录

实现栈太简单了,直接上代码

代码展开目录
  • public class Stack {
  • private Integer[] arr;
  • private Integer idx;
  • public Stack(int size) {
  • if(size < 0)
  • throw new StackOverflowError("please input again and input numer must more than 0");
  • arr = new Integer[size];
  • idx = 0;
  • }
  • public Integer peek() {
  • if(idx == 0)
  • return null;
  • return arr[idx - 1];
  • }
  • public void push(int obj) {
  • if(idx == arr.length)
  • throw new StackOverflowError("The Stack is full");
  • arr[idx++] = obj;
  • }
  • public Integer pop() {
  • if(idx == 0)
  • throw new StackOverflowError("The Stack is null");
  • return arr[--idx];
  • }
  • public static void main(String[] args) {
  • Stack stack = new Stack(5);
  • stack.push(1);
  • stack.push(2);
  • stack.push(3);
  • System.out.println(stack.pop());
  • System.out.println(stack.pop());
  • System.out.println(stack.pop());
  • }
  • }

用数组实现队列展开目录

题解展开目录

队列可能稍微有点复杂,定义队列的时候需要定义三个变量,分别是 end,start,size,先说说他们分别的作用,每次用户拿队中的元素,都从 start 下标位置取,每次进队都从 s=end 位置进,每次出队或者进队 size 都要 ++ 或 --

假设数组长度是 3,如果 size 没有到 3,进队时就把元素放到 end 的位置上,这是 end 和 size 之间的约束关系;如果 size 不等于 0,出队时就总出 start 位置,这是 start 和 size 之间的约束关系。end 本身还有一个约束,end 是控制进队的,所以每次进一个元素 end 就 ++,但在 ++ 前,如果 end== 数组长度,那么 end 就回到开头也就是 0 位置;同样的,start 也有这个约束

代码展开目录
  • public class Queue {
  • private int start = 0,end = 0,size = 0;
  • private int[] arr;
  • Queue(int size) {
  • arr = new int[size];
  • }
  • public void push(int obj){
  • if(size == arr.length)
  • throw new ArrayIndexOutOfBoundsException("The Queue is full");
  • size++;
  • arr[end] = obj;
  • end = end == arr.length - 1 ? 0 : end + 1;
  • }
  • public int pop(){
  • if(size == 0)
  • throw new ArrayIndexOutOfBoundsException("The Queue is full");
  • size--;
  • int tmp = start;
  • start = start == arr.length - 1 ? 0 : start + 1;
  • return arr[tmp];
  • }
  • public Integer peek() {
  • if(size == 0)
  • return null;
  • return arr[start];
  • }
  • public static void main(String[] args) {
  • Queue queue = new Queue(3);
  • queue.push(3);
  • queue.push(2);
  • queue.push(1);
  • System.out.println(queue.pop());
  • System.out.println(queue.pop());
  • System.out.println(queue.pop());
  • }
  • }

题目链接:LeetCode155展开目录

题解展开目录

如何在常数时间内检索到最小元素这是关键,可以开辟一个新的 min 栈,当 min 为空或者 push 的值比 min 的栈顶元素小时,就将该值 push 到 min 中去,否则就再次压入 min 栈的栈顶元素

同时如果用户调用了一次 pop () 函数,那么 min 栈也要跟着 pop

代码展开目录
  • class MinStack {
  • int[] data = new int[10000];
  • int[] min = new int[10000];
  • int idx_data,idx_min;
  • public MinStack() {
  • idx_data = 0;
  • idx_min = 0;
  • }
  • public void push(int x) {
  • data[idx_data++] = x;
  • if(idx_min == 0 || x < min[idx_min - 1])
  • min[idx_min++] = x;
  • else
  • min[idx_min++] = min[idx_min - 2];
  • }
  • public void pop() {
  • idx_min--;
  • idx_data--;
  • }
  • public int top() {
  • return data[idx_data - 1];
  • }
  • public int getMin() {
  • return min[idx_min - 1];
  • }
  • }

题目链接:LeeCode225展开目录

题解展开目录

这个题不要觉得很简单就不想写,很多地方有可能会用到,比方说图的深度优先遍历,别人不让你用栈去实现深度优先遍历,怎么办,其实就和这个道题的思路一样,用两个队列合成一个栈,然后再去遍历

那么说一下这道题的思路。假设现在有元素 12345 入队,要按照栈的方式弹出,应该怎么做,很简单,再设一个辅助队列 help,将 1234 全部弹出到 help 中,然后弹出 5 返回给用户即可

代码展开目录
  • class MyStack {
  • Queue<Integer> myQueue;
  • public MyStack() {
  • myQueue = new LinkedList();
  • }
  • /** Push element x onto stack. */
  • public void push(int x) {
  • int n= myQueue.size();
  • Queue<Integer> tempQueue= new LinkedList();
  • for(int i= 0; i<n; i++){
  • tempQueue.add(myQueue.poll());
  • }
  • myQueue.add(x);
  • for(int i= 0; i<n; i++){
  • myQueue.add(tempQueue.poll());
  • }
  • }
  • /** Removes and returns the element on top of the stack. */
  • public int pop() {
  • return (int)myQueue.poll();
  • }
  • /** Get the top element. */
  • public int top() {
  • return (int)myQueue.peek();
  • }
  • /** Returns whether the stack is empty. */
  • public boolean empty() {
  • return myQueue.isEmpty();
  • }
  • }

题目链接:LeetCode232展开目录

题解展开目录

用两个栈实现一个队列更简单,假设先在有两个栈 data 和 help,12345 首先进 data 栈,然后将 data 栈中的元素全部倒到 help 栈里,然后依次从 help 栈弹出即可,所以进元素全从 data 栈进,出元素全从 help 栈出,但是这两个栈交互的时候有两个条件:

  1. data 栈每次倒元素必须倒完
  2. 如果 help 栈里有东西,绝对不能将 data 栈的元素倒入 help 栈
代码展开目录
  • class MyQueue {
  • private Stack<Integer> data = new Stack<Integer>();
  • private Stack<Integer> help = new Stack<Integer>();
  • public MyQueue() {
  • }
  • /** Push element x to the back of queue. */
  • public void push(int x) {
  • data.push(x);
  • }
  • /** Removes the element from in front of queue and returns that element. */
  • public int pop() {
  • if(help.isEmpty())
  • data_to_help();
  • return help.pop();
  • }
  • /** Get the front element. */
  • public int peek() {
  • if(help.isEmpty())
  • data_to_help();
  • return help.peek();
  • }
  • /** Returns whether the queue is empty. */
  • public boolean empty() {
  • return data.isEmpty() && help.isEmpty();
  • }
  • public void data_to_help() {
  • while(!data.isEmpty()) {
  • help.push(data.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();
  • */
Last Modified: May 23, 2020
Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment

  • OωO
  • |´・ω・)ノ
  • ヾ(≧∇≦*)ゝ
  • (☆ω☆)
  • (╯‵□′)╯︵┴─┴
  •  ̄﹃ ̄
  • (/ω\)
  • ∠( ᐛ 」∠)_
  • (๑•̀ㅁ•́ฅ)
  • →_→
  • ୧(๑•̀⌄•́๑)૭
  • ٩(ˊᗜˋ*)و
  • (ノ°ο°)ノ
  • (´இ皿இ`)
  • ⌇●﹏●⌇
  • (ฅ´ω`ฅ)
  • (╯°A°)╯︵○○○
  • φ( ̄∇ ̄o)
  • ヾ(´・ ・`。)ノ"
  • ( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
  • (ó﹏ò。)
  • Σ(っ °Д °;)っ
  • ( ,,´・ω・)ノ"(´っω・`。)
  • ╮(╯▽╰)╭
  • o(*////▽////*)q
  • >﹏<
  • ( ๑´•ω•) "(ㆆᴗㆆ)
  • (。•ˇ‸ˇ•。)
  • 泡泡
  • 阿鲁
  • 颜文字