专栏首页Android开发小工数据结构基础-栈和队列

数据结构基础-栈和队列

栈的理论描述

栈是一个有序线性表,只能在表的一端(成为栈顶,top)执行插入和删除操作。最后插入的元素将第一个被删除。所以栈也称为后进先出(Last In First Out)或先进后出(First In Last Out)线性表。栈主要有两个操作,一个入栈(push),表示在栈中插入一个元素,一个出栈(pop),表示将栈顶元素删除。试图对空栈执行出栈操作称为UnderFlow,对满栈执行入栈操作称为OverFlow。

栈的抽象数据结构

栈的主要操作:
  • void push(int data):将data插入栈
  • int pop():删除并返回最后一个插入栈的元素
栈的辅助操作
  • int top():返回最后一个插入栈的元素
  • int size():返回存储在栈中元素的个数
  • int isEmpty():判断栈中是否有元素
  • int StackFull():判断栈中是否存满元素
异常

pop和top操作在栈空的时候是不能操作的。试图对空栈执行pop和top会抛出异常。试图对满栈执行push操作也会抛出异常。

代码实现

栈抽象数据结构有多种实现方式:

  • 基于简单数组的实现方法
  • 基于动态数组的实现方法
  • 基于链表的实现方法

简单数组:

public class DynArrayStack {

    private int top;
    private int capacity;
    private int[] array;

    public DynArrayStack(){
        capacity = 1;
        array = new int[capacity];
        top = -1;
    }

    public boolean isEmpty() {
        return (top == -1);
    }

    public boolean isStackFull() {
        return (top == capacity -1);
    }

    public void push(int data) {
        if (isStackFull()) {
            System.out.println("Stack overflow!");
        }else {
            array[++top] = data;
        }
    }

    public int pop() {
        if (isEmpty()) {
            System.out.println("Stack is empty!");
            return 0;
        }else {
            return array[top--];
        }
    }

}

动态数组的实现方法大致一样,只是比上面的多了当到达数组最大容量的时候将容量扩大到现有的一倍。

private void doubleSize(){
        int newArray[] = new int[capacity << 1];
        System.arraycopy(array, 0, newArray, 0, capacity);
        capacity = capacity << 1;
        array = newArray;
    }
    
public void push(int data) {
        if (isStackFull()) {
            doubleSize();
        }else {
            array[++top] = data;
        }
    }

链表的栈实现方式:

public class LLStack {

    private LinkedNode headNode;

    public LLStack(){}

    public void push(int data) {
        if (headNode == null) {
            headNode = new LinkedNode(data);
        }else if (headNode.getData() == null) {
            headNode.setData(data);
        }else {
            LinkedNode node = new LinkedNode(data);
            node.setNext(headNode);
            headNode = node;
        }
    }

    public int pop(){
        if (headNode == null) {
            throw new EmptyStackException("Stack Empty");
        }
        int data = headNode.getData();
        headNode = headNode.getNext();
        return data;
    }

    public int top(){
        return headNode == null ? null : headNode.getData();
    }

    public boolean isEmpty(){
        return headNode == null || headNode.getData() == null;
    }

}

各种实现方式的比较:

基于数组实现的栈:

  • 各个操作都是常数时间开销
  • 每隔一段时间倍增的开销教大
  • n个操作的任意序列的平摊时间开销为O(n)

基于链表实现的栈:

  • 栈规模增加减少都很简洁
  • 各个操作都是常数时间开销
  • 每个操作都要使用额外的时间和空间开销来处理指针

应用

  • IDE和编译器中符号匹配
  • 中缀表达式转换为后缀表达式
  • 实现函数调用(包括递归)

栈的相关问题

eg:计算跨度:给定数组A,A[i]的跨度S[i]定义为:满足A[j]<= A[j+1]而且在A[i]前的连续元素A[j]的最大个数。如图

/* time:O(n), space:(n) */
public int[] findingSpans(int[] inputArray) {
    int[] spans = new int[inputArray.length];
    Stack<Integer> stack = new Stack();
    int p;
    for (int i = 0; i < inputArray.length; i++) {
        while (!stack.isEmpty() && inputArray[i] > inputArray[stack.pop()]) {
            stack.pop();
        }
        if (stack.isEmpty()) {
            p = -1;
        }else {
            p = stack.top();
        }
        spans[i] = i - p;
        stack.push(i);
        }
    return spans;
    }

eg:设计一个可以把栈中元素按照升序排列的排序算法,并且不能限定栈的实现方法。

/* time:O(n^2) , space:O(n) */
    public Stack<Integer> sort(Stack<Integer> s) {
        Stack<Integer> r = new Stack<>();
        while (!s.isEmpty()) {
            int temp = s.pop();
            while (!r.isEmpty() && r.peek() > temp) {
                s.push(r.pop());
            }
            r.push(temp);
        }
        return r;
    }

eg:删除所有相邻的重复元素:给定一个数字数组,删除相邻的重复数字,结果数组中不能有任何相邻的重复数字。

input

1, 5, 6, 8, 8, 0, 1, 1, 0, 6, 5

optput

1

/* space:O(n) , time:O(n) */
    public int removeAdjacentDuplicates(int[] a){
        int stkptr = -1;
        int i = 0;
        while (i < a.length) {
            if (stkptr == -1 || a[stkptr] != a[i]) {
                stkptr++;
                a[stkptr] = a[i];
            }else {
                while (i < a.length && a[stkptr] == a[i]) {
                    i++;
                }
                stkptr--;
            }
        }
        return stkptr;
    }

队列的理论描述

定义:队列是一种只能在一端插入(队尾),在另一端(队首)的有序线性表。队列中第一个插入就是第一个被删除的元素。所以队列是一种先进先出(FIFO,first in first out)或者后进后出(LILO,last in last out)线性表。

队列的抽象数据结构

队列的主要操作:
  • void enQueue(int data):将data插入队列
  • int deQueue():删除并返回队首的元素
栈的辅助操作
  • int front():返回队首元素
  • int size():返回存储在队列中元素的个数
  • int isEmpty():判断队列中是否存储了元素
异常
  • 队空时异常(执行deQueue操作)
  • 队满时异常(执行enQueue操作)

代码实现

基于循环数组

为什么需要循环数组?由队列定义,在一端插入,一端删除。 当执行多次插入和删除操作后,就可以容易地发现数组靠前位置的空间被浪费了,所以基于简单数组实现队列不是一个靠谱的方法。循环数组刚好可以用来解决这个问题

public class DynArrayQueue {

    private int front;
    private int rear;
    private int capacity;
    private int[] array;

    public DynArrayQueue(){
        capacity = 1;
        front = rear = -1;
        array = new int[capacity];
    }

    public boolean isEmpty() {
        return front == -1;
    }

    public boolean isFull() {
        return (rear + 1) % capacity == front;
    }

    public int getSize() {
        if (front  == -1) {
            return 0;
        }
        int size = (capacity + rear + 1 - front);
        if (size == 0) {
            return capacity;
        }else {
            return size;
        }
    }

    public void resizeQueue() {
        int initCapacity = capacity;
        capacity *= 2;
        int[] old = array;
        array = new intp[capacity];
        for (int i = 0; i < old.length; i++) {
            array[i] = old[i];
        }
        if (front > rear) {
            for (int i = 0; i < front; i++) {
                array[i + capacity] = array[i];
                array[i] = null;
            }
            rear += initCapacity;
        }
    }

    public void enQueue(int data) {
        if (isFull()) {
            resizeQueue();
        }
        rear = (rear + 1) % capacity;
        array[rear] = data;
        if (front == -1) {
            front = rear;
        }
    }

    public int deQueue(){
        int data = null;
        if (isEmpty()) {
            throw new EmptyQueueException("Queue is empty");
        }else {
            data = array[front];
            if (front == rear) {
                front = rear = -1;
            }else {
                front = (front + 1) % capacity;
            }
        }
        return data;
    }

}

基于动态循环数组

基于上面的理解,循环数组其实还是有个问题,就是当分配给数组的个数到达最大值的时候,再插入元素就会溢出,所以有了动态循环数组。

public class DynArrayQueue {

    private int front;
    private int rear;
    private int capacity;
    private int[] array;

    public DynArrayQueue(){
        capacity = 1;
        front = rear = -1;
        array = new int[capacity];
    }

    public boolean isEmpty() {
        return front == -1;
    }

    public boolean isFull() {
        return (rear + 1) % capacity == front;
    }

    public int getSize() {
        return ((capacity - front + rear + 1)%capacity);
    }

    public void enQueue(int data) {
        if (isFull()) {
            throw new QueueOverFlowException("queue overflow");
        }
        rear = (rear + 1) % capacity;
        array[rear] = data;
        if (front == -1) {
            front = rear;
        }
    }

    public int deQueue(){
        int data = null;
        if (isEmpty()) {
            throw new EmptyQueueException("Queue is empty");
        }else {
            data = array[front];
            if (front == rear) {
                front = rear = -1;
            }else {
                front = (front + 1) % capacity;
            }
        }
        return data;
    }

}

基于链表

public class LLQueue {

    private LinkedListNode<Integer> frontNode;
    private LinkedListNode<Integer> rearNode;

    public boolean isEmpty() {
        return frontNode == null;
    }

    public void enQueue(int data){
        LinkedListNode newNode = new LinkedListNode(data);
        if (rearNode != null) {
            rearNode.setNext(newNode);
        }else {
            frontNode = rearNode = newNode;
        }
    }

    public int deQueue() {
        int data;
        if (isEmpty()) {
           throw new EmptyQueueEmptyException("Queue Empty"); 
        }
        data = frontNode.getData();
        frontNode = frontNode.getNext();
        return data;
    }

}

链表和数组的对比和栈是一样的区别:链表需要花费指针这些额外的空间,但是操作和思路都很简便。

应用

  • 操作系统根据任务到达的顺序调度任务(如打印队列)
  • 模拟现实世界中的队列
  • 多道程序设计
  • 异步数据传输

队列的相关问题

eg:如果需要反向输出队列中元素,应该用什么数据结构? 答:

public Queue<Integer> reverseQueue(Queue<Integer> queue){
    Stack stack = new Stack<Integer>();
    while(!queue.isEmpty(){
        stack.push(queue.deQueue());
    }
    while(!stack.isEmpty()){
        queue.enQueue(stack.poll());
    }
    return queue;
}

eg:用两个队列实现一个栈的数据结构接口。 解答:

public class StackWithTwoQueues {

    LLQueue queue1;
    LLQueue queue2;

    public StackWithTwoQueues(){
        queue1 = new LLQueue();
        queue2 = new LLQueue();
    }

    public void push(int data) {
        if (queue1.isEmpty()) {
            queue2.enQueue(data);
        }else {
            queue1.enQueue(data);
        }
    }

    public int pop(){
        int i, size, value;
        i = 0;
        if (queue1.isEmpty()) {
            size = queue2.getSize();
            while (i < size -1) {
                queue1.enQueue(queue2.deQueue());
                i++;
            }
            value = queue2.deQueue();
        }else {
            size = queue1.getSize();
            while (i < size -1) {
                queue2.enQueue(queue1.deQueue());
                i++;
            }
            value = queue1.deQueue();
        }
        return 0;
    }

}

eg:给定一个整数栈,如何检查栈中每队相邻数字是否是连续的。每对数字的值可以是递增或递减的。如果栈中元素的个数是奇数,那么组队时忽略栈顶元素。例如,假设栈中元素为[4,5,-2,-3,11,10,5,6,20],那算法应该输出真,因为每对二元组(4,5),(-2,-3),(11,10)和(5,6)都是连续数字。 解答:

public boolean checkStackPairwiseOrder(Stack<Integer> s) {
        boolean pairwiseOrder = true;
        LLQueue queue = new LLQueue();
        while (!s.isEmpty()) {
            queue.enQueue(s.pop());
        }
        while (!queue.isEmpty()) {
            s.push(queue.enQueue());
        }
        while (!s.isEmpty()) {
            int n = s.pop();
            if (!s.isEmpty()) {
                int m = s.pop();
                queue.add(m);
                if (Math.abs(n - m) != 1) {
                    pairwiseOrder = false;
                    break;
                }
            }
        }
        return pairwiseOrder;
    }

eg:给定一个整数k和一个整数队列,如何把队列中前k个元素逆置,其余的元素保持不变?例如,如果k等于4,队列中元素序列为[10,20,30,40,50,60,70,80,90],那么应该输出[40,30,20,10,50,60,70,80,90]。 解答:

public void reverseQueueFirstKElements(int k, Queue<Integer> q) {
        if (q == null || k > q.getSize()) {
            throw new IllegalArgumentException();
        }
        if (k > 0) {
            Stack<Integer> stack = new Stack<Integer>();
            for(int i=0;i<k;i++){
                stack.push(q.remove());
            }
            while(!stack.isEmpty()){
                q.add(stack.pop());
            }
            for (int i = 0; i < q.size() - k; i++) {
                q.add(q.remove());
            }
        }
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 完全自定义样式的一句话实现RecyclerView的单选多选

    今天的主题是封装RecyclerView的单选多选,现在大家应该都是用的RecyclerView开发列表数据吧。

    1025645
  • 优雅地实现RecyclerView的上拉加载

    这篇博客是承接上一篇博客--探索Android架构的DataLayer层(DataManager方式)具体实现,其实是上篇博客的一个使用比较普遍的例子,当然如果...

    1025645
  • RecyclerView的通用快速适配封装

    其实这篇博客是我后面一篇博客的准备~一句话实现RecyclerView的单选多选的选项列表

    1025645
  • 常用的递归算法

    版权声明:本文为博主原创文章,遵循 CC 4.0 by-sa 版权协议,转载请附上原文出处链接和本声明。

    张凝可
  • java之单元测试

    Vincent-yuan
  • 算法学习之栈与队列

    Stack<E> void push(E) //入栈 E pop() //出栈 E peek() //查看 int getSize() //长度 bool...

    慕白
  • 委托学习过程及委托、Lambda表达式和匿名方法的关系总结及事件总结

    委托是一个类,它定义了方法的类型,使得可以将方法当作另一个方法的参数来进行传递,这种将方法动态地赋给参数的做法,可以避免在程序中大量使用If-Else(Swit...

    wfaceboss
  • Data Structure_Visualization排序可视化走迷宫生成迷宫扫雷

    选择排序很简单,遍历所有元素,查看一下他们的之后最小的元素和当前元素交换即可。模板函数使用上面的swing模板。为了更清楚显示出排序的过程,可以用不同颜色代表排...

    西红柿炒鸡蛋
  • C#基础知识系列一(goto、i++、三元运算符、ref和out、String和string、重载运算符)

      这两天在网上看到的总结很多,尤其是博客园中的,很多很多,也给了我很多的启发,当然自己也总结过,而且有很多人也给与我一些意见和看法。不管怎样,自己还是先把所谓...

    aehyok
  • Go语言3

    字符串替换,对原始字符串str进行替换,把原始的old替换成new。 最后一个n是替换的次数,如果 n<0 则替换所有。一般就-1。

    py3study

扫码关注云+社区

领取腾讯云代金券