数据布局《栈和队列》

---

提示：关于栈和队列的实现着实很简朴，根本上是对之前的次序表和链表的一种应用，代码部分也不难。重要的是对栈和队列的实际运用。
一、什么是栈？

可以明白为一个竖过来的数组、次序表，同时这个数组只能将末端的元素先推出来，再推出来前面的元素，也就是我们所说的，先辈后出、后进先出。

栈的实例化

1. Stack<E> stack = new Stack<>();

复制代码

1.1 栈的模仿实现

---

自界说的接口，规范自界说的类,便于模仿实现

1. public interface IStack {
2.     //放入元素
3.     int push(int a);
4.     //推出栈顶元素
5.     int pop();
6.     //查看栈顶元素
7.     int peek();
8.     //栈是否为空
9.     boolean isEmpty(int[] array);
10.     //栈中的元素个数
11.     int size();
12.     //栈中寻找某个元素距离栈顶的距离
13.     int search(int a);
14. }

复制代码

---

push(int a) — 将元素放入栈中

1. public int push(int a) {
2.         isFull(array);
3.         array[useSide++] = a;
4.         return a;
5.     }

复制代码

---

peek() — 检察栈顶元素

1. public int peek() {
2.         try {
3.             if(isEmpty(array)){
4.                 throw new EmptyException("空数组读取异常");
5.             }
6.         }catch (EmptyException e){
7.             e.printStackTrace();
8.         }
9.         return array[useSide - 1];
10.     }

复制代码

---

pop() — 出栈顶元素

1. public int pop() {
2.         int top = peek();
3.         useSide--;
4.         return top;
5.     }

复制代码

---

isEmpty(int[] array) — 判定栈是否为空

1. public boolean isEmpty(int[] array) {
2.         return array.length == useSide;
3.     }

复制代码

---

size() — 得到栈中的元素个数

1. public int size() {
2.         return useSide;
3.     }

复制代码

---

search(int a) — 得到栈中某个元素隔断栈顶的隔断，栈顶元素位置按1来盘算

1. public int search(int a) {
2.         int cur = useSide - 1;
3.         int len = 1;
4.         while (0 <= cur){
5.             if(a == array[cur]){
6.                 return len;
7.             }else {
8.                 cur--;
9.                 len++;
10.             }
11.         }
12.         return -1;
13.     }

复制代码

---

代码整合

1. public class MyStack implements IStack{    private int[] array;    public MyStack() {        this.array = new int[10];    }    private int useSide;    private void isFull(int[] check){        if(isEmpty(check)){            array = Arrays.copyOf(check,2*check.length);        }    }    @Override    public int push(int a) {
2.         isFull(array);
3.         array[useSide++] = a;
4.         return a;
5.     }
6.     @Override    public int pop() {
7.         int top = peek();
8.         useSide--;
9.         return top;
10.     }
11.     @Override    public int peek() {
12.         try {
13.             if(isEmpty(array)){
14.                 throw new EmptyException("空数组读取异常");
15.             }
16.         }catch (EmptyException e){
17.             e.printStackTrace();
18.         }
19.         return array[useSide - 1];
20.     }
21.     @Override    public boolean isEmpty(int[] array) {
22.         return array.length == useSide;
23.     }
24.     @Override    public int size() {
25.         return useSide;
26.     }
27.     @Override    public int search(int a) {
28.         int cur = useSide - 1;
29.         int len = 1;
30.         while (0 <= cur){
31.             if(a == array[cur]){
32.                 return len;
33.             }else {
34.                 cur--;
35.                 len++;
36.             }
37.         }
38.         return -1;
39.     }
40. }

复制代码

---

1.2 关于栈的例题

例题1 有效括号

1. class Solution {
2.     public boolean isValid(String s) {
3.         Stack<Character> stack = new Stack<>();
4.         if(s == null){
5.             return false;
6.         }
7.         for(int i = 0; i < s.length(); i++){
8.             char cur = s.charAt(i);
9.             if(cur == '(' || cur == '{' || cur == '['){
10.                 stack.push(cur);
11.             }else if(cur == ')' || cur == '}' || cur == ']'){
12.                 if(stack.isEmpty()){
13.                     return false;
14.                 }
15.                 if(cur == ')'&&stack.peek() == '(' ||
16.                    cur == '}'&&stack.peek() == '{' ||
17.                    cur == ']'&&stack.peek() == '['){
18.                     stack.pop();
19.                 }else{
20.                     return false;
21.                 }
22.             }else{
23.                 return false;
24.             }
25.         }
26.         if(stack.isEmpty()){
27.             return true;
28.         }
29.         return false;
30.     }
31. }

复制代码

---

例题2 逆波兰表达式

1. public int evalRPN(String[] tokens) {
2.         
3.         Stack<String> stack = new Stack<>();
4.         for(int i = 0; i < tokens.length; i++){
5.             if(tokens[i].equals("+") || tokens[i].equals("-") || tokens[i].equals("*") || tokens[i].equals("/")){
6.                 int m = Integer.parseInt(stack.pop());
7.                 int n = Integer.parseInt(stack.pop());
8.                 if(tokens[i].equals("+")){
9.                     stack.push(String.valueOf(m+n));
10.                 }else if(tokens[i].equals("-")){
11.                     stack.push(String.valueOf(n-m));
12.                 }else if(tokens[i].equals("*")){
13.                     stack.push(String.valueOf(m*n));
14.                 }else{
15.                     stack.push(String.valueOf(n/m));
16.                 }
17.             }else{
18.                 stack.push(tokens[i]);
19.             }
20.         }
21.         return Integer.parseInt(stack.pop());
22.     }

复制代码

---

例题3 最小栈

1. public Stack<Integer> stack;
2.     public Stack<Integer> minStack;
4.     public MinStack() {
5.         stack = new Stack<>();
6.         minStack = new Stack<>();
7.     }
8.    
9.     public void push(int val) {
10.         stack.push(val);
11.         if(minStack.empty()){
12.             minStack.push(val);
13.         }else{
14.             int m = minStack.peek();
15.             if(m >= val){
16.                 minStack.push(val);
17.             }
18.         }
19.     }
20.    
21.     public void pop() {
22.         if(stack.empty()){
23.             return;
24.         }
25.         int m = stack.pop();
26.         if(m == minStack.peek()){
27.             minStack.pop();
28.         }
29.     }
30.    
31.     public int top() {
32.         if(stack.empty()){
33.             return -1;
34.         }
35.         return stack.peek();
36.     }
37.    
38.     public int getMin() {
39.         if(minStack.empty()){
40.             return -1;
41.         }
42.         return minStack.peek();
43.     }

复制代码

---

例题4 栈的压入、弹出序列

1. public boolean IsPopOrder (int[] pushV, int[] popV) {
2.         // write code here
3.         Stack<Integer> stack = new Stack<>();
4.         int j = 0;
5.         for(int i = 0; i < pushV.length;i++){
6.             stack.push(pushV[i]);
7.             while(!stack.isEmpty() && stack.peek() == popV[j] && j < popV.length){
8.                 stack.pop();
9.                 j++;
10.             }
11.         }
12.         
13.         return stack.isEmpty();
14.     }

复制代码

---

二、什么是队列？

可以明白为一个双向链表(一个一个节点在列队)，同时这个链表只能将队头的元素先推出来，再推出来反面的元素，也就是我们所说的，先辈先出、后进后出。

队列的实例化

1. Deque<E> stack = new ArrayDeque<>();//双端队列的线性实现
2. Deque<E> queue = new LinkedList<>();//双端队列的链式实现

复制代码

---

2.2 队列的模仿实现

---

自界说的接口，规范自界说的类,便于模仿实现

1. public interface IQueue {
2.     //
3.     int offer(int a);
4.     int poll();
5.     int peek();
6.     boolean isEmpty();
7. }

复制代码

---

isEmpty() — 判定是否为空队列

1. @Override
2.     public boolean isEmpty() {
3.         return useSide == 0;
4.     }

复制代码

---

offer(int a) — 从队尾放入元素

1. public int offer(int a) {
2.         ListNode listNode = new ListNode(a);
3.         listNode.val = a;
4.         if(isEmpty()){
5.             head = listNode;
6.             last = listNode;
7.         }else {
8.             last.next = listNode;
9.             listNode.pre = last;
10.             last = listNode;
11.         }
12.         useSide++;
13.         return a;
14.     }

复制代码

---

peek() — 检察队头元素

1. public int peek() {
2.         try {
3.             if(head == null){
4.                 throw new EmptyException("空指针异常访问");
5.             }
6.         }catch (EmptyException e){
7.             e.printStackTrace();
8.         }
9.         return head.val;
10.     }

复制代码

---

poll() — 推出队头的元素

1. public int poll() {
2.         int fisrt = peek();
3.         head = head.next;
4.         useSide --;
5.         return fisrt;
6.     }

复制代码

---

代码整合

1. public class MyQueue implements IQueue{    static class ListNode{        int val;        ListNode pre;        ListNode next;        public ListNode(int val) {            this.val = val;        }    }    private ListNode head;    private ListNode last;    private int useSide;    @Override    public int offer(int a) {
2.         ListNode listNode = new ListNode(a);
3.         listNode.val = a;
4.         if(isEmpty()){
5.             head = listNode;
6.             last = listNode;
7.         }else {
8.             last.next = listNode;
9.             listNode.pre = last;
10.             last = listNode;
11.         }
12.         useSide++;
13.         return a;
14.     }
15.     @Override    public int poll() {
16.         int fisrt = peek();
17.         head = head.next;
18.         useSide --;
19.         return fisrt;
20.     }
21.     @Override    public int peek() {
22.         try {
23.             if(head == null){
24.                 throw new EmptyException("空指针异常访问");
25.             }
26.         }catch (EmptyException e){
27.             e.printStackTrace();
28.         }
29.         return head.val;
30.     }
31.     @Override
32.     public boolean isEmpty() {
33.         return useSide == 0;
34.     }
35. }

复制代码

---

2.2 关于队列的例题

例题1 筹划循环队列

1. class MyCircularQueue {
2.     public int[] array;
3.     int front;
4.     int rear;
6.     public MyCircularQueue(int k) {
7.         array = new int[k+1];
8.     }
9.     // 向循环队列插入一个元素。如果成功插入则返回真。
10.     public boolean enQueue(int value) {
11.         if(isFull()){
12.             return false;
13.         }
14.         array[rear] = value;
15.         rear = (rear+1) % array.length;
16.         return true;
17.     }
18.     //从循环队列中删除一个元素。如果成功删除则返回真。
19.     public boolean deQueue() {
20.         if(isEmpty()){
21.             return false;
22.         }
23.         front = (front+1) % array.length;
24.         return true;
25.     }
26.     //从队首获取元素。如果队列为空，返回 -1 。
27.     public int Front() {
28.         if(isEmpty()){
29.             return -1;
30.         }
31.         return array[front];
32.     }
33.     //获取队尾元素。如果队列为空，返回 -1 。
34.     public int Rear() {
35.         if(isEmpty()){
36.             return -1;
37.         }
38.         if(rear == 0){
39.             return array[array.length - 1];
40.         }
41.         return array[rear-1];
42.     }
43.     //检查循环队列是否为空。
44.     public boolean isEmpty() {
45.         return rear == front;
46.     }
47.     //检查循环队列是否已满。
48.     public boolean isFull() {
49.         return (rear+1) % array.length == front;
50.     }
51. }

复制代码

---

例题2 用队列实现栈

1. class MyStack {
2.     public Queue<Integer> queue1;
3.     public Queue<Integer> queue2;
4.     int size;
5.     public MyStack() {
6.         queue1 = new LinkedList<>();
7.         queue2 = new LinkedList<>();
8.     }
9.    
10.     public void push(int x) {
11.         if(queue1.isEmpty() && queue2.isEmpty()){
12.             queue1.offer(x);
13.             size++;
14.         }else if(!queue1.isEmpty()){
15.             queue1.offer(x);
16.             size++;
17.         }else if(!queue2.isEmpty()){
18.             queue2.offer(x);
19.             size++;
20.         }
21.     }
22.    
23.     public int pop() {
24.         if(queue1.isEmpty() && queue2.isEmpty()){
25.             return -1;
26.         }
27.         if(queue1.isEmpty() && !queue2.isEmpty()){
28.             int cur = size - 1;
29.             while(cur != 0){
30.                 queue1.offer(queue2.poll());
31.                 cur--;
32.             }
33.             size--;
34.             return queue2.poll();
35.         }else if(!queue1.isEmpty() && queue2.isEmpty()){
36.             int cur = size - 1;
37.             while(cur != 0){
38.                 queue2.offer(queue1.poll());
39.                 cur--;
40.             }
41.             size--;
42.             return queue1.poll();
43.         }
44.         return -1;
45.     }
46.    
47.     public int top() {
48.         if(queue1.isEmpty() && queue2.isEmpty()){
49.             return -1;
50.         }
51.         if(queue1.isEmpty() && !queue2.isEmpty()){
52.             int cur = size - 1;
53.             while(cur != 0){
54.                 queue1.offer(queue2.poll());
55.                 cur--;
56.             }
57.             int m = queue2.peek();
58.             queue1.offer(queue2.poll());
59.             return m;
60.         }else if(!queue1.isEmpty() && queue2.isEmpty()){
61.             int cur = size - 1;
62.             while(cur != 0){
63.                 queue2.offer(queue1.poll());
64.                 cur--;
65.             }
66.             int m = queue1.peek();
67.             queue2.offer(queue1.poll());
68.             return m;
69.         }
70.         return -1;
71.     }
72.    
73.     public boolean empty() {
74.         return size == 0;
75.     }
77. }

复制代码

---

例题3 用栈实现队列

1. Stack<Integer> stack1;
2.     Stack<Integer> stack2;
3.     int size = 0;
5.     public MyQueue() {
6.         stack1 = new Stack<>();
7.         stack2 = new Stack<>();
8.     }
9.     //将元素 x 推到队列的末尾
10.     public void push(int x) {
11.         stack1.push(x);
12.         size++;
13.     }
14.     //从队列的开头移除并返回元素
15.     public int pop() {
16.         if(empty()){
17.             return -1;
18.         }
19.         if(!stack2.isEmpty()){
20.             size--;
21.             return stack2.pop();
22.         }else if(stack2.isEmpty() && !stack1.isEmpty()){
23.             while(!stack1.isEmpty()){
24.                 stack2.push(stack1.pop());
25.             }
26.             size--;
27.             return stack2.pop();
28.         }
29.         return -1;
30.     }
31.     //返回队列开头的元素
32.     public int peek() {
33.         if(empty()){
34.             return -1;
35.         }
36.         if(!stack2.isEmpty()){
37.             return stack2.peek();
38.         }else if(stack2.isEmpty() && !stack1.isEmpty()){
39.             while(!stack1.isEmpty()){
40.                 stack2.push(stack1.pop());
41.             }
42.             return stack2.peek();
43.         }
44.         return -1;
45.     }
46.     //如果队列为空，返回 true ；否则，返回 false
47.     public boolean empty() {
48.         return size == 0;
49.     }

复制代码

---

总结

本篇文章先容了有关数据布局中的栈和队列的相干内容，以及它们的简质朴现，和简朴利用，如果有什么不准确的大概不严谨的地方，还望指正，谢谢各人！

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！qidao123.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金