做公司网站需要注意哪些,wordpress架设教程,绘本馆借阅网站开发,怎么制作表格教程文章目录 一、什么是栈#xff1f;1.1 栈的模拟实现1.2 关于栈的例题 二、什么是队列#xff1f;2.2 队列的模拟实现2.2 关于队列的例题 总结 提示#xff1a;关于栈和队列的实现其实很简单#xff0c;基本上是对之前的顺序表和链表的一种应用#xff0c;代码部分也不难。… 文章目录 一、什么是栈1.1 栈的模拟实现1.2 关于栈的例题 二、什么是队列2.2 队列的模拟实现2.2 关于队列的例题 总结 提示关于栈和队列的实现其实很简单基本上是对之前的顺序表和链表的一种应用代码部分也不难。主要的是对栈和队列的实际运用。
一、什么是栈
可以理解为一个竖过来的数组、顺序表同时这个数组只能将末尾的元素先推出来再推出来前面的元素也就是我们所说的先进后出、后进先出。 栈的实例化
StackE stack new Stack();1.1 栈的模拟实现 自定义的接口规范自定义的类,便于模拟实现
public interface IStack {//放入元素int push(int a);//推出栈顶元素int pop();//查看栈顶元素int peek();//栈是否为空boolean isEmpty(int[] array);//栈中的元素个数int size();//栈中寻找某个元素距离栈顶的距离int search(int a);
} push(int a) — 将元素放入栈中
public int push(int a) {isFull(array);array[useSide] a;return a;}peek() — 查看栈顶元素
public int peek() {try {if(isEmpty(array)){throw new EmptyException(空数组读取异常);}}catch (EmptyException e){e.printStackTrace();}return array[useSide - 1];}pop() — 出栈顶元素
public int pop() {int top peek();useSide--;return top;}isEmpty(int[] array) — 判断栈是否为空
public boolean isEmpty(int[] array) {return array.length useSide;}size() — 得到栈中的元素个数
public int size() {return useSide;}search(int a) — 得到栈中某个元素距离栈顶的距离栈顶元素位置按1来计算
public int search(int a) {int cur useSide - 1;int len 1;while (0 cur){if(a array[cur]){return len;}else {cur--;len;}}return -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);}}Overridepublic int push(int a) {isFull(array);array[useSide] a;return a;}Overridepublic int pop() {int top peek();useSide--;return top;}Overridepublic int peek() {try {if(isEmpty(array)){throw new EmptyException(空数组读取异常);}}catch (EmptyException e){e.printStackTrace();}return array[useSide - 1];}Overridepublic boolean isEmpty(int[] array) {return array.length useSide;}Overridepublic int size() {return useSide;}Overridepublic int search(int a) {int cur useSide - 1;int len 1;while (0 cur){if(a array[cur]){return len;}else {cur--;len;}}return -1;}
}1.2 关于栈的例题
例题1 有效括号
class Solution {public boolean isValid(String s) {StackCharacter stack new Stack();if(s null){return false;}for(int i 0; i s.length(); i){char cur s.charAt(i);if(cur ( || cur { || cur [){stack.push(cur);}else if(cur ) || cur } || cur ]){if(stack.isEmpty()){return false;}if(cur )stack.peek() ( || cur }stack.peek() { || cur ]stack.peek() [){stack.pop();}else{return false;}}else{return false;}}if(stack.isEmpty()){return true;}return false;}
}例题2 逆波兰表达式
public int evalRPN(String[] tokens) {StackString stack new Stack();for(int i 0; i tokens.length; i){if(tokens[i].equals() || tokens[i].equals(-) || tokens[i].equals(*) || tokens[i].equals(/)){int m Integer.parseInt(stack.pop());int n Integer.parseInt(stack.pop());if(tokens[i].equals()){stack.push(String.valueOf(mn));}else if(tokens[i].equals(-)){stack.push(String.valueOf(n-m));}else if(tokens[i].equals(*)){stack.push(String.valueOf(m*n));}else{stack.push(String.valueOf(n/m));}}else{stack.push(tokens[i]);}}return Integer.parseInt(stack.pop());}例题3 最小栈
public StackInteger stack;public StackInteger minStack;public MinStack() {stack new Stack();minStack new Stack();}public void push(int val) {stack.push(val);if(minStack.empty()){minStack.push(val);}else{int m minStack.peek();if(m val){minStack.push(val);}}}public void pop() {if(stack.empty()){return;}int m stack.pop();if(m minStack.peek()){minStack.pop();}}public int top() {if(stack.empty()){return -1;}return stack.peek();}public int getMin() {if(minStack.empty()){return -1;}return minStack.peek();}例题4 栈的压入、弹出序列
public boolean IsPopOrder (int[] pushV, int[] popV) {// write code hereStackInteger stack new Stack();int j 0;for(int i 0; i pushV.length;i){stack.push(pushV[i]);while(!stack.isEmpty() stack.peek() popV[j] j popV.length){stack.pop();j;}}return stack.isEmpty();}二、什么是队列
可以理解为一个双向链表(一个一个节点在排队)同时这个链表只能将队头的元素先推出来再推出来后面的元素也就是我们所说的先进先出、后进后出。 队列的实例化
DequeE stack new ArrayDeque();//双端队列的线性实现
DequeE queue new LinkedList();//双端队列的链式实现2.2 队列的模拟实现 自定义的接口规范自定义的类,便于模拟实现
public interface IQueue {//int offer(int a);int poll();int peek();boolean isEmpty();
}isEmpty() — 判断是否为空队列
Overridepublic boolean isEmpty() {return useSide 0;}offer(int a) — 从队尾放入元素
public int offer(int a) {ListNode listNode new ListNode(a);listNode.val a;if(isEmpty()){head listNode;last listNode;}else {last.next listNode;listNode.pre last;last listNode;}useSide;return a;}peek() — 查看队头元素
public int peek() {try {if(head null){throw new EmptyException(空指针异常访问);}}catch (EmptyException e){e.printStackTrace();}return head.val;}poll() — 推出队头的元素
public int poll() {int fisrt peek();head head.next;useSide --;return fisrt;}代码整合
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;Overridepublic int offer(int a) {ListNode listNode new ListNode(a);listNode.val a;if(isEmpty()){head listNode;last listNode;}else {last.next listNode;listNode.pre last;last listNode;}useSide;return a;}Overridepublic int poll() {int fisrt peek();head head.next;useSide --;return fisrt;}Overridepublic int peek() {try {if(head null){throw new EmptyException(空指针异常访问);}}catch (EmptyException e){e.printStackTrace();}return head.val;}Overridepublic boolean isEmpty() {return useSide 0;}} 2.2 关于队列的例题
例题1 设计循环队列
class MyCircularQueue {public int[] array;int front;int rear;public MyCircularQueue(int k) {array new int[k1];}// 向循环队列插入一个元素。如果成功插入则返回真。public boolean enQueue(int value) {if(isFull()){return false;}array[rear] value;rear (rear1) % array.length;return true;}//从循环队列中删除一个元素。如果成功删除则返回真。public boolean deQueue() {if(isEmpty()){return false;}front (front1) % array.length;return true;}//从队首获取元素。如果队列为空返回 -1 。public int Front() {if(isEmpty()){return -1;}return array[front];}//获取队尾元素。如果队列为空返回 -1 。public int Rear() {if(isEmpty()){return -1;}if(rear 0){return array[array.length - 1];}return array[rear-1];}//检查循环队列是否为空。public boolean isEmpty() {return rear front;}//检查循环队列是否已满。public boolean isFull() {return (rear1) % array.length front;}
}例题2 用队列实现栈
class MyStack {public QueueInteger queue1;public QueueInteger queue2;int size;public MyStack() {queue1 new LinkedList();queue2 new LinkedList();}public void push(int x) {if(queue1.isEmpty() queue2.isEmpty()){queue1.offer(x);size;}else if(!queue1.isEmpty()){queue1.offer(x);size;}else if(!queue2.isEmpty()){queue2.offer(x);size;}}public int pop() {if(queue1.isEmpty() queue2.isEmpty()){return -1;}if(queue1.isEmpty() !queue2.isEmpty()){int cur size - 1;while(cur ! 0){queue1.offer(queue2.poll());cur--;}size--;return queue2.poll();}else if(!queue1.isEmpty() queue2.isEmpty()){int cur size - 1;while(cur ! 0){queue2.offer(queue1.poll());cur--;}size--;return queue1.poll();}return -1;}public int top() {if(queue1.isEmpty() queue2.isEmpty()){return -1;}if(queue1.isEmpty() !queue2.isEmpty()){int cur size - 1;while(cur ! 0){queue1.offer(queue2.poll());cur--;}int m queue2.peek();queue1.offer(queue2.poll());return m;}else if(!queue1.isEmpty() queue2.isEmpty()){int cur size - 1;while(cur ! 0){queue2.offer(queue1.poll());cur--;}int m queue1.peek();queue2.offer(queue1.poll());return m;}return -1;}public boolean empty() {return size 0;}}例题3 用栈实现队列
StackInteger stack1;StackInteger stack2;int size 0;public MyQueue() {stack1 new Stack();stack2 new Stack();}//将元素 x 推到队列的末尾public void push(int x) {stack1.push(x);size;}//从队列的开头移除并返回元素public int pop() {if(empty()){return -1;}if(!stack2.isEmpty()){size--;return stack2.pop();}else if(stack2.isEmpty() !stack1.isEmpty()){while(!stack1.isEmpty()){stack2.push(stack1.pop());}size--;return stack2.pop();}return -1;}//返回队列开头的元素public int peek() {if(empty()){return -1;}if(!stack2.isEmpty()){return stack2.peek();}else if(stack2.isEmpty() !stack1.isEmpty()){while(!stack1.isEmpty()){stack2.push(stack1.pop());}return stack2.peek();}return -1;}//如果队列为空返回 true 否则返回 falsepublic boolean empty() {return size 0;}总结
本篇文章介绍了有关数据结构中的栈和队列的相关内容以及它们的简单实现和简单使用如果有什么不正确的或者不严谨的地方还望指正谢谢大家
