赞
踩
栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈 顶,另一端称为栈底。栈中的数据元素遵守先进后出,后进先出的原则(LIFO——Last In First Out)。
举几个栈在现实生活中的例子,如:羽毛球放进羽毛球筒里,第一个放的最后一个拿,而最后放的最先拿到。
再比如,子弹装入弹匣,最先装的最后打出,而最后装的,最先打出。
方法 | 功能 |
Stack() | 构造一个空的栈 |
E push(E e) | 将e入栈,并返回e |
E pop() | 将栈顶元素出栈并返回 |
E peek() | 获取栈顶元素,并且该栈顶元素不动 |
int size() | 获取栈中有效元素个数 |
boolean empty() | 检测栈是否为空 |
对比其他的数据结构,可以发现栈是一种较为简单的数据结构,主要特征便是先进后出,里面的方法也较其他数据结构数量更少。
- import java.util.Stack;
-
- public class Text {
- public static void main(String[] args) {
- Stack<Integer> stack = new Stack<>();
- stack.push(0);
- stack.push(1);
- stack.push(2);
- stack.push(3);
- stack.push(4);
- stack.push(5);
- System.out.println(stack.size());
- System.out.print(stack.pop()+" ");
- System.out.print(stack.pop()+" ");
- System.out.print(stack.pop()+" ");
- System.out.print(stack.peek()+" ");//返回栈顶元素,但该元素依旧留在栈顶
- System.out.print(stack.peek()+" ");
- System.out.print(stack.pop()+" ");//返回栈顶元素,并将该元素出栈
- System.out.print(stack.pop()+" ");
- System.out.println(stack.pop()+" ");
- System.out.println(stack.empty());
- }
- }
输出:
6
5 4 3 2 2 2 1 0
true
栈的实现,可以使用数组,那就是个顺序栈,而如果使用链表,那就是链式栈,而若是使用单链表的话,拿就只能头插头删,只有这样的时间复杂度才都是 O(1);而如果使用的是双向链表的话,也是头插头删:
- public static void main(String[] args) {
- LinkedList<Integer> stack = new LinkedList<>();
- stack.push(1);
- stack.push(2);
- stack.push(3);
- stack.push(4);
- System.out.println(stack.peek());
- System.out.println(stack.pop());
- System.out.println(stack.pop());
- System.out.println(stack.pop());
- System.out.println(stack.pop());
- }
输出:
4
4
3
2
1
在 LinkedList 类的源代码中,也有跟栈一样的方法,发现 push 是头插,且 pop 也是头删:
下面的一个模拟实现,是用数组来实现的。
- import java.util.Arrays;
-
- public class MyStack {
- public int[] arr;
- public int usedSize;
-
- public MyStack() {
- arr = new int[10];
- }
-
- public int push(int data){
- if(isFull()){
- arr = Arrays.copyOf(arr,arr.length + 10);
- }
- arr[usedSize] = data;
- usedSize++;
- return data;
- }
-
- private boolean isFull(){
- return usedSize == arr.length;
- }
-
- public boolean isEmpty(){
- return usedSize == 0;
- }
- public int pop(){
- if(isEmpty()){
- throw new EmptyStackException("The Stack is empty!");
- }
- // int val = usedSize-1;
- // usedSize--;
- // return arr[val];
- //又或者写成如下更加简便的形式:
- return arr[--usedSize];
- }
-
- public int peek(){
- if(isEmpty()){
- throw new EmptyStackException("The Stack is empty!");
- }
- return arr[usedSize-1];
- }
-
- public int size(){
- return usedSize;
- }
- }
题目 最小栈中:
在 push 函数中,else 的代码块中,if(val <= minStack.peek()) ,也就是说,stack 里如果出现相同的最小元素,也要存放到 minStack 中,
而在 pop 函数中, int val = stack.pop (拆箱了),后面if 判断 就可以写成 if(val == minStack.peek())
这个题目,采用以下两种方法来求解:
- //递归打印链表
- public static void playList(Node pHead){
- if(pHead == null){
- return ;
- }
-
- if(pHead.next == null){
- System.out.println(pHead.val);
- return ;
- }
-
- playList(pHead.next);
- System.out.println(pHead.val);
- }
- //使用栈来逆着打印单向链表
- public static void playList1(){
- Stack<Node> stack = new Stack<>();
- Node cur = head;
- while(cur != null){
- stack.push(cur);
- cur = cur.next;
- }
- while(!stack.isEmpty()){
- Node temp = stack.pop();
- System.out.print(temp.val+" ");
- }
- System.out.println();
- }
给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号
- class Solution {
- public boolean isValid(String s) {
- Stack<Character> stack = new Stack<>();
- for(int i = 0; i < s.length() ;i++){
- char ch = s.charAt(i);
- if(ch == '(' || ch == '{'||ch == '['){
- stack.push(ch);
- }else{
- if(stack.empty()){
- return false;
- }
- char ch2 = stack.peek();
- if(ch == ')' && ch2 == '(' || ch == '}' && ch2 == '{' || ch == ']' && ch2 == '['){
- stack.pop();
- }else{
- return false;
- }
- }
- }
-
- if(!stack.empty()){
- return false;
- }
-
- return true;
- }
- }
给你一个字符串数组 tokens ,表示一个根据 逆波兰表达式 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
- class Solution {
- public boolean isOperation(String x){
- if(x.equals("+") || x.equals("-") || x.equals("*") || x.equals("/")){
- return true;
- }
- return false;
- }
- public int evalRPN(String[] tokens) {
- Stack<Integer> stack = new Stack<>();
- for(String x : tokens){
- if(isOperation(x)){
- int num2 = stack.pop();
- int num1 = stack.pop();
- switch(x){
- case "+":
- stack.push(num1 + num2);
- break;
- case "-":
- stack.push(num1 - num2);
- break;
- case "*":
- stack.push(num1 * num2);
- break;
- case "/":
- stack.push(num1 / num2);
- break;
- }
-
- }else{
- stack.push(Integer.parseInt(x));
- }
- }
- return stack.pop();
- }
- }
输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。
- import java.util.ArrayList;
- import java.util.Stack;
-
- public class Solution {
- public boolean IsPopOrder(int [] pushA,int [] popA) {
- int j = 0;
- Stack<Integer> stack = new Stack<>();
- for(int i = 0; i < pushA.length;i++){
- stack.push(pushA[i]);
- while(j < popA.length && !stack.empty() && stack.peek().equals(popA[j])){
- stack.pop();
- j++;
- }
- }
- if(!stack.empty()){
- return false;
- }
- return true;
- }
- }
注意:stack.peek() == popA[j] 最好修改成 stack.peek().equals(popA[j])
设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。
- class MinStack {
- private Stack<Integer> stack ;
- private Stack<Integer> minStack;
-
-
- public MinStack() {
- stack = new Stack<>();
- minStack = new Stack<>();
-
- }
-
- public void push(int val) {
- stack.push(val);
- if(minStack.empty()){
- minStack.push(val);
- }else{
- if(val <= minStack.peek()){
- minStack.push(val);
- }
- }
- }
-
- public void pop() {
- if(!stack.empty()){
- Integer val = stack.pop();
- if(val.equals(minStack.peek())){
- minStack.pop();
- }
- }
-
- }
-
- public int top() {
- if(!stack.empty()){
- return stack.peek();
- }
- return -1;
- }
-
- public int getMin() {
- return minStack.peek();
-
- }
- }
栈是一种先进后出的数据结构,虚拟机栈是运行程序时的内存,而方法在虚拟机栈开辟的内存就叫栈帧。
队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出的原则。(FIFO——First In First Out)
入队列:进行插入操作的一端称为队尾(Tail/Rear) 出队列:进行删除操作的一端称为队头 (Head/Front)
在Java中,Queue是个接口,底层是通过链表实现的。
方法 | 功能 |
boolean offer(E e) | 入队列 |
E poll() | 出队列 |
E peek() | 获取队头元素 |
int size() | 获取队列有效元素个数 |
boolean isEmpty() | 检测队列是否为空 |
注意:Queue是个接口,在实例化时必须实例化LinkedList的对象,因为LinkedList实现了Queue接口。
- public static void main(String[] args) {
- Queue<Integer> queue = new LinkedList<>();
- queue.offer(6);
- queue.offer(7);
- queue.offer(8);
- queue.offer(9);
- queue.offer(10);
- System.out.println(queue.toString());
- System.out.println(queue.size());
- System.out.println(queue.peek());
- System.out.println(queue.poll());
- System.out.println(queue.poll());
- System.out.println(queue.poll());
- System.out.println(queue.poll());
- System.out.println(queue.poll());
- }
输出:
[6, 7, 8, 9, 10]
5
6
6
7
8
9
10
LinkedList 重写 Queue 里面的方法,发现 offer 是尾插:
而 poll 是头删:
单链表实现队列,首先得记录尾部,并且只能尾部插入,头部删除,而不能头部插入,尾部删除,因为此时,尾部的前一个节点不可知。
- public class MyQueue {
- static class Node{
- public int val;
- public Node next;
-
- public Node(int val) {
- this.val = val;
- }
- }
-
- public Node head;
- public Node last;
- public int usedSize;
-
- //入队列
- public void offer(int data){
- Node node = new Node(data);
- //队列为空时:
- if(head == null){
- head = node;
- last = node;
- }else{
- //队列不为空时,单向链表的尾部入队列:
- last.next = node;
- last = node;
- }
- usedSize++;
- }
-
- //出队列
- public int poll(){
- //队列为空时:
- if(empty()){
- throw new EmptyQueueException("队列为空,出队列失败!");
- }
- int val = head.val;
- //队列只有一个元素时:
- if(head.next == null){
- last = last.next;
- }
- head = head.next;
- usedSize--;
- return val;
- }
-
- public int peek(){
- if(empty()){
- throw new EmptyQueueException("队列为空,队头的首个元素获取失败!");
- }
- return head.val;
- }
-
- public boolean empty(){
- return usedSize == 0;
- }
-
- public int getUsedSize(){
- return usedSize;
- }
- }
- public class Text {
- public static void main(String[] args) {
- MyQueue myQueue = new MyQueue();
- myQueue.offer(1);
- myQueue.offer(5);
- myQueue.offer(8);
- myQueue.offer(13);
- myQueue.offer(19);
- System.out.println(myQueue.getUsedSize());
- System.out.println(myQueue.peek());
- System.out.println(myQueue.poll());
- System.out.println(myQueue.poll());
- System.out.println(myQueue.poll());
- System.out.println(myQueue.poll());
- System.out.println(myQueue.poll());
- }
- }
输出:
5
1
1
5
8
13
19
而双向链表实现队列,头删尾插 ,或头插尾删的时间复杂度都是 O(1) ,下面的模拟实现,是头插尾删:
- public class MyQueue2 {
- static class Node{
- public int val;
- public Node prev;
- public Node next;
-
- public Node(int val) {
- this.val = val;
- }
- }
- public Node head;
- public Node last;
- public int usedSize;
-
- public void offer(int data){
- Node node = new Node(data);
- if(head == null){
- last = node;
- }else{
- node.next = head;
- head.prev = node;
- }
- head = node;
- usedSize++;
- }
-
- public int poll(){
- if(empty()){
- throw new EmptyQueueException("队列为空,出队列失败!");
- }
- int ret = last.val;
- if(last == head){
- last = null;
- head = null;
- }else{
- last = last.prev;
- last.next.prev = null;
- last.next = null;
- }
- usedSize--;
- return ret;
- }
-
- public int getUsedSize(){
- return usedSize;
- }
- public boolean empty(){
- return usedSize == 0;
- }
-
- public int peek(){
- return last.val;
- }
- }
- public static void main(String[] args) {
- MyQueue2 myQueue2 = new MyQueue2();
- myQueue2.offer(9);
- myQueue2.offer(6);
- myQueue2.offer(4);
- myQueue2.offer(3);
- myQueue2.offer(2);
- System.out.println(myQueue2.getUsedSize());
- System.out.println(myQueue2.peek());
- System.out.println(myQueue2.poll());
- System.out.println(myQueue2.poll());
- System.out.println(myQueue2.poll());
- System.out.println(myQueue2.poll());
- System.out.println(myQueue2.poll());
- }
输出:
5
9
9
6
4
3
2
实际中我们有时还会使用一种队列叫循环队列。如操作系统中,讲解生产者消费者模型时可以就会使用循环队列。 循环队列通常使用数组实现。
如果我们使用数组去实现队列,就会遇到这样一个问题:一旦这个数组满了,即使释放了队列前面的元素,我们也无法插入新的元素。但是使用循环队列,我们能使用这些空间去存储新的值。
循环队列的实现思路:
用 front 和 rear 引用来分别存储队列的头元素和尾部的下一个元素,当队列为空时,front 和 rear 指向数组下标为 0 的位置:
从 rear 位置处插入第一个元素 666 , front 不变,而 rear 往后走一个:
以此类推,将整个队列装满元素:
不知同学们发现没有,数组下标为 7 的位置是空的,但我在上面却说“满”,这是为何?
如果连下标为 7 的地方也放了元素,那么 rear 和 front 又重新指向同一个地方了,那如何与空区别?
上面两个问题,让我来一一解答:
其实判断循环队列是否满了,有很多方法,这里讲解两种。
第一种,牺牲一个空间,为后续判断是否满了做准备。
在这里我们先思考一个问题,循环队列,如何循环呢? 0 -> 1 -> 2 -> 3 - >4 ->5 ->6 -> 7 ->0 ,所以不管对于 front 还是 rear ,下标7 的下一个是 0 ,而不是8 ,也就是说,我们不能再使用 front++ ,或 rear++,而是
front = (front + 1) % arr.length
rear = (rear + 1) % arr.length
而最后一个空间不去用,就是为了区分空和满的状态,空是 front == rear, 而满就是 (rear + 1) % arr.length == front ,即 rear 的下一个位置,与 front 相同。此时队列为满,不再添加。除非在头部进行删除,这样 front = (front + 1) % arr.length , front 来到下一个:
这时,又可以在尾部进行添加了。
而第二种判断循环队列是否满的方法,是利用一个 size 变量,来记录队列已存储的总个数,这时候整个数组都可以放满。
下面的代码实现,是通过牺牲一个空间来判断满否:
- class MyCircularQueue {
- private int[] elem;
- private int front;//表示队列的头
- private int rear;//表示队列的尾
-
- public MyCircularQueue(int k) {
- //如果是以牺牲一个空间来作为判断是否满了的标准,这里可以多申请一个空间
- elem = new int[k+1];
- }
-
- //入队列
- public boolean enQueue(int value) {
- if(isFull()){
- return false;
- }
- elem[rear] = value;
- rear = (rear + 1) % elem.length;
- return true;
- }
-
- //出队列
- public boolean deQueue() {
- if(isEmpty()){
- return false;
- }
- front = (front + 1) % elem.length;
- return true;
- }
-
- public int Front() {
- if(isEmpty()){
- return -1;
- }
- return elem[front];
- }
-
- public int Rear() {
- if(isEmpty()){
- return -1;
- }
- return rear == 0 ? elem[elem.length - 1] :elem[rear - 1];
- }
-
- public boolean isEmpty() {
- return rear == front;
- }
-
- public boolean isFull() {
- return (rear + 1) % elem.length == front;
- }
- }
双端队列(deque)是指允许两端都可以进行入队和出队操作的队列,deque 是 “double ended queue” 的简称。 那就说明元素可以从队头出队和入队,也可以从队尾出队和入队。
申请两个栈:
offer 时,如果是首次 offer,那么指定一个栈用来存放元素入队列,这里是 stack1 入队列,往后入队列就都往 stack1 去放。
poll 时,找到非空的那个栈,这里是 stack2 ,往 stack2 依次放入 stack1 里的所有元素,最后 stack2 栈顶的元素就是队列 poll 的元素。
继续往队列中放元素,放入 stack1 中:
队列中继续删掉 22 和 41,那么 stack2 中依次出栈,为空:
队列继续出队列,由于 stack2 为空,而 stack1 不为空,那么将 stack1 中的元素依次放于 stack2 中,再依次出栈,一直到两个栈都没有元素为止。
- import java.util.Stack;
-
- public class MyQueue {
- private Stack<Integer> stack1 ;
- private Stack<Integer> stack2 ;
-
- public MyQueue() {
- stack1 = new Stack<>();
- stack2 = new Stack<>();
- }
-
- //选择 stack1 存放入队列时的数据
- public void push(int x) {
- stack1.push(x);
- }
-
- //选择 stack2 存放出队列时的数据
- public int pop() {
- if(empty()){
- return -1;
- }
- if(stack2.empty()){
- while(!stack1.empty()){
- stack2.push(stack1.pop());
- }
- }
- return stack2.pop();
-
- }
-
- public int peek() {
- if(empty()){
- return -1;
- }
- if(stack2.empty()){
- while(!stack1.empty()){
- stack2.push(stack1.pop());
- }
- }
- return stack2.peek();
- }
-
- public boolean empty() {
- return stack1.empty() && stack2.empty();
- }
- }
申请两个队列,queue1 和 queue2 :
入栈时,若是首次入栈,则选一个空的队列存放入栈数据即可,这里选择了 queue1 :
出栈时,找到那个非空的队列,如 queue1,队头元素 queue1.size() - 1 次出队列到一个空的队列中,如 queue2。然后让 queue1 中最后一个元素出队列,这就是出栈的元素。
此时若是再入栈,那么将元素入队列到非空的队列中,如 queue2
若是再出栈,便如步骤3 所示。
3、4 反复操作,一直到两个队列为空为止。
- public class MyStack {
- private Queue<Integer> queue1 ;
- private Queue<Integer> queue2 ;
-
- public MyStack() {
- queue1 = new LinkedList<>();
- queue2 = new LinkedList<>();
- }
-
- public void push(int x) {
- if(!queue1.isEmpty()){
- queue1.offer(x);
- }else if(!queue2.isEmpty()){
- queue2.offer(x);
- }else{
- queue1.offer(x);
- }
- }
-
- public int pop() {
- if(empty()){
- return -1;
- }
- if(!queue1.isEmpty()){
- int size = queue1.size();
- for (int i = 0; i < size - 1 ; i++) {
- queue2.offer(queue1.poll());
- }
- return queue1.poll();
- }else{
- int size = queue2.size();
- for (int i = 0; i < size - 1 ; i++) {
- queue1.offer(queue2.poll());
- }
- return queue2.poll();
- }
- }
-
- public int top() {
- if(empty()){
- return -1;
- }
- int val = -1;
- if(!queue1.isEmpty()){
- int size = queue1.size();
-
- for (int i = 0; i < size ; i++) {
- val = queue1.poll();
- queue2.offer( val);
- }
- return val;
- }else{
- int size = queue2.size();
- for (int i = 0; i < size ; i++) {
- val = queue2.poll();
- queue1.offer( val);
- }
- return val;
- }
- }
-
- public boolean empty() {
- return queue1.isEmpty() && queue2.isEmpty();
- }
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。