精华内容
下载资源
问答
  • 栈和队列是数组和链表的...栈和队列的重点在其结构特性,栈和队列底层不论是数组实现还是链表实现都不重要,因为同属于线性存储结构,可以通过数组实现一个栈结构,也可以使用链表实现一个栈结构,同样队列也是如此。

    一、概述

    栈和队列是数组和链表的高级封装的数据结构。

    栈和队列的重点在其结构特性,栈和队列的底层不论是数组实现还是链表实现都不重要,因为同属于线性存储结构,可以通过数组实现一个栈结构,也可以使用链表实现一个栈结构,同样队列也是如此。

    二、实现

    2.1 栈

    2.1.1栈结构的特点

    • 栈的结构特性是:元素先进后出(First In Last Out,简称FILO)
    • 我们将元素放入栈结构中的操作称之为元素入栈
    • 将元素从栈结构中取出的操作称之为元素出栈
    • 将最先进入栈结构中的元素称之为栈底元素,这个方向同时称之为栈底
    • 将最后进入栈结构中的元素称之为栈顶元素,这个方法同时称之为栈顶

    2.1.2 Java中的栈结构:Stack

    在Java中存在一个栈结构的实现类,这个类是Stack类;
    Stack类是Vector类的子类,从集成的角度来说,Stack类是List接口的实现类,同样属于Collection接口的实现类之一;
    从这个角度来说,Stack类同样具有List接口下其他实现类类似的功能,能够有序可重复的保存元素;
    但是除了这些特性之外,Stack类还提供了一些额外的方法,能够从数据结构的角度体现出栈结构的特性。

    2.1.3 案例

    1、.数组逆序

    import java.util.Arrays;
    import java.util.Stack;
    
    public class ArrayReverseByStack {
    	
    	/**
    	 * 使用栈结构实现数组元素逆序
    	 * @param array 参数数组
    	 */
    	public void reverse(int[] array) {
    		
    		//[1]创建一个栈结构,用来逆序数组中的元素
    		Stack<Integer> reverseStack = new Stack<>();
    		
    		//[2]将数组中全部元素入栈
    		for(int i = 0; i < array.length; i++) {
    			reverseStack.push(array[i]);
    		}
    		
    		//[3]将栈结构中的所有元素出栈,出栈过程就是讲数组中元素逆序的过程
    		for(int i = 0; i < array.length; i++) {
    			array[i] = reverseStack.pop();
    		}
    		
    	}
    	
    	public static void main(String[] args) {
    		
    		int[] array = new int[] {1,3,5,7,9};
    		
    		ArrayReverseByStack arbs = new ArrayReverseByStack();
    		arbs.reverse(array);
    		
    		System.out.println(Arrays.toString(array));
    		
    	}
    	
    }
    

    2、.10进制正整数转2进制

    import java.util.Stack;
    
    public class DecimalToBinary {
    	
    	/**
    	 * 将一个10进制正整数转换为一个2进制字符串并返回
    	 * @param num 作为参数的10进制整数
    	 * @return 10进制整数对应的2进制字符串
    	 */
    	public String toBinary(int num) {
    		
    		//[1]创建一个栈结构,用来存储整除法产生的余数
    		Stack<Integer> binaryStack = new Stack<>();
    		
    		//[2]对参数num进行对2的整除法,直到这个数取值为0为止,将过程中产生的所有余数全部入栈(最后产生的0不用入栈)
    		int remainder = 0;  //创建一个临时变量,用来保存num对2的余数
    		while(num > 0) {
    			remainder = num % 2;
    			binaryStack.push(remainder);  //余数入栈
    			num /= 2;  //别忘了对num除以2,因为上面的步骤只是取余,没有除以2的功能
    		}
    		
    		//[3]将栈中所有余数出栈,出栈过程就是倒排余数的过程
    		String result = "0B";
    		while(!binaryStack.isEmpty()) {  //只要栈结构不是空,就继续元素出栈
    			result += binaryStack.pop();
    		}
    	
    		//[4]返回结果值
    		return result;
    		
    	}
    
    	public static void main(String[] args) {
    		
    		int num = 12;  //12的2进制结构:0b1100
    		
    		DecimalToBinary dtb = new DecimalToBinary();
    		String result = dtb.toBinary(num);
    		System.out.println(result);
    		
    	}
    	
    }

    2.2 队列

    2.2.1 队列的结构特性

    • 队列的结构特性是:元素先进先出(First In First Out,简称FIFO)
    • 队列结构的特征就和现实生活中的排队买东西一样,先来排队的先买,一切先来后到,元素按照进入队列的顺序出队列
    • 我们将元素键入队列的操作,称之为元素入队列
    • 将元素从队列中取出的操作,称之为元素出队列
    • 将元素出队列的一端称之为队头(front)
    • 将元素入队列的一端称之为队尾(rear)

    2.2.2 Java中的队列结构:LinkedLIst

    • Collection接口下,不仅仅有List和Set两大子接口,实际上还存在着一个名为Queue的接口,这个接口从名字上来看,本身就是队列的含义,并且这个接口还有一个子接口名为Deque(双端队列)
    • LinkedList类,一方面实现了List接口,一方面也实现了Deque接口,所以我们可以认为LinkedList本身就是一个通过链表实现的双端队列结构
    • 双端队列是一种两端可以同时元素入队列、出队列的结构,也就是说,两端同为队头和队尾

    同样的,在LinkedList类型中,也提供了一些方法,用来支持队列操作:

    2.2.3 案例

    1、利用两个栈实现一个队列

    给定元素加入结构顺序:a b c d e
    元素出结构顺序:a b c d e
    这个结构功能等同于一个队列结构,但是内部要求使用两个栈结构实现

    import java.util.Stack;
    
    /**
     * 使用两个栈结构模拟的队列
     */
    public class StackQueue<E> {
    	
    	private Stack<E> s1 = new Stack<>();
    	private Stack<E> s2 = new Stack<>();
    	
    	/**
    	 * 将元素加入这个结构的方法
    	 * @param e 加入结构的元素
    	 */
    	public void add(E e) {
    		
    		//[1]如果栈s2中还有剩余元素,说明上一次的出栈并没有“出干净”,还需要将s2中的元素全部入栈s1当中,保证元素加入结构的相对顺序不变
    		if(!s2.isEmpty()) {
    			while(!s2.isEmpty()) {
    				E tmp = s2.pop();  //s2出栈
    				s1.push(tmp);  //s1入栈
    			}
    		}
    		
    		//[2]如果元素要加入这个结构的话,那么首先将这些元素全部加入栈s1当中
    		s1.push(e);
    		
    	}
    	
    	/**
    	 * 将元素从结构中退出的方法
    	 * @return 退出结构的元素
    	 */
    	public E get() {
    		
    		//[1]如果元素要从结构中退出,那么将栈s1中所有的元素全部出栈,并按照元素出栈顺序加入到栈s2中
    		if(!s1.isEmpty()) {
    			while(!s1.isEmpty()) {
    				E tmp = s1.pop();  //s1出栈
    				s2.push(tmp);  //s2入栈
    			}
    		}
    		
    		//[2]将栈s2中的栈顶元素出栈并返回,这个过程就是元素按照加入结构顺序退出的过程
    		if(!s2.isEmpty()) {
    			return s2.pop();
    		}
    		return null;
    		
    	}
    	
    	public static void main(String[] args) {
    		
    		StackQueue<Character> sq = new StackQueue<>();
    		
    		//加入结构5个元素
    		sq.add('A');
    		sq.add('B');
    		sq.add('C');
    		sq.add('D');
    		sq.add('E');
    		
    		//退出结构3个元素
    		System.out.println(sq.get());
    		System.out.println(sq.get());
    		System.out.println(sq.get());
    		
    		//再次加入结构3个元素
    		sq.add('F');
    		sq.add('G');
    		sq.add('H');
    		
    		//全部元素退出结构
    		System.out.println(sq.get());
    		System.out.println(sq.get());
    		System.out.println(sq.get());
    		System.out.println(sq.get());
    		System.out.println(sq.get());
    		
    	}
    	
    }
    

    2、用两个队列实现一个栈

    给定元素加入结构顺序:a b c d e
    元素出结构顺序:e d c b a
    这个结构功能等同于一个栈结构,但是内部要求使用两个队列结构实现

    步骤(1):将全部加入结构的元素加入队列q1
    步骤(2):当元素e要退出结构的时候,将q1中除了元素e之外的其他元素全部出队列q1,并同时加入队列q2
    步骤(3):将队列q1中的元素e出队列,此时队列q1空
    步骤(4):当元素d要退出结构的时候,将q2中除了元素d之外的其他元素全部出队列q2,并同时加入队列q1
    步骤(5):将队列q2中的元素d出队列,此时队列q2空
    ……
    以此类推,就能够实现元素的倒序输出

    import java.util.LinkedList;
    
    /**
     * 使用两个队列结构模拟的栈
     */
    public class QueueStack<E> {
    
    	private LinkedList<E> l1 = new LinkedList<>();
    	private LinkedList<E> l2 = new LinkedList<>();
    	
    	private LinkedList<E> currentList = l1;  //创建一个队列变量,用来记录当前应该向哪一个队列中添加元素,默认初始情况是向l1中添加元素
    	
    	/**
    	 * 元素加入结构的方法
    	 * @param e 加入结构的元素
    	 */
    	public void add(E e) {
    		
    		//[1]向currentList中添加元素
    		currentList.offer(e);
    		
    	}
    	
    	/**
    	 * 元素退出结构的方法
    	 * @return 退出结构的元素
    	 */
    	public E get() {
    		
    		//[1]将当前用来存储元素的队列中的n个元素的前n-1个元素出队列,并存储到另一个空队列中
    		if(currentList == l1 && !l1.isEmpty()) {
    			while(l1.size() > 1) {
    				E tmp = l1.poll();  //l1出队列
    				l2.offer(tmp);  //l2入队列
    			}
    			
    			//[2]现在队列l1中仅剩一个元素,将这个元素出队列并返回,并且后来的元素全部存储在l2中
    			currentList = l2;
    			return l1.poll();
    			
    		}else if(currentList == l2 && !l2.isEmpty()) {
    			while(l2.size() > 1) {
    				E tmp = l2.poll();  //l2出队列
    				l1.offer(tmp);  //l1如队列
    			}
    			
    			//[2]现在队列l2中仅剩一个元素,将这个元素出队列并返回,并且后来的元素全部存储在l1中
    			currentList = l1;
    			return l2.poll();
    			
    		}else {  //如果两个队列中都没有任何元素,那么直接返回空,方法结束
    			return null;
    		}
    		
    	}
    	
    	public static void main(String[] args) {
    		
    		QueueStack<Character> qs = new QueueStack<>();
    		
    		//相结构中添加5个元素
    		qs.add('A');
    		qs.add('B');
    		qs.add('C');
    		qs.add('D');
    		qs.add('E');
    		
    		//退出结构3个元素
    		System.out.println(qs.get());
    		System.out.println(qs.get());
    		System.out.println(qs.get());
    		
    		//再次追加3个元素
    		qs.add('F');
    		qs.add('G');
    		qs.add('H');
    		
    		//全部元素出结构
    		System.out.println(qs.get());
    		System.out.println(qs.get());
    		System.out.println(qs.get());
    		System.out.println(qs.get());
    		System.out.println(qs.get());
    		
    	}
    	
    }
    

     

     

    展开全文
  • 这里可以先回忆一下基于动态数组实现的栈和队列,无论是底层是链表还是动态数组,栈和队列的接口都是一致的。 首先,我们一起来看以前定义的栈的接口 public interface StackInterface&lt;E&gt; { E ...

    上篇博客和大家分享了java的链表实现,这篇博客将和大家一起分享基于链表的栈和队列。这里可以先回忆一下基于动态数组实现的栈和队列,无论是底层是链表还是动态数组,栈和队列的接口都是一致的。

    首先,我们一起来看以前定义的栈的接口

    public interface StackInterface<E> {
    
        E pop();
    
        E peek();
    
        void push(E e);
    
        boolean isEmpty();
    
        int getSize();
    }

    相信大家一定不陌生,接下来,让我们一起看看如何使用链表实现栈,由于我们在链表中已经封装好一些方法,所以实现栈其实是很简单的

    public class LinkedListStack<E> implements StackInterface<E> {
    
        private LinkedList<E> list;
    
        public LinkedListStack() {
            list = new LinkedList<>();
        }
    
        @Override
        public E pop() {
            return list.removeFirst();
        }
    
        @Override
        public E peek() {
            return list.getFist();
        }
    
        @Override
        public void push(E e) {
            list.addFirst(e);
        }
    
        @Override
        public boolean isEmpty() {
            return list.isEmpty();
        }
    
        @Override
        public int getSize() {
            return list.getSize();
        }
    
        @Override
        public String toString() {
            StringBuilder res = new StringBuilder();
            res.append("Stack: top ");
            res.append(list);
            return res.toString();
        }
    }

    既然基于链表的栈已经被轻松拿下,那么队列一定也不会难住我们,我们还是先看以前定义好的队列的接口

    public interface QueueInterface<E> {
    
        int getSize();
    
        boolean isEmpty();
    
        void enqueue(E e);
    
        E dequeue();
    
        E getFront();
    }
    

    同样根据队列的定义,使用我们在链表里封住好的方法

    public class LinkedListQueue<E> implements QueueInterface<E> {
    
        private class Node {
            public E e;
            public Node next;
    
            public Node(E e, Node next) {
                this.e = e;
                this.next = next;
            }
    
            public Node(E e) {
                this(e, null);
            }
    
            public Node() {
                this(null, null);
            }
    
            @Override
            public String toString() {
                return e.toString();
            }
        }
    
        private Node head, tail;
        private int size;
    
        public LinkedListQueue() {
            head = null;
            tail = null;
            size = 0;
        }
    
        @Override
        public int getSize() {
            return size;
        }
    
        @Override
        public boolean isEmpty() {
            return size == 0;
        }
    
        @Override
        public void enqueue(E e) {
            if (tail == null) {
                tail = new Node(e);
                head = tail;
            } else {
                tail.next = new Node(e);
                tail = tail.next;
            }
            size++;
        }
    
        @Override
        public E dequeue() {
            if (isEmpty()) {
                throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
            }
    
            Node retNode = head;
            head = head.next;
            retNode.next = null;
            if (head == null) {
                tail = null;
            }
            size--;
            return retNode.e;
        }
    
        @Override
        public E getFront() {
            if (isEmpty()) {
                throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
            }
            return head.e;
        }
    
        @Override
        public String toString() {
            StringBuilder res = new StringBuilder();
    
            Node cur = head;
            while (cur != null) {
                res.append(cur + "->");
                cur = cur.next;
            }
    
            res.append("NULL tail");
            return res.toString();
        }
    }
    

    这里需要注意的是,我们在链表的尾部添加了一个tail节点,因为队列是先进先出的结构,不同于栈,我们只需要操作头节点就可以了,在入队操作时,如果没有队尾的引用,那么每次都需要遍历整个链表,是O(n)的复杂度,所以引入了tail节点。

    到了这里,同学们对于线性数据结构,应该会有一些新的认识,但是只有线性结构,往往是不够的,下一篇博客,将和大家一起分享一种新的数据结构,树结构。感谢阅读~

    还请需要转载的同学注明出处:https://blog.csdn.net/sinat_33150417/article/details/82492809

    展开全文
  • 栈和队列都是用来保存数据的,无论底层是使用数组还是链表来实现,其基本原理是不变的,那就是栈的特点的先进后出,队列的特点是先进先出。

    @Author:Runsen

    编程的本质来源于算法,而算法的本质来源于数学,编程只不过将数学题进行代码化。 ---- Runsen

    算法,一门既不容易入门,也不容易精通的学问。

    栈和队列都是用来保存数据的,无论底层是使用数组还是链表来实现,其基本原理是不变的,那就是栈的特点的先进后出,队列的特点是先进先出。

    栈 (Stack)是一种后进先出(last in first off,LIFO)的数据结构。线性表是用数组来实现的,对于栈这种只能一头插入删除的线性表来说,用数组下标为0(栈底不变,只需要跟踪栈顶的变化即可)的一端作为栈底比较合适。

    列表封装的这些方法,实现栈这个常用的数据结构比较容易。栈是一种只能在列表一端进出的特殊列表,pop方法正好完美实现:

    In [1]: stack=[1,3,5]
    
    In [2]: stack.append(0) # push元素0到尾端,不需要指定索引
    
    In [3]: stack
    Out[3]: [1, 3, 5, 0]
    
    In [4]: stack.pop() # pop元素,不需指定索引,此时移出尾端元素
    Out[4]: 0
    
    In [5]: stack
    Out[5]: [1, 3, 5]
    

    由此可见Python的列表当做栈用,完全没有问题,push 和 pop 操作的时间复杂度都为 O(1)

    队列

    队列(Queue)则是一种先进先出 (fisrt in first out,FIFO)的结构.。使用顺序表存储队列时,队列元素的出队是在队头,即下标为0的地方,当有元素出队时,出队元素后面的所有元素都需要向前移动,保证队列的队头始终处在下标为0的位置,此时会大大增加时间复杂度。

    使用列表模拟队列,需要借助Python的collections模块中的双端队列deque实现。如下模拟队列的先进先出,后进后出:

    In [1]: from collections import deque
    
    In [2]: queue = [1,3,5]
    
    In [3]: deq = deque(queue)
    
    In [4]: deq.append(0) 
    
    In [5]: deq
    Out[5]: deque([1, 3, 5, 0]) # 后进插入到队列尾部
    
    In [6]: deq.popleft()  
    Out[6]: 1
    
    In [7]: deq
    Out[7]: deque([3, 5, 0])# 先进的先出
    

    LeetCode 第 225题:用队列实现栈

    #使用队列实现栈的下列操作: 
    # push(x) -- 元素 x 入栈 
    # pop() -- 移除栈顶元素 
    # top() -- 获取栈顶元素 
    # empty() -- 返回栈是否为空 
    # 注意: 
    # 你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。 
    # 你所使用的语言也许不支持队列。 你可以使用 list 或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。 
    # 你可以假设所有操作都是有效的(例如, 对一个空的栈不会调用 pop 或者 top 操作)。 
    # Related Topics 栈 设计
    

    根据题意,我们只能使用队列的基本操作,队列因为是先进先出,要实现先进后出的栈。

    无论是用队列实现栈,还是用栈实现队列。常见的解法方法是使用两个队列或者两个栈。

    假设有q1,q2两个队列,我们先初始化队列。

    from collections import deque
    class MyStack:
        def __init__(self):
            """
            Initialize your data structure here.
            """
            self.q1 = deque()
            self.q2 = deque()
    

    push(x) :元素 x 入栈 时和队列添加元素的方法一样。

    压入栈时,加入到q1的末尾,那么q1末尾的元素就是栈顶元素。因此只需要append(x)即可。

    def push(self, x: int) -> None:
        """
        Push element x onto stack.
        """
        self.q1.append(x)
    

    对于pop删除元素,我们可以使用q2保存q1的最后的元素之前的元素,然后将q1的元素进行删除,最后将两个队列进行互换。

    我们需要弹出栈顶元素,也就是q1最后的元素,队列只能是先进先出,我们得用q2把q1出队的元素装着,最后一个出队元素就是栈顶元素。

    因此,代码需要对q1的长度进行判断,如果q1的长度大于1,那么将q1的头部元素添加到q2,直到q1只有最后一个元素。

    def pop(self) -> int:
        """
        Removes the element on top of the stack and returns that element.
        """
        while len(self.q1) > 1:
            self.q2.append(self.q1.popleft())
        tmp = self.q1.popleft()
        self.q2, self.q1 = self.q1, self.q2
        return tmp
    

    判断是否为空,只需要判断q1的队列是否为空。

    def empty(self) -> bool:
        """
        Returns whether the stack is empty.
        """
        return not bool(self.q1)
    

    取栈顶元素。这里其实可以巧妙地解决,我们直接调用pop方法进行删除,在pop进行删除时用一个变量进行保存,还需要对该元素重新进行插入操作。

    def top(self) -> int:
        ans = self.pop()
        self.q1.append(ans)
        return ans
    

    下面就是用队列实现栈完整代码

    from collections import deque
    class MyStack:
        def __init__(self):
            """
            Initialize your data structure here.
            """
            self.q1 = deque()
            self.q2 = deque()
    
    
        def push(self, x: int) -> None:
            """
            Push element x onto stack.
            """
            self.q1.append(x)
    
    
        def pop(self) -> int:
            """
            Removes the element on top of the stack and returns that element.
            """
            while len(self.q1) > 1:
                self.q2.append(self.q1.popleft())
            tmp = self.q1.popleft()
            self.q2,self.q1 = self.q1, self.q2
            return tmp
    
    
        def top(self) -> int:
            """
            Get the top element.
            """
            ans = self.pop()
            self.q1.append(ans)
            return ans
    
    
        def empty(self) -> bool:
            """
            Returns whether the stack is empty.
            """
            return not bool(self.q1)
    
    

    LeetCode 第232题:用栈实现队列

    #使用栈实现队列的下列操作:
    # push(x) -- 将一个元素放入队列的尾部。 
    # pop() -- 从队列首部移除元素。 
    # peek() -- 返回队列首部的元素。 
    # empty() -- 返回队列是否为空。
    # 示例:
    # MyQueue queue = new MyQueue();
    #queue.push(1);
    #queue.push(2);  
    #queue.peek();  // 返回 1
    #queue.pop();   // 返回 1
    #queue.empty(); // 返回 false
    # 说明:
    # 你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。 
    # 你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。 
    # 假设所有操作都是有效的 (例如,一个空的队列不会调用 pop 或者 peek 操作)。
    # Related Topics 栈 设计
    

    最简单的方法使用list表示一个栈,只能使用栈的相关方法,如append(),pop(),s[-1],分别是栈顶追加元素,删除栈顶元素,取出栈顶元素.。

    class MyQueue:
        def __init__(self):
            self.s = []
        def push(self, x: int) -> None:
            self.s.append(x)
        def pop(self) -> int:    
            return self.s.pop(0)
        def peek(self) -> int:
            return self.s[0]
        def empty(self) -> bool:
            return not bool(self.s)
    

    当然也可以使用两个栈,这个是比较复杂的操作,但也是比较常见的算法考点。

    (1)初始化两个栈结构,s1为主栈,s2为辅助栈。

    (2)push往s1末尾添加元素,利用append即可实现。

    (3)pop时候,先将s1元素向s2转移,知道s1只剩下一个元素时候(这就是我们要返回的队列首部元素),然后我们再把2中的元素转移回s1中即可。

    (4)返回队列首部的元素,类似于步骤(3)的操作,唯一不同是这里我们需要将elenment先添加回stack2,然后再将stack2的元素转移回stack1中,因为peek操作不需要删除队列首部元素

    (5)empty判断stack1尺寸即可。

    出队操作首先判断缓存栈s2是否有元素,有的话直接取出s2栈顶元素;若s2为空并且s1中有元素,将s1中元素全部转移到s2中,再取出s2栈顶元素,即可模拟队列出队操作;本例中没有出现s2和s1都为空的情况。

    class MyQueue:
        def __init__(self):
            """
            Initialize your data structure here.
            """
            self.s1 = []
            self.s2 = []
            
        def push(self, x: int) -> None:
            """
            Push element x to the back of queue.
            """
            self.s1.append(x)
    
        def pop(self) -> int:
            """
            Removes the element from in front of queue and returns that element.
            """
            if self.s2:
                return self.s2.pop()
            else:
                if  self.s1 :
                    while self.s1:
                        self.s2.append(self.s1.pop())
                    return self.s2.pop()
    
        def peek(self) -> int:
            """
            Get the front element.
            """
            if self.s2:
                return self.s2[-1]
            else:
                if  self.s1 :
                    while self.s1:
                        self.s2.append(self.s1.pop())
                    return self.s2[-1]
    
        def empty(self) -> bool:
            """
            Returns whether the queue is empty.
            """
            if self.s1 or self.s2:
                return False
            else:
                return True
    
    # Your MyQueue object will be instantiated and called as such:
    # obj = MyQueue()
    # obj.push(x)
    # param_2 = obj.pop()
    # param_3 = obj.peek()
    # param_4 = obj.empty()
    

    本文已收录 GitHub,传送门~ ,里面更有大厂面试完整考点,欢迎 Star。



    展开全文
  • 使用两个队列实现栈

    2018-05-06 15:03:47
    使用两个 队列实现栈参考文章栈的队列的特点栈和队列都是用来保存数据的,无论底层是使用数组还是链表来实现,其基本原理是不变的,那就是栈的特点的先进后出,队列的特点是先进先出。队列的常用方法 isEmpty() 判断...

    使用两个 队列实现栈

    参考文章

    栈的队列的特点

    栈和队列都是用来保存数据的,无论底层是使用数组还是链表来实现,其基本原理是不变的,那就是栈的特点的先进后出,队列的特点是先进先出。

    队列的常用方法

    • isEmpty()

      • 判断队列是否为空
    • size()

      • 返回队列中元素的个数
    • enqueue()

      • 向队列中插入数据
    • dequeue()

      • 从队列中弹出数据并返回
    • peek()

      • 返回队列中第一个数据

    使用队列来实现栈
    使用队列来实现栈的方式其实和通过栈实现队列的方式差不多。用以上方法也是可以的。但是,为了让大家更好的掌握这两种数据结构,再给大家提供另外一种思路。

    上面的队列实现中。插入方法并没有额外的操作,只是在弹出的时候需要做些额度的处理。那么另外一个思路就是在插入的时候做些事情,这样在弹出的时候就可以无须额外操作直接弹出了。同样,还是需要两个队列来实现栈。具体如何操作呢?

    image

    先来定义一下这个栈:

    class MyStack {
       queue<int> a;
       queue<int> b;
    }

    还是通过一张图,看下使用队列实现的栈是如何进行元素的插入的。

    image

    从上图中可以看出,用来实现栈的两个队列是不区分用途的,也就是说两个队列都具备插入和弹出的功能。之所以可以这么做的原因就是,他要保证任何时候都只有一个队列中有元素。

    上图的插入操作,插入H的时候,两个队列都为空,优先选择从queue1插入。 当想要插入O的时候,由于queue1中已经包含了数据,那么就讲O插入queue2中,然后再将queue1中的数据依次插入queue2。实现代码如下:

    void push(int x) {
       if (a.empty() && b.empty()) {
           a.push(x);
           return;
       }
       if (a.empty()) {
           a.push(x);
           while (!b.empty()) {
               a.push(b.front());
               b.pop();
           }
       }
       else {
           b.push(x);
           while (!a.empty()) {
               b.push(a.front());
               a.pop();
           }
       }
    }

    再来一张图,看看如何使用两个队列来实现栈的弹出操作。

    image

    由于我们在插入的时候,保证了两个队列中只有一个队列包含数据,并且数据的顺序已经调整好了(包含数据的那个队列的队列头就是整个栈的栈顶),那么就直接从有数据的那个队列中往外弹数据就可以了。实现代码如下:

    int pop() {
       if (a.empty()) {
           int temp = b.front();
           b.pop();
           return temp;
       }
       else {
           int temp = a.front();
           a.pop();
           return temp;
       }
    }

    好了,至此,我们已经完成了使用两个栈实现队列和两个队列实现栈的功能的介绍。总结一下,主要有两种方案。拿通过栈来实现队列举例。

    1. 方案一:定义两个栈,一个专门用来插入,一个专门用来弹出。插入操作只会插入到插入栈。弹出的时候,优先从弹出栈往外弹,如果弹出栈中的内容为空,那么就将插入栈中的数据依次弹出,并压入弹出栈,然后再弹出。

    2. 方案二:定义两个栈,不区分作用,但是有一个原则就是始终要保证其中一个栈为空。每次插入的时候先将待插入数据直接插入到空的栈中,然后再将另外一个栈中的数据依次弹出,并压入这个刚刚插入新数据的栈中。弹出的时候,只要从那个有数据的栈中往外弹数据就可以了。

    无论以上哪种方案,其实根本原理都是和我们小时候玩的汉诺塔游戏差不多。

    展开全文
  • 使用两个栈实现队列

    2018-05-06 15:03:02
    使用两个栈实现队列参考文章栈的队列的特点栈和队列都是用来保存数据的,无论底层是使用数组还是链表来实现,其基本原理是不变的,那就是栈的特点的先进后出,队列的特点是先进先出。栈的常用方法 isEmpty() 判断栈...
  • 不仅如此,数组和其他线性存储结构不同,顺序表、链表、栈和队列存储的都不可再分的数据元素(如数字 5、字符 ‘a’ 等),而数组既可以用来存储不可再分的数据元素,也可以用来存储像顺序表、链表这样的数据结构...
  • 其实还是一个队列,从外部调用的接口和实际的功能上看和普通的队列完全没有区别,而之所以它叫循环队列而不是队列,因为它用于实现的底层逻辑和一般队列不同,一般队列底层采用双向链表,而循环队列底层采用索引...
  • 有界队列底层使用数组实现,并发控制使用ReentrantLock控制,不管插入操作还是读取操作,都需要获取锁之后才能执行。 LinkedBlockingQueue 底层基于单向链表实现,既可以当做有界队列,也可以当做无界队列使用。...
  • 链表是一种动态数组,向比较栈、队列来说,栈、队列底层还是一个静态数组,靠resize解决固定容量问题。而链表是真正的动态数据结构,也最简单的动态数据结构。学习链表更深入的理解了指针,更深入理解递归,链表...
  • 一、 容器的由来,有什么好处?...就需要设计一个容器类,底层还是依赖数组链表,但是要根据不同需求,添加不同的功能,让容器方便操作存储的多个对象。 例如:ArrayList针对数据的添加和查询设计...
  • 队列的实现有很多种方式,可以通过底层数据结构链表和数组来实现,甚至栈也可以实现队列。其中,通过动态数组实现的队列,它的入队操作的时间复杂度为O(1),出队时间复杂度为O(n)(或出队为O(1);入队为O(n)。只是...
  • 用两个栈实现队列,java代码实现

    千次阅读 2020-04-30 20:07:48
    不管是队列还是栈,他们的功能都存储数据,底层实现可以数组也可以是链表,但是他们各自有他们的特点。既然队列存储数据的一种数据结构,那么他就有增删改查等功能。队列的添加元素在队尾添加,删除元素在...
  • 虽然LinkedList是一个List集合,但是它的实现方式和ArrayList是完全不同的,ArrayList的底层是通过一个动态的Object[]数组实现的,而LinkedList的底层是通过链表来实现的,因此它的随机访问速度是比较差的,但是它的...
  • 栈与队列

    2017-12-20 17:57:43
    看C++的STL,看习惯了数据结构,不看底层实现实在非常难受的一件事情。 数据结构的底层无非还是指针和数据单元。实现所用到的数据结构 一般为 数组/指针 配合以 指针进行的。 栈的FILO,队列的FIFO。...
  • 优先级队列--大根堆和小根堆

    千次阅读 2019-08-10 16:43:41
    概述 与FIFO的普通队列不同,在优先级队列中,元素出队顺序由元素的优先级决定。...堆一棵完全二叉树,这样就保证了底层存储的数组拥有很高的空间利用率。无论大根堆还是小根堆,它们的插入和删除的复杂性...
  • ArrayList底层采用数组来保存每个集合的元素,LinkedList则一种链式存储的线性表。其本质上就是一个双向链表,但它不仅实现了List接口,还是想了Deque接口。也就是说LinkedList既可以当成双向链表使用,也可以当成...
  • 先进后出、无论出栈还是入栈都在栈顶 2、队列 简称队,先进先出 3、数组 查询快、增删慢 ; 有索引 查询快:数组在内存中存储地址连续的,每个元素所占大小固定的,可以通过首地址+便宜 快速定位到制定...
  • 注:(写了一半,另一半有时间再写) 现在日新月异的大环境下,框架层出不穷,比如前几天还火热的框架,之后就很少被人提起。...数组链表、堆、栈、队列、Hash表、二叉树等。明白LinkedList,ArrayLi...
  • SLAM数据结构面试题

    2021-05-07 17:04:28
    deque: 双端队列,deque的底层实现一个链表数组,序列式容器 list: 底层实现一个双向链表,序列式容器 map: 底层通常由一颗红黑树组成,第一个可以称为键(key),第二个可以称为该键的值(value),在map
  • 前言 上一篇文章讲了ArrayList和Vector,这两者是基于...从结构上,我们还看到了LinkedList实现了Deque接口,因此,我们可以操作LinkedList像操作队列和栈一样,LinkedList的底层是链表,先来看一下节点的定义: ...
  • LinkedList源码解析

    2020-06-30 18:17:14
    虽然LinkedList是一个List集合,但是它的实现方式和ArrayList是完全不同的,ArrayList的底层是通过一个动态的Object[]数组来实现的,而LinkedList的底层是通过链表来实现的,因此它的随机访问速度是比较差的,但是它...
  • 深入ArrayList和LinkedList

    2016-08-10 19:01:33
    ArrayList则一种顺序存储的线性表,ArrayList底层则采用数组来保存每个集合元素,LinkedList则一种链式存储的线性表,它实现了List的接口,还是实现了Deque的接口,LinkedList不仅可以当队列,和双向链表使用,...
  • 二叉树前奏

    2020-09-14 16:47:57
    在前面的数据结构学习中,无论以顺序结构存储的数组还是链式存储结构的链表、栈、队列等,实际上都可以归类成线性结构,今天回忆另外一种数据结构,树形结构,没错,就是生活中的那种树,要倒过来的那种。...
  • 数据结构与算法.xmind

    2020-06-19 17:04:23
    底层干的还是插入排序干的活 做法 最外层for外循环控制增量的数量,每次/2 第二层for循环控制每次增量那组开始进行插入排序,直至完毕 第三层while循环找到要插入到哪个位置 归并...

空空如也

空空如也

1 2 3
收藏数 51
精华内容 20
关键字:

队列底层是数组还是链表