Stack (stack) Also known as the stack , It's an operationally constrained linear table . A linear table limited to insert and delete operations only at the end of the table . This end is called the top of the stack , relatively , Call the other end the bottom of the stack . Inserting a new element into a stack is also called a push 、 Push or push , It's putting a new element on top of the top of the stack , Make it the new top element ; Removing an element from a stack is also called making a stack or backing a stack , It removes the top element of the stack , Make its adjacent elements the new top of the stack .
Processing elements in the stack can be understood as pouring water into the cup and pouring out water , Conform to the principle of first in, last out and last in, first out .
Here are some operations on the stack :
use Python It is very simple to construct the stack from the list in the encapsulated sequence table in , We regard the end of the list as the top of the stack , Because the time complexity of adding elements at the end of the list is O(1), The time complexity of adding elements to the head of the list is O(n).
class Stack(object):
def __init__(self):
self.__list=[]
def push(self,item):
"""
Add an element at the end of the list , Time complexity O(1)( Stack pressing operation )
:return: None
"""
self.__list.append(item)
def is_empty(self):
"""
Judge whether the stack is empty
:return:
"""
return not self.__list
def pop(self):
"""
:return: Pop up top element
"""
if self.is_empty():
return None
return self.__list.pop()
def peek(self):
""" Back to top of stack element """
if self.is_empty():
return None
return self.__list[-1]
def size(self):
"""
Return the stack size
:return: len(self.__list)
"""
return len(self.__list)