栈和队列

迈不过友情╰ 2023-07-03 04:52 29阅读 0赞

### 文章目录 ###

*   *  栈
     *   *   *   *  栈的实现
                 *  栈 - 用法
     *  队列
     *   *   *   *  队列 - 实现
                 *  循环队列
                 *  队列 - 用法
     *  Leetcode链表练习

**启示**  
： **栈是限定仅在表尾进行插入和删除操作的线性表**  
： **队列是只允许在一端插入，而在另一端删除的线性表**

## 栈 ##

**后入先出的数据结构**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjU4NDU0NQ_size_16_color_FFFFFF_t_70]  
栈是一种线性表的特殊表现形式  
栈是按照“后进先出”（Last In Firt Out，LIFO）的原则处理数据  
栈的基本操作只有两个：

*  入栈（Push）：即将数据保存到栈顶。进行该操作前，先修改栈顶指针，使其向上移一个元素位置，然后将数据保存到栈顶指针所指的位置
 *  出栈（Pop）：即将栈顶的数据弹出，然后修改栈顶指针，使其指向栈中的下一个元素

在 LIFO 数据结构中，将首先处理添加到队列中的最新元素。

与队列不同，栈是一个 LIFO 数据结构。通常，插入操作在栈中被称作入栈 push 。与队列类似，总是在堆栈的末尾添加一个新元素。但是，删除操作，退栈 pop ，将始终删除队列中相对于它的最后一个元素。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjU4NDU0NQ_size_16_color_FFFFFF_t_70 1]

##### 栈的实现 #####

**基于数组的实现  
基于链表的实现**

// "static void main" must be defined in a public class.
    class MyStack { 
        private List<Integer> data;               // store elements
        public MyStack() { 
            data = new ArrayList<>();
        }
        /** Insert an element into the stack. */
        public void push(int x) { 
            data.add(x);
        }
        /** Checks whether the queue is empty or not. */
        public boolean isEmpty() { 
            return data.isEmpty();
        }
        /** Get the top item from the queue. */
        public int top() { 
            return data.get(data.size() - 1);
        }
        /** Delete an element from the queue. Return true if the operation is successful. */
        public boolean pop() { 
            if (isEmpty()) { 
                return false;
            }
            data.remove(data.size() - 1);
            return true;
        }
    };
    
    public class Main { 
        public static void main(String[] args) { 
            MyStack s = new MyStack();
            s.push(1);
            s.push(2);
            s.push(3);
            for (int i = 0; i < 4; ++i) { 
                if (!s.isEmpty()) { 
                    System.out.println(s.top());
                }
                System.out.println(s.pop());
            }
        }
    }

##### 栈 - 用法 #####

大多数流行的语言都提供了内置的栈库，因此你不必重新发明轮子。除了初始化，我们还需要知道如何使用两个最重要的操作：入栈和退栈。除此之外，你应该能够从栈中获得顶部元素。下面是一些供你参考的代码示例：

// "static void main" must be defined in a public class.
    public class Main { 
        public static void main(String[] args) { 
            // 1. Initialize a stack.
            Stack<Integer> s = new Stack<>();
            // 2. Push new element.
            s.push(5);
            s.push(13);
            s.push(8);
            s.push(6);
            // 3. Check if stack is empty.
            if (s.empty() == true) { 
                System.out.println("Stack is empty!");
                return;
            }
            // 4. Pop an element.
            s.pop();
            // 5. Get the top element.
            System.out.println("The top element is: " + s.peek());
            // 6. Get the size of the stack.
            System.out.println("The size is: " + s.size());
        }
    }

## 队列 ##

**先入先出的数据结构**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjU4NDU0NQ_size_16_color_FFFFFF_t_70 2]  
队列是一种特殊的线性表(First In First Output)  
只允许在表的**前端进行删除操作**，而在**表的后端进行插入操作**

*  进行插入操作的端称为**队尾**
 *  进行删除操作的端称为**队头**  
    在 FIFO 数据结构中，将首先处理添加到队列中的第一个元素。

如上图所示，队列是典型的 FIFO 数据结构。插入（insert）操作也称作入队（enqueue），新元素始终被添加在队列的末尾。 删除（delete）操作也被称为出队（dequeue)。 你只能移除第一个元素。  
**示例 - 队列**

1.  入队：您可以单击下面的 Enqueue 以查看如何将新元素 6 添加到队列中。2. 出队：您可以单击下面的 Dequeue 以查看将删除哪个元素。

##### 队列 - 实现 #####

为了实现队列，我们可以使用动态数组和指向队列头部的索引。

如上所述，队列应支持两种操作：入队和出队。入队会向队列追加一个新元素，而出队会删除第一个元素。 所以我们需要一个索引来指出起点。

这是一个供你参考的实现：

// "static void main" must be defined in a public class.
    
    class MyQueue { 
        // store elements
        private List<Integer> data;         
        // a pointer to indicate the start position
        private int p_start;            
        public MyQueue() { 
            data = new ArrayList<Integer>();
            p_start = 0;
        }
        /** Insert an element into the queue. Return true if the operation is successful. */
        public boolean enQueue(int x) { 
            data.add(x);
            return true;
        };    
        /** Delete an element from the queue. Return true if the operation is successful. */
        public boolean deQueue() { 
            if (isEmpty() == true) { 
                return false;
            }
            p_start++;
            return true;
        }
        /** Get the front item from the queue. */
        public int Front() { 
            return data.get(p_start);
        }
        /** Checks whether the queue is empty or not. */
        public boolean isEmpty() { 
            return p_start >= data.size();
        }     
    };
    
    public class Main { 
        public static void main(String[] args) { 
            MyQueue q = new MyQueue();
            q.enQueue(5);
            q.enQueue(3);
            if (q.isEmpty() == false) { 
                System.out.println(q.Front());
            }
            q.deQueue();
            if (q.isEmpty() == false) { 
                System.out.println(q.Front());
            }
            q.deQueue();
            if (q.isEmpty() == false) { 
                System.out.println(q.Front());
            }
        }
    }

##### 循环队列 #####

此前，我们提供了一种简单但低效的队列实现。

更有效的方法是使用循环队列。 具体来说，我们可以使用固定大小的数组和两个指针来指示起始位置和结束位置。 目的是重用我们之前提到的被浪费的存储。  
**循环队列 - 实现**  
在循环队列中，我们使用一个数组和两个指针（head 和 tail）。 head 表示队列的起始位置，tail 表示队列的结束位置。

class MyCircularQueue { 
        
        private int[] data;
        private int head;
        private int tail;
        private int size;
    
        /** Initialize your data structure here. Set the size of the queue to be k. */
        public MyCircularQueue(int k) { 
            data = new int[k];
            head = -1;
            tail = -1;
            size = k;
        }
        
        /** Insert an element into the circular queue. Return true if the operation is successful. */
        public boolean enQueue(int value) { 
            if (isFull() == true) { 
                return false;
            }
            if (isEmpty() == true) { 
                head = 0;
            }
            tail = (tail + 1) % size;
            data[tail] = value;
            return true;
        }
        
        /** Delete an element from the circular queue. Return true if the operation is successful. */
        public boolean deQueue() { 
            if (isEmpty() == true) { 
                return false;
            }
            if (head == tail) { 
                head = -1;
                tail = -1;
                return true;
            }
            head = (head + 1) % size;
            return true;
        }
        
        /** Get the front item from the queue. */
        public int Front() { 
            if (isEmpty() == true) { 
                return -1;
            }
            return data[head];
        }
        
        /** Get the last item from the queue. */
        public int Rear() { 
            if (isEmpty() == true) { 
                return -1;
            }
            return data[tail];
        }
        
        /** Checks whether the circular queue is empty or not. */
        public boolean isEmpty() { 
            return head == -1;
        }
        
        /** Checks whether the circular queue is full or not. */
        public boolean isFull() { 
            return ((tail + 1) % size) == head;
        }
    }
    
    /** * Your MyCircularQueue object will be instantiated and called as such: * MyCircularQueue obj = new MyCircularQueue(k); * boolean param_1 = obj.enQueue(value); * boolean param_2 = obj.deQueue(); * int param_3 = obj.Front(); * int param_4 = obj.Rear(); * boolean param_5 = obj.isEmpty(); * boolean param_6 = obj.isFull(); */

##### 队列 - 用法 #####

大多数流行语言都提供内置的队列库，因此您无需重新发明轮子。

如前所述，队列有两个重要的操作，入队 enqueue 和出队 dequeue。 此外，我们应该能够获得队列中的第一个元素，因为应该首先处理它。  
下面是使用内置队列库及其常见操作的一些示例：

// "static void main" must be defined in a public class.
    public class Main { 
        public static void main(String[] args) { 
            // 1. Initialize a queue.
            Queue<Integer> q = new LinkedList();
            // 2. Get the first element - return null if queue is empty.
            System.out.println("The first element is: " + q.peek());
            // 3. Push new element.
            q.offer(5);
            q.offer(13);
            q.offer(8);
            q.offer(6);
            // 4. Pop an element.
            q.poll();
            // 5. Get the first element.
            System.out.println("The first element is: " + q.peek());
            // 7. Get the size of the queue.
            System.out.println("The size is: " + q.size());
        }
    }

## Leetcode链表练习 ##

1.  Min Stack  
    20 Valid Parentheses
2.  Evaluate Reverse Polish Notation  
    225 Implement Stack using Queues  
    232 Implement Queue using Stacks  
    622 Design Circular Queue  
    641 Design Circular Deque

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjU4NDU0NQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200202155443824.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjU4NDU0NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjU4NDU0NQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200202155046787.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjU4NDU0NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjU4NDU0NQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200202160354550.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjU4NDU0NQ==,size_16,color_FFFFFF,t_70