- Implement Queue using Stacks
简单
https://leetcode-cn.com/problems/implement-queue-using-stacks/
Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).
Implement the MyQueue class:
void push(int x) Pushes element x to the back of the queue.
int pop() Removes the element from the front of the queue and returns it.
int peek() Returns the element at the front of the queue.
boolean empty() Returns true if the queue is empty, false otherwise.
Notes:
You must use only standard operations of a stack, which means only push to top, peek/pop from top, size, and is empty operations are valid. Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack's standard operations.
Example 1:
Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]
Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
Constraints:
1 <= x <= 9
At most 100 calls will be made to push, pop, peek, and empty.
All the calls to pop and peek are valid.
Follow-up: Can you implement the queue such that each operation is amortized O(1) time complexity? In other words, performing n operations will take overall O(n) time even if one of those operations may take longer.
相关企业
- 亚马逊 Amazon|8
- 微软 Microsoft|5
- 高盛集团 Goldman Sachs|3
- 字节跳动|2
- 谷歌 Google|2
相关标签
- Stack
- Design
- Queue
相似题目
- Implement Stack using Queues 简单
- 1 Use Array (may fake array overflow)
- 2 Implement Circular Queue Use Array (solve fake array overflow)
- 3 Use LinkedList
- 4 Use Interface Queue (Class LinkedList)
- 5 Use Interface Deque (Class ArrayDeque)
- 6 Use Abstract Class AbstractQueue (class LinkedBlockingQueue)
- 7 Use Class Stack
- 8 python use module collections class deque
在使用数组表示队列时，首先要创建一个长度为MAXSIZE的数组作为队列。
因为MAXSIZE是数组的长度，那MAXSIZE-1就是队列的最大下标了。
在队列中，除了用一组地址连续的存储单元依次存储从队首到队尾的元素外，还需要附设两个整型变量head和tail分别指示队首和队尾的位置。
- head 头元素下标
- tail 尾元素下标+1
每次元素入队时，tail向后移动；每次元素出队时，head向后移动。
可以将队列视作一个类，通过成员变量数组来表示一组地址连续的存储单元，再定义两个成员变量head和tail，将队列的基本操作定义成类的方法。（注意：为了将重点放在实现队列上，做了适当简化。示范队列仅支持整数类型，若想实现泛型，可用反射机制和object对象传参；此外，可多做安全检查并抛出异常）
- head: index for first ele
- tail: index of last ele + 1
- first ele push: no special
- empty: head == tail
- one element: head + 1 == tail
- full: tail >= maxsize
class MyQueue {
private int head;
private int tail;
private int MAXSIZE = 100;
private int[] elements;
public MyQueue() {
this.head = 0;
this.tail = 0;
this.elements = new int[this.MAXSIZE];
}
public void push(int x) {
if (this.tail >= this.MAXSIZE){
return; // it is full. Push failed.
}
this.elements[this.tail] = x;
this.tail ++;
}
public int pop() {
if (this.head == this.tail){
return -1; // empty
}
int firstEleValue = this.elements[this.head];
this.head ++;
return firstEleValue;
}
public int peek() {
return this.elements[this.head];
}
public boolean empty() {
if (this.head == this.tail){
return true;
}
return false;
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/java:
public class MyQueue {
public int head, tail;
public int MAXSIZE = 100000;
public int[] queue = new int[MAXSIZE];
public MyQueue() {
head = tail = 0;
// do initialize if necessary
}
public void enqueue(int item) {
// 队列已满
if(tail == MAXSIZE){
return ;
}
queue[tail++] = item;
}
public int dequeue() {
// 队列为空
if (head == tail){
return -1;
}
return queue[head++];
}
}python:
class MyQueue(object):
def __init__(self):
# do some intialize if necessary
self.MAXSIZE = 4
self.queue = [0] * self.MAXSIZE
self.head, self.tail = 0, 0
# @param {int} item an integer
# @return nothing
def enqueue(self, item):
queue = self.queue
# 队列满
if self.tail == self.MAXSIZE:
return
queue[self.tail] = item
self.tail += 1
# @return an integer
def dequeue(self):
queue = self.queue
## 队列为空
if self.head == self.tail:
return -1
item = queue[self.head]
self.head += 1
return item 但是如果这样实现队列的话，我们考虑MAXSIZE为4的情况，如果我们采取下面的操作
enqueue(1)
enqueue(2)
enqueue(3)
enqueue(4)
dequeue()
dequeue()
结束后数组的状态时[^, ^, 3, 4], head = 2, tail = 4。（'^'表示该位置为空，即当前元素已经出队）
从之前的判断来看，tail == MAXSIZE , 当前队列已经满了，不能继续添加元素了，但是实际上还可以继续添加元素。因此在使用数组实现队列时，可能会出现空间未有效利用的情况，因此，有两种解决方法：
- 使用链表来实现队列
- 使用数组来实现循环队列
- head: index for first ele
- tail: index of last ele + 1
- first ele push: no special
- empty: head == tail
- one element: head + 1 == tail
- full: (tail + 1) % MAXSIZE == head. Always leave one element/spot empty to help us to determine when is full.
class MyQueue {
private int head;
private int tail;
private int MAXSIZE = 100;
private int[] elements;
// always leave one ele/spot empty to help us to determine when full.
public MyQueue() {
this.head = 0;
this.tail = 0;
this.elements = new int[this.MAXSIZE];
}
public void push(int x) {
if ((this.tail + 1) % this.MAXSIZE == head){
return; // it is full. Push failed.
}
this.elements[this.tail] = x;
this.tail = (this.tail + 1) % this.MAXSIZE;
}
public int pop() {
if (this.head == this.tail){
return -1; // empty
}
int firstEleValue = this.elements[this.head];
this.head ++;
return firstEleValue;
}
public int peek() {
return this.elements[this.head];
}
public boolean empty() {
if (this.head == this.tail){
return true;
}
return false;
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/队列是一种先进先出的线性表，它只允许在表的一端进行插入，而在另一端删除元素。允许插入的一端称为队尾，允许删除的一端称为队首。但是之前也提到了，数组实现的队列会导致“虽然数组没满，但是tail已经指向了数组末尾，返回数组已满，队列溢出的错误信号”，我们称之为“假溢出”。
为充分利用向量空间，克服"假溢出"现象的方法是：
- 将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。循环队列是把顺序队列首尾相连，把存储队列元素的表从逻辑上看成一个环，成为循环队列。
在循环队列中，除了用一组地址连续的存储单元依次存储从队首到队尾的元素外，还需要附设两个整型变量head和tail分别指示队首和队尾的位置。
可以将循环队列视作一个类，通过成员变量数组来表示一组地址连续的存储单元，再定义两个成员变量head和tail，将循环队列的基本操作定义成类的方法，循环效果则用“模”运算实现，以此来实现循环队列。
每当tail到达末尾的时候，将tail对MAXSIZE取模，使其回到队首。但是如果这样会发现一个问题，队列为空和队列已满的条件都成了tail == head。
为了避免这种无法判断的情况，我们规定当循环队列只剩一个空位的时候，就认为队列已满。这样队列已满的条件就成了 (tail + 1) % MAXSIZE == head。
java:
public class MyQueue {
public int head, tail;
public int SIZE = 4;
public int[] queue = new int[SIZE];
public MyQueue() {
head = tail = 0;
// do initialize if necessary
}
//压入一个元素
public void enqueue(int item) {
// 队列已满
if ((tail + 1) % SIZE == head){
return ;
}
queue[tail++] = item;
tail %= SIZE;
}
//弹出一个元素
public int dequeue() {
// 队列为空
if (head == tail){
return -1;
}
int item = queue[head++];
head %= SIZE;
return item;
}
}python:
class MyQueue(object):
def __init__(self):
# do some intialize if necessary
self.SIZE = 100000
self.queue = [0] * self.SIZE
self.head, self.tail = 0, 0
# @param {int} item an integer
# @return nothing
# 压入队列
def enqueue(self, item):
queue = self.queue
# 队列满
if (self.tail + 1) % self.SIZE == self.head:
return
queue[self.tail] = item
self.tail = (self.tail + 1) % self.SIZE
# @return an integer
# 弹出元素
def dequeue(self):
queue = self.queue
## 队列为空
if self.head == self.tail:
return -1
item = queue[self.head]
self.head = (self.head + 1) % self.SIZE
return item 链表是由多个节点构成的，一个节点由两部分组成:
- 一个是数据域,
- 一个是指针域.
链表分为:
- 单链表(只能是父节点引用子节点),
- 双链表(相邻的节点可相互引用),
- 循环链表(在双链表的基础上,头尾节点可相互引用).
实现链表,就是在链表里加入节点,使用节点的引用域使节点之间形成连接,可相互调用.
链表队列的实现原理:
- 首先定义一个节点类,节点类包含引用域和数据域.
- 然后定义一个链表类,链表类形成节点间的引用关系.
在队列中，只要用两个指针head和tail分别指向链表的头部和尾部即可实现基本队列功能
- head: pointer to fisrt ele;
- tail: pointer to last ele;
- fisrt ele push: head == null
- empty: head == null;
- one element: head == tail;
class Node {
public int value;
public Node next;
public Node(int v){
this.value = v;
this.next = null;
}
}
class MyQueue {
private Node head;
private Node tail;
public MyQueue() {
this.head = this.tail = null;
}
public void push(int x) {
if (this.head == null){
// fisrt ele push
this.head = new Node(x);
this.tail = this.head; // head tial point to same node bc there is only one
return;
}
Node newtail = new Node(x);
this.tail.next = newtail;
this.tail = newtail;
}
public int pop() {
if (this.head == null){
System.out.println("empty so pop failed.");
return -1; // empty
}
int firstEleValue = this.head.value;
this.head = this.head.next;
return firstEleValue;
}
public int peek() {
if (this.head == null){
System.out.println("empty so peek failed.");
return -1; // empty
}
return this.head.value;
}
public boolean empty() {
if (this.head == null){
return true;
}
return false;
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/java:
class Node {
public int val;
public Node next;
public Node(int _val) {
val = _val;
next = null;
}
}
public class MyQueue {
public Node head, tail;
public MyQueue() {
head = tail = null;
// do initialize if necessary
}
public void enqueue(int item) {
if (head == null) {
tail = new Node(item);
head = tail;
} else {
tail.next = new Node(item);
tail = tail.next;
}
}
public int dequeue() {
if (head != null) {
int item = head.val;
head = head.next;
return item;
}
return -1;
}
}puthon:
class Node():
def __init__(self, _val):
self.next = None
self.val = _val
class MyQueue(object):
def __init__(self):
# do some intialize if necessary
self.head, self.tail = None, None
# @param {int} item an integer
# @return nothing
def enqueue(self, item):
if self.head is None:
self.head = Node(item)
self.tail = self.head
else:
self.tail.next = Node(item)
self.tail = self.tail.next
# @return an integer
def dequeue(self):
if self.head is not None:
item = self.head.val
self.head = self.head.next
return item
return -1在算法面试中，当我们要使用队列（如实现BFS时）是否需要自己实现队列呢？
如果不是题目要求实现一个队列，我们都可以使用变成语言自带的队列数据结构，因为这些题目，面试官并不是想考察你是否能够实现队列，而是想考察其他的算法，如果现场实现队列，时间可能会不够。
比如在Java中我们就可以调用Queue接口来实现队列.
class MyQueue {
private Queue<Integer> elements;
public MyQueue() {
this.elements = new LinkedList<Integer>();
}
public void push(int x) {
this.elements.add(x);
}
public int pop() {
return this.elements.poll();
}
public int peek() {
return this.elements.peek();
}
public boolean empty() {
if (this.elements.peek() == null){
return true;
}
return false;
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/class MyQueue {
private Deque<Integer> elements;
public MyQueue() {
this.elements = new ArrayDeque<Integer>();
}
public void push(int x) {
this.elements.addLast(x);
}
public int pop() {
return this.elements.pollFirst();
}
public int peek() {
return this.elements.getFirst();
}
public boolean empty() {
return this.elements.isEmpty();
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/Since AbstractQueue is an abstract class, it’s implementation is provided by its sub-classes. Below shows the list of classes that can provide the implementation. To create it, we need to it from java.util.AbstractQueue.
- protected AbstractQueue(): The default constructor, but being abstract, it doesn’t allow to create an AbstractQueue object.
- The implementation should be provided by one of its subclasses like
-
- ArrayBlockingQueue,
- ConcurrentLinkedQueue,
- DelayQueue,
- LinkedBlockingDeque,
- LinkedBlockingQueue,
- LinkedTransferQueue,
- PriorityBlockingQueue,
- PriorityQueue,
- SynchronousQueue.
AbstractQueue objName = new ArrayBlockingQueue();
import java.util.AbstractQueue;
class MyQueue {
private AbstractQueue<Integer> elements;
public MyQueue() {
this.elements = new LinkedBlockingQueue<Integer>();
}
public void push(int x) {
this.elements.offer(x);
}
public int pop() {
return this.elements.poll(); // remove head ele
}
public int peek() {
return this.elements.peek();
}
public boolean empty() {
if (this.elements== null || this.elements.size() == 0){
return true;
}
return false;
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/class MyQueue {
// only use one to store all elements. The other one must be empty.
private Stack<Integer> stackHeadAtBottom;
private Stack<Integer> stackTailAtBottom;
private int head; // save for peek()
public MyQueue() {
this.stackHeadAtBottom = new Stack<Integer>();
this.stackTailAtBottom = new Stack<Integer>();
}
public void push(int x) {
if (this.empty()){
this.stackHeadAtBottom.push(x); // first ele push
this.head = x;
return;
}else if (!this.stackHeadAtBottom.empty() && this.stackTailAtBottom.empty()){
this.stackHeadAtBottom.push(x); // O(1)
return;
}else { // O(n)
while (!this.stackTailAtBottom.empty()){
this.stackHeadAtBottom.push(this.stackTailAtBottom.pop());
}
this.head = this.stackHeadAtBottom.peek();
this.stackHeadAtBottom.push(x);
}
}
public int pop() {
if (this.empty()){
return -1;
}else if (!this.stackHeadAtBottom.empty() && this.stackTailAtBottom.empty()){
while (!this.stackHeadAtBottom.empty()){
this.stackTailAtBottom.push(this.stackHeadAtBottom.pop());
}
}
int oldheadvalue = this.stackTailAtBottom.pop();
if (this.stackTailAtBottom.empty()){
this.head = -1;
}else{
this.head = this.stackTailAtBottom.peek();
}
return oldheadvalue;
}
public int peek() {
return this.head;
}
public boolean empty() {
if (this.stackHeadAtBottom.empty() && this.stackTailAtBottom.empty()){
return true;
}
return false;
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/from collections import deque
class MyQueue:
def __init__(self):
self.myqueue = deque() # left as head
def push(self, x: int) -> None:
self.myqueue.append(x)
def pop(self) -> int:
return self.myqueue.popleft()
def peek(self) -> int:
if self.myqueue:
return self.myqueue[0]
return -1
def empty(self) -> bool:
return len(self.myqueue) == 0
# 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()