首页 > itarticle > l225 implement stack using queues

l225 implement stack using queues

admin 11月 13, 2020 0

题目描述

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.
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).`

解题思路

使用Go的list结构
使用Python实现

###Go实现

package main

import (
    "container/list"
    "fmt"
)

type MyStack struct {
    stack  *list.List
}



func () MyStack {
    mystack := MyStack{}
    mystack.stack = list.New()
    return mystack
}


/** Push element x onto stack. */
func (this *MyStack) Push(x int)  {
    this.stack.PushBack(x)
}


/** Removes the element on top of the stack and returns that element. */
func (this *MyStack) Pop() int {
    front := this.stack.Front()
    this.stack.Remove(front)
    return front.Value.(int)
}


/** Get the top element. */
func (this *MyStack) Top() int {
    if !this.Empty() {
        front := this.stack.Back()
        return front.Value.(int)
    }else{
        panic("Empty")
    }
}


/** Returns whether the stack is empty. */
func (this *MyStack) Empty() bool {
    return this.stack.Len() == 0
}


/**
 * Your MyStack object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(x);
 * param_2 := obj.Pop();
 * param_3 := obj.Top();
 * param_4 := obj.Empty();
 */

func main()  {
    obj := Constructor()
    obj.Push(1)
    obj.Push(1)
    obj.Push(2)
    fmt.Println(obj.Top())
}

Python实现

class MyStack(object):

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

    def push(self, x):
        """
        Push element x onto stack.
        :type x: int
        :rtype: void
        """
        self.stack.append(x)

    def pop(self):
        """
        Removes the element on top of the stack and returns that element.
        :rtype: int
        """
        if not self.empty():
            val = self.stack[-1]
            self.stack = self.stack[0:-1]
            return val

    def top(self):
        """
        Get the top element.
        :rtype: int
        """
        if not self.empty():
            val = self.stack[-1]
            return val

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