数据结构与算法之栈入门题目

Bertha 。 2021-12-23 14:55 242阅读 0赞

# 数据结构与算法之栈题目 #

--------------------

## 目录 ##

1.  用数组实现大小固定的队列和栈
2.  实现一个特殊的栈，在实现栈的基础功能上，再实现返回栈中最小元素的操作
3.  如果仅用栈结构实现队列结构和如何仅用队列结构实现栈结构

--------------------

### 1. 用数组实现大小固定的队列和栈 ###

##### （一）数组实现大小固定的栈思路 #####

1.  创建一个变量size指向数组0位置上
2.  当执行push操作时将添加的num加到size指的位置上，然后size++
3.  当执行peek操作时只需要返回 size-1 位置上的数。
4.  当执行pop操作时，返回 --size 上的数即可。

##### （二）数组实现大小固定的队列思路 #####

1.  创建三个变量size，start，end 指向数组0位置上。其中size记录队列中的元素，start执行队列的第一个元素，end指向下一个可以添加元素的位置
2.  当执行push操作时，size++，将元素添加到end指向的位置。然后判断end是否溢出，即数组长度为3，end执行了第4个位置时候，将end置为0，即`end = end == arr.length - 1 ? 0 : end + 1;`
3.  当执行pop操作时，size–，准备个临时变量保存要返回的队列头元素，然后判断start+1后是否超过最后一个位置，超过置为0，即`start = start == arr.length - 1 ? 0 : start + 1;`，返回临时变量即可。
4.  当执行peek操作时，返回start指向的元素即可。

##### （三）代码实现 #####

package class_03;
    
    
    public class Array_To_Stack_Queue {
        
    
        public static class ArrayStack {
        
            private Integer[] arr;
            private Integer size;
    
            public ArrayStack(int initSize) {
        
                if (initSize < 0) {
        
                    throw new IllegalArgumentException("The init size is less than 0");
                }
                arr = new Integer[initSize];
                size = 0;
            }
    
    
            public void push(int obj) {
        
                if (size == arr.length) {
        
                    throw new ArrayIndexOutOfBoundsException("The queue is full");
                }
                arr[size++] = obj;
            }
    
            public Integer peek() {
        
                if (size == 0) {
        
                    throw new ArrayIndexOutOfBoundsException("The queue is null");
                }
                return arr[size - 1];
            }
    
            public Integer pop() {
        
                if (size == 0) {
        
                    throw new ArrayIndexOutOfBoundsException("The queue is null");
                }
                return arr[--size];
            }
    
    
        }
    
        public static class ArrayQueue {
        
            private Integer start;
            private Integer end;
            private Integer size;
            private Integer[] arr;
    
            public ArrayQueue(int initSize) {
        
                if (initSize < 0) {
        
                    System.out.println("initSize不能小于0");
                    return;
                }
                start = 0;
                end = 0;
                size = 0;
                arr = new Integer[initSize];
            }
    
            public void push(int num) {
        
                if (size == arr.length) {
        
                    System.out.println("队列满");
                }
                size++;
                arr[end] = num;
                end = end == arr.length - 1 ? 0 : end + 1;
            }
    
            public Integer pop() {
        
                if (size == 0) {
        
                    return null;
                }
                size--;
                int temp = arr[start];
                start = start == arr.length - 1 ? 0 : start + 1;
                return temp;
            }
    
            public Integer peek() {
        
                if (size == 0) {
        
                    return null;
                }
                return arr[start];
            }
        }
    
        public static void main(String[] args) {
        
    
        }
    }

--------------------

### 2. 实现一个特殊的栈，在实现栈的基础功能上，再实现返回栈中最小元素的操作 ###

##### （一）思路分析 #####

以myStack2为例

1.  准备两个栈，一个用来添加数据stackData，另外一个用来存放最小值stackMin
2.  当执行push操作时，如果最小栈为null，则直接将添加元素添加到最小栈，否则peek出最小栈中的元素和添加元素相比，当添加元素小时则添加进stackMin，否则添加peek出的元素。
3.  当执行pop操作时，直接弹出stackMin和stackData栈顶元素

##### （二）代码实现 #####

public class GetMinStack {
        
        public static class MyStack1 {
        
            private Stack<Integer> stackData;
            private Stack<Integer> stackMin;
    
            public MyStack1() {
        
                this.stackData = new Stack<Integer>();
                this.stackMin = new Stack<Integer>();
            }
    
            public void push(int newNum) {
        
                if (this.stackMin.isEmpty()) {
        
                    this.stackMin.push(newNum);
                } else if (newNum <= this.getmin()) {
        
                    this.stackMin.push(newNum);
                }
                this.stackData.push(newNum);
            }
    
            public int pop() {
        
                if (this.stackData.isEmpty()) {
        
                    throw new RuntimeException("Your stack is empty.");
                }
                int value = this.stackData.pop();
                if (value == this.getmin()) {
        
                    this.stackMin.pop();
                }
                return value;
            }
    
            public int getmin() {
        
                if (this.stackMin.isEmpty()) {
        
                    throw new RuntimeException("Your stack is empty.");
                }
                return this.stackMin.peek();
            }
        }
    
        public static class MyStack2 {
        
            private Stack<Integer> stackData;
            private Stack<Integer> stackMin;
    
            public MyStack2() {
        
                this.stackData = new Stack<Integer>();
                this.stackMin = new Stack<Integer>();
            }
    
            public void push(int newNum) {
        
                if (this.stackMin.isEmpty()) {
        
                    this.stackMin.push(newNum);
                } else if (newNum < this.getmin()) {
        
                    this.stackMin.push(newNum);
                } else {
        
                    int newMin = this.stackMin.peek();
                    this.stackMin.push(newMin);
                }
                this.stackData.push(newNum);
            }
    
            public int pop() {
        
                if (this.stackData.isEmpty()) {
        
                    throw new RuntimeException("Your stack is empty.");
                }
                this.stackMin.pop();
                return this.stackData.pop();
            }
    
            public int getmin() {
        
                if (this.stackMin.isEmpty()) {
        
                    throw new RuntimeException("Your stack is empty.");
                }
                return this.stackMin.peek();
            }
        }
    
        public static void main(String[] args) {
        
            MyStack1 stack1 = new MyStack1();
            stack1.push(3);
            System.out.println(stack1.getmin());
            stack1.push(4);
            System.out.println(stack1.getmin());
            stack1.push(1);
            System.out.println(stack1.getmin());
            System.out.println(stack1.pop());
            System.out.println(stack1.getmin());
    
            System.out.println("=============");
    
            MyStack1 stack2 = new MyStack1();
            stack2.push(3);
            System.out.println(stack2.getmin());
            stack2.push(4);
            System.out.println(stack2.getmin());
            stack2.push(1);
            System.out.println(stack2.getmin());
            System.out.println(stack2.pop());
            System.out.println(stack2.getmin());
        }
    }

--------------------

### 3. 如果仅用栈结构实现队列结构和如何仅用队列结构实现栈结构 ###

思路  
（一）用栈结构实现队列结构

1.  由队列先进先出，栈后进先出知道。我们可以用两个栈实现队列。创建两个栈，分别为stackPush（用来添加元素），stackPop（用来弹出元素）
2.  当执行push操作时，直接把元素添加进stackPush栈即可。
3.  当执行poll，peek操作时，当stackPop为null，且stackPush不为null时，将stackPush元素全部添加到stackPop里，然后返回栈顶元素即可。

（二）用队列结构实现栈结构  
4. 由队列先进先出，栈后进先出知道。我们可以用两个队列实现栈。创建两个队列分别为queue，help，queue队列用来存放元素，help用来辅助。  
5. 当执行push操作时，直接添加到queue队列即可。  
6. 当执行pop，peek操作时，把queue队列中的元素移到help栈，queue只剩下一个即为要返回的数据。

（三）代码实现

import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Stack;
    
    public class Code_03_StackAndQueueConvert {
        
    
    	public static class TwoStacksQueue {
        
    		private Stack<Integer> stackPush;
    		private Stack<Integer> stackPop;
    
    		public TwoStacksQueue() {
        
    			stackPush = new Stack<Integer>();
    			stackPop = new Stack<Integer>();
    		}
    
    		public void push(int pushInt) {
        
    			stackPush.push(pushInt);
    		}
    
    		public int poll() {
        
    			if (stackPop.empty() && stackPush.empty()) {
        
    				throw new RuntimeException("Queue is empty!");
    			} else if (stackPop.empty()) {
        
    				while (!stackPush.empty()) {
        
    					stackPop.push(stackPush.pop());
    				}
    			}
    			return stackPop.pop();
    		}
    
    		public int peek() {
        
    			if (stackPop.empty() && stackPush.empty()) {
        
    				throw new RuntimeException("Queue is empty!");
    			} else if (stackPop.empty()) {
        
    				while (!stackPush.empty()) {
        
    					stackPop.push(stackPush.pop());
    				}
    			}
    			return stackPop.peek();
    		}
    	}
    
    	public static class TwoQueuesStack {
        
    		private Queue<Integer> queue;
    		private Queue<Integer> help;
    
    		public TwoQueuesStack() {
        
    			queue = new LinkedList<Integer>();
    			help = new LinkedList<Integer>();
    		}
    
    		public void push(int pushInt) {
        
    			queue.add(pushInt);
    		}
    
    		public int peek() {
        
    			if (queue.isEmpty()) {
        
    				throw new RuntimeException("Stack is empty!");
    			}
    			while (queue.size() != 1) {
        
    				help.add(queue.poll());
    			}
    			int res = queue.poll();
    			help.add(res);
    			swap();
    			return res;
    		}
    
    		public int pop() {
        
    			if (queue.isEmpty()) {
        
    				throw new RuntimeException("Stack is empty!");
    			}
    			while (queue.size() > 1) {
        
    				help.add(queue.poll());
    			}
    			int res = queue.poll();
    			swap();
    			return res;
    		}
    
    		private void swap() {
        
    			Queue<Integer> tmp = help;
    			help = queue;
    			queue = tmp;
    		}
    
    	}
    
    }