Create a stack with a queue and a queue with a stack (from LetCode / Implement Stack using Queues, Implement Queue using Stacks)

(Reprinted from Blog article)

One of the important data structures is Stack and Queue, but we will address the issue of implementing them.

However, as shown in This commentary article, stacks and queues can be represented by arrays, which is a special data structure. Is not. The important difference is the following usage.

Extracts the last pushed element in the stack data structure Extract the first pushed element in the queue data structure

Implement Stack class and Queue class with the above functions.

Implement Stack using Queues

[https://leetcode.com/problems/implement-stack-using-queues/]

Implement the following operations of a stack using queues.

push(x) -- Push element x onto stack. pop() -- Removes the element on top of the stack. top() -- Get the top element. empty() -- Return whether the stack is empty.

Example:

MyStack stack = new MyStack();

stack.push(1); stack.push(2); stack.top(); // returns 2 stack.pop(); // returns 2 stack.empty(); // returns false

Notes:

You must use only standard operations of a queue -- which means only push to back, peek/pop from front, size, and is empty operations are valid. Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue. You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

First of all, from the implementation of stack. As you can see in the problem title, you are required to implement stack using queue.

Using a queue also limits the possible operations. Push is limited to the back and pop is limited to the front, as only push to back, peek / pop from front, size, and is empty operations are valid.

Wrong answer

If you do it, the test will pass even if you ignore the intent of the problem and use stack. But, of course, there is no point in creating a stack using stack. In python, list shows the behavior corresponding to stack.

class MyStack:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.stack = []
        

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

    def pop(self) -> int:
        """
        Removes the element on top of the stack and returns that element.
        """
        return self.stack.pop()
        

    def top(self) -> int:
        """
        Get the top element.
        """
        return self.stack[-1]
        

    def empty(self) -> bool:
        """
        Returns whether the stack is empty.
        """
        return len(self.stack) == 0

solution

This problem requires you to implement stack using queue, but the point is pop. Again, stack retrieves the last pushed element, while queue retrieves the first pushed element.

In python you can retrieve the first pushed element with queue.popleft (). The following solution is to use popleft to sort the queue so that the element that was pushed later comes first when you execute push.

class MyStack:

    def __init__(self):
        self.queue = collections.deque()
        

    def push(self, x: int) -> None:
        q = self.queue
        q.append(x)
        for _ in range(len(q)-1):
            q.append(q.popleft())
        

    def pop(self) -> int:
        return self.queue.popleft()
        

    def top(self) -> int:
        return self.queue[0]
        

    def empty(self) -> bool:
        return len(self.queue) == 0

The time complexity is $ O (n) $ for push and $ O (1) $ for pop.

By the way, it cannot be used under the request of this problem, but as described in the following article, there is also a pop method incollections.deque (), and the time complexity is $ O (1) $ from the back. It is possible to retrieve and delete elements.

[https://note.nkmk.me/python-collections-deque/:embed:cite]

Implement Queue using Stacks

[https://leetcode.com/problems/implement-queue-using-stacks/]

Implement the following operations of a queue using stacks.

push(x) -- Push element x to the back of queue. pop() -- Removes the element from in front of queue. peek() -- Get the front element. empty() -- Return whether the queue is empty.

Example:

MyQueue queue = new MyQueue();

queue.push(1); queue.push(2); queue.peek(); // returns 1 queue.pop(); // returns 1 queue.empty(); // returns false

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, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack. You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

Next is the implementation of Queue. Now you are asked to implement a queue using stack.

This also limits the possible operations. only push to top, peek / pop from top, size, and is empty operations are valid. This means that only list.append (x), list [-1], and list.pop () are allowed for push, peek, and pop.

solution

The following solution is to prepare two stacks, store them in the inStack when pushing, and prepare an outStack which stores the elements of the inStack in the reverse order for peek and pop, and perform processing.

class MyQueue:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.inStack, self.outStack = [], []
        

    def push(self, x: int) -> None:
        """
        Push element x to the back of queue.
        """
        self.inStack.append(x)
        

    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        self.peek()
        return self.outStack.pop()
        

    def peek(self) -> int:
        """
        Get the front element.
        """
        if(self.outStack == []):
            while(self.inStack != []):
                self.outStack.append(self.inStack.pop())
        return self.outStack[-1]
        

    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """
        return len(self.inStack) == 0 and len(self.outStack) == 0

Recommended Posts

Create a stack with a queue and a queue with a stack (from LetCode / Implement Stack using Queues, Implement Queue using Stacks)
Create a dataframe from excel using pandas
Implement a model with state and behavior
Create a tool to automatically furigana with html using Mecab from Python3
Create a Todo app with Django ④ Implement folder and task creation functions
Create a decision tree from 0 with Python and understand it (5. Information Entropy)
Create a game UI from scratch with pygame2!
Create a phylogenetic tree from Biopyton using ClustalW2
Create a web map using Python and GDAL
Create a decision tree from 0 with Python (1. Overview)
Create a Mac app using py2app and Python3! !!
Create a color sensor using a Raspberry Pi and a camera
Create a native GUI app with Py2app and Tkinter
[Python] Create a ValueObject with a complete constructor using dataclasses
Algorithm learned with Python 18th: Sorting (stack and queue)
Create a batch of images and inflate with ImageDataGenerator
Create a 3D model viewer with PyQt5 and PyQtGraph
Create a company name extractor with python using JCLdic
Create a machine learning environment from scratch with Winsows 10
[Linux] Create a self-signed certificate with Docker and apache
Create a decision tree from 0 with Python and understand it (3. Data analysis library Pandas edition)
Create a web surveillance camera with Raspberry Pi and OpenCV
Create applications, register data, and share with a single email
Let's create a PRML diagram with Python, Numpy and matplotlib.
Hash with python and escape from a certain minister's egosa
Python: Create a dictionary from a list of keys and values
Create a deploy script with fabric and cuisine and reuse it
Create a GCE instance from a GCR Docker image using terraform
Shoot time-lapse from a PC camera using Python and OpenCV
Create a homepage with django
Using a printer with Debian 10
Stack and Queue in Python
Create a heatmap with pyqtgraph
Create a directory with python
Create an API that returns data from a model using turicreate
Let's create a tic-tac-toe AI with Pylearn 2-Save and load models-
Create a temporary file with django as a zip file and return it
Create a striped illusion with gamma correction for Python3 and openCV3
Get data from MySQL on a VPS with Python 3 and SQLAlchemy
Create and deploy a Django (PTVS) app using Azure Table storage
Create a simple scheduled batch using Docker's Python Image and parse-crontab
Create a TalkBot easily using Discord.py and A3RT's Talk API (pya3rt).
I tried to create Bulls and Cows with a shell program
[Note] Using 16x2-digit character LCD (1602A) from Python with Raspberry Pi
Create a C ++ and Python execution environment with WSL2 + Docker + VSCode
Create a simple Python development environment with VS Code and Docker
Get OCTA simulation conditions from a file and save with pandas
Create and return a CP932 CSV file for Excel with Chalice