Leetcode的AC指南 —— 栈与队列:225.用队列实现栈

发布时间:2024年01月20日

摘要:
**Leetcode的AC指南 —— 栈与队列:225.用队列实现栈 **。题目介绍:请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty)。
实现 MyStack 类:
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的,返回 true ;否则,返回 false 。
注意:
你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list (列表)或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。

一、题目


题目介绍:请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty)。

实现 MyStack 类:

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的,返回 true ;否则,返回 false 。

注意:

你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list (列表)或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。

力扣题目链接

示例 1:

输入:
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出:
[null, null, null, 2, 2, false]

解释:
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

提示:
1 <= x <= 9
最多调用100 次 push、pop、top 和 empty
每次调用 pop 和 top 都保证栈不为空

进阶:

  • 你能否仅用一个队列来实现栈

二、解析 (go语言版)


1、两个队列实现栈

  • 思路:
    • 根据栈先进后出和队列先进先出的特点,
      • 将后进栈的元素放入队列的头部,实现后进先出
      • 进栈的实现:
        • 将后进栈的元素压进队列2,
        • 然后在依次将队列1中的元素压入队列2内
        • 最后交换队列1指向队列2,队列2置空
      • 出栈:直接弹出队列1的头元素。
        在这里插入图片描述
  • 时间复杂度: pop为O(n),其他为O(1)
  • 空间复杂度: O(n)

package main

type MyStack struct {
	que1 []int
	que2 []int
}
// 栈的初始化
func Constructor() MyStack {
	return MyStack{
		que1: make([]int, 0),
		que2: make([]int, 0),
	}
}

// 将队列1中的元素压入队列2,并交换队列1和队列2
func (this *MyStack) Move() {
	if len(this.que1) == 0 { 
		// 当队列1中的没有元素后,交换队列1为队列2,队列2为空
		this.que1, this.que2 = this.que2, this.que1
	} else {
		// 将队列1中的元素依次弹出压入队列2
		this.que2 = append(this.que2, this.que1[0])
		this.que1 = this.que1[1:]
		this.Move()
	}
}

// 进栈: 向栈中添加元素
func (this *MyStack) Push(x int) {
	// 将元素压入栈2
	this.que2 = append(this.que2, x)
	// 更新栈1和栈2的数据
	this.Move()
}

// 出栈: 将队列1中的头元素弹出
func (this *MyStack) Pop() int {
	val := this.que1[0]
	this.que1 = this.que1[1:]
	return val
}

// 获取栈顶元素的值
func (this *MyStack) Top() int {
	return this.que1[0]

}

// 判断栈是否为空
func (this *MyStack) Empty() bool {
	return len(this.que1) == 0
}

2、一个队列实现栈

  • 思路:
    • 将进栈的元素放在队列的队头位置
      • 实现:
        • 将新元素压入队列的队尾
        • 将队头元素依次出队,然后在重新入队
        • 直到新压入的元素成为队头
package main

type MyStack struct {
	que []int
}

func Constructor() MyStack {
	return MyStack{
		que: make([]int, 0),
	}
}

func (this *MyStack) Push(x int) {
	// 将进栈元素压入队列
	this.que = append(this.que, x)
	// 将该元素前面的元素依次出队,在重新进队,使后进栈的元素在队头
	for i := 0; i < len(this.que)-1; i++ {
		// 将队头元素出队列
		val := this.que[0]
		this.que = this.que[1:]
		// 将出队列的队头元素入队列
		this.que = append(this.que, val)
	}
}

func (this *MyStack) Pop() int {
	val := this.que[0]
	this.que = this.que[1:]
	return val
}

func (this *MyStack) Top() int {
	return this.que[0]
}

func (this *MyStack) Empty() bool {
	return len(this.que) == 0
}

三、其他语言版本


Java

class MyStack {

    Queue<Integer> queue1; // 和栈中保持一样元素的队列
    Queue<Integer> queue2; // 辅助队列

    /** Initialize your data structure here. */
    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        queue2.offer(x); // 先放在辅助队列中
        while (!queue1.isEmpty()){
            queue2.offer(queue1.poll());
        }
        Queue<Integer> queueTemp;
        queueTemp = queue1;
        queue1 = queue2;
        queue2 = queueTemp; // 最后交换queue1和queue2,将元素都放到queue1中
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return queue1.poll(); // 因为queue1中的元素和栈中的保持一致,所以这个和下面两个的操作只看queue1即可
    }
    
    /** Get the top element. */
    public int top() {
        return queue1.peek();
    }
    
     /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue1.isEmpty();
    }
}

C++

class MyStack {
public:
    queue<int> que1;
    queue<int> que2; // 辅助队列,用来备份
    /** Initialize your data structure here. */
    MyStack() {

    }

    /** Push element x onto stack. */
    void push(int x) {
        que1.push(x);
    }

    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int size = que1.size();
        size--;
        while (size--) { // 将que1 导入que2,但要留下最后一个元素
            que2.push(que1.front());
            que1.pop();
        }

        int result = que1.front(); // 留下的最后一个元素就是要返回的值
        que1.pop();
        que1 = que2;            // 再将que2赋值给que1
        while (!que2.empty()) { // 清空que2
            que2.pop();
        }
        return result;
    }

    /** Get the top element. */
    int top() {
        return que1.back();
    }

    /** Returns whether the stack is empty. */
    bool empty() {
        return que1.empty();
    }
};

Python

from collections import deque

class MyStack:

    def __init__(self):
        """
        Python普通的Queue或SimpleQueue没有类似于peek的功能
        也无法用索引访问,在实现top的时候较为困难。

        用list可以,但是在使用pop(0)的时候时间复杂度为O(n)
        因此这里使用双向队列,我们保证只执行popleft()和append(),因为deque可以用索引访问,可以实现和peek相似的功能

        in - 存所有数据
        out - 仅在pop的时候会用到
        """
        self.queue_in = deque()
        self.queue_out = deque()

    def push(self, x: int) -> None:
        """
        直接append即可
        """
        self.queue_in.append(x)


    def pop(self) -> int:
        """
        1. 首先确认不空
        2. 因为队列的特殊性,FIFO,所以我们只有在pop()的时候才会使用queue_out
        3. 先把queue_in中的所有元素(除了最后一个),依次出列放进queue_out
        4. 交换in和out,此时out里只有一个元素
        5. 把out中的pop出来,即是原队列的最后一个
        
        tip:这不能像栈实现队列一样,因为另一个queue也是FIFO,如果执行pop()它不能像
        stack一样从另一个pop(),所以干脆in只用来存数据,pop()的时候两个进行交换
        """
        if self.empty():
            return None

        for i in range(len(self.queue_in) - 1):
            self.queue_out.append(self.queue_in.popleft())
        
        self.queue_in, self.queue_out = self.queue_out, self.queue_in    # 交换in和out,这也是为啥in只用来存
        return self.queue_out.popleft()

    def top(self) -> int:
        """
        写法一:
        1. 首先确认不空
        2. 我们仅有in会存放数据,所以返回第一个即可(这里实际上用到了栈)
        写法二:
        1. 首先确认不空
        2. 因为队列的特殊性,FIFO,所以我们只有在pop()的时候才会使用queue_out
        3. 先把queue_in中的所有元素(除了最后一个),依次出列放进queue_out
        4. 交换in和out,此时out里只有一个元素
        5. 把out中的pop出来,即是原队列的最后一个,并使用temp变量暂存
        6. 把temp追加到queue_in的末尾
        """
        # 写法一:
        # if self.empty():
        #     return None
        
        # return self.queue_in[-1]    # 这里实际上用到了栈,因为直接获取了queue_in的末尾元素

        # 写法二:
        if self.empty():
            return None

        for i in range(len(self.queue_in) - 1):
            self.queue_out.append(self.queue_in.popleft())
        
        self.queue_in, self.queue_out = self.queue_out, self.queue_in 
        temp = self.queue_out.popleft()   
        self.queue_in.append(temp)
        return temp


    def empty(self) -> bool:
        """
        因为只有in存了数据,只要判断in是不是有数即可
        """
        return len(self.queue_in) == 0


文章来源:https://blog.csdn.net/Huacyu/article/details/135713974
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。