用python写算法——栈笔记

栈的定义

1.它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。（来自百度）

特征: 后进先出LIFO（last-in,first-out）
栈的基本操作：

• 进栈：push

• 出栈：pop

• 取栈顶：gettop
  在python中可以用列表实现栈。

• 进栈：li.append

• 出栈：li.pop

• 取栈顶：li[-1]

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, element):
        self.stack.append(element)

    def pop(self):
        return self.stack.pop()

    def get_top(self):
	    # if len(self.stack) > 0:
	    if not self.empty():
	        return self.stack[-1]
	    else:
	        return None

    def empty(self):
        if len(self.stack) == 0:
            return True
        else:
            return False
   		
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.get_top())

结果是：取出栈顶元素3

3

相关算法题

1.用两个栈实现队列
牛客网：用两个栈实现队列
描述
用两个栈来实现一个队列，使用n个元素来完成 n 次在队列尾部插入整数(push)和n次在队列头部删除整数(pop)的功能。 队列中的元素为int类型。保证操作合法，即保证pop操作时队列内已有元素。

class Solution:
    def __init__(self):
        self.stack_in = []
        self.stack_out = []

    def push(self, element):
        self.stack_in.append(element)

    def empty(self):
        if len(self.stack_in) == 0 and len(self.stack_out) == 0:
            return True
        else:
            return False

    def pop(self):
        if self.empty():
            return None

        if self.stack_out:
            return self.stack_out.pop()
        else:
            while self.stack_in:
                self.stack_out.append(self.stack_in.pop())
            return self.stack_out.pop()


#result = Solution()
#result.push(1)
#result.push(2)
#result.push(3)

#print(result.pop())