>

python数据结构之栈,python算法入门

- 编辑:www.bifa688.com -

python数据结构之栈,python算法入门

读书笔记

Python算法之栈(stack)的实现,pythonstack

本文以实例形式展示了Python算法中栈(stack)的实现,对于学习数据结构域算法有一定的参考借鉴价值。具体内容如下:

1.栈stack通常的操作:

Stack() 建立一个空的栈对象
push() 把一个元素添加到栈的最顶层
pop() 删除栈最顶层的元素,并返回这个元素
peek()  返回最顶层的元素,并不删除它
isEmpty()  判断栈是否为空
size()  返回栈中元素的个数

2.简单案例以及操作结果:

Stack Operation      Stack Contents   Return Value
 s.isEmpty()   []        True
 s.push(4)   [4] 
 s.push('dog')   [4,'dog'] 
 s.peek()   [4,'dog']    'dog'
 s.push(True)   [4,'dog',True] 
 s.size()   [4,'dog',True]   3
 s.isEmpty()   [4,'dog',True]   False
 s.push(8.4)   [4,'dog',True,8.4] 
 s.pop()       [4,'dog',True]   8.4
 s.pop()       [4,'dog']     True
 s.size()   [4,'dog']     2

这里使用python的list对象模拟栈的实现,具体代码如下:

#coding:utf8
class Stack:
  """模拟栈"""
  def __init__(self):
    self.items = []

  def isEmpty(self):
    return len(self.items)==0 

  def push(self, item):
    self.items.append(item)

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

  def peek(self):
    if not self.isEmpty():
      return self.items[len(self.items)-1]

  def size(self):
    return len(self.items) 
s=Stack()
print(s.isEmpty())
s.push(4)
s.push('dog')
print(s.peek())
s.push(True)
print(s.size())
print(s.isEmpty())
s.push(8.4)
print(s.pop())
print(s.pop())
print(s.size())

感兴趣的读者可以动手测试一下本文所述实例代码,相信会对大家学习Python能有一定的收获。

  栈(stack),有些地方称为堆栈,是一种容器,可存入数据元素、访问元素、删除元素,它的特点在于只能允许在容器的一端(称为栈顶端指标,英语:top)进行加入数据(英语:push)和输出数据(英语:pop)的运算。没有了位置概念,保证任何时候可以访问、删除的元素都是此前最后存入的那个元素,确定了一种默认的访问顺序。

Stack : LIFO last-in first-out

用Python语言实现一个 stack

class Stack :
# Creates an empty stack.
def __init__( self ):
self._theItems = list()
# Returns True if the stack is empty or False otherwise.
def isEmpty( self ):
return len( self ) == 0
# Returns the number of items in the stack.
def __len__ ( self ):
return len( self._theItems )
# Returns the top item on the stack without removing it.
def peek( self ):
assert not self.isEmpty(), "Cannot peek at an empty stack"
return self._theItems[-1]
# Removes and returns the top item on the stack.
def pop( self ):
assert not self.isEmpty(), "Cannot pop from an empty stack"
return self._theItems.pop()
# Push an item onto the top of the stack.
def push( self, item ):
self._theItems.append( item )

这本书里面有'Data structures and algorithms using python'自己搜一下吧。  

  由于栈数据结构只允许在一端进行操作,因而按照后进先出(LIFO, Last In First Out)的原理运作。

生活中的例子: 放书,浏览器记录等

试编写一个算法,让两个顺序栈共用一个数组stack[N],分别实现入栈出栈操作

要2个栈公用一个存储空间看来栈顶指针只能从两端开始了(和队列有点像)
设2个栈为s0,s1 ,s1初始的栈顶指针为-1,s2的初始栈顶指针为N
typedef struct
{
elemtype stack[N]; //栈存储空间
int top[2]; //top为两个栈顶指针
}St;
St s;//s为全局变量用于操作
void push(int i,elemtype e)//入栈操作,i代表栈的编号,e为入栈元素
{
if(i!=0||i!=1)exit(0);//栈号不对
if(s.top[1]-s.top[0]==1)//栈满
{
printf("FULL!");
return;
}
if(i==0)s.tack[ s.top[0]]=e;//s0入栈
if(i==1)s.tack[--s.top[1]]=e;//s1入栈
}
void pop(int i,elemtype &e)//出栈操作,i代表栈的编号,e为出栈元素
{
if(i!=0||i!=1)exit(0);//栈号不对
if(i==0)
{
if(s.top[0]==-1)//栈s0空
{
printf("EMPTY!");
return;
}
else e=s.stack[s.top[0]--];//s0出栈
}
if(i==1)
{
if(s.top[1]==N)//栈s1空
{
printf("EMPTY!");
return;
}
else e=s.stack[s.top[1] ];//s1出栈
}
}  

本文以实例形式展示了Python算法中栈(stack)的实现,对于学习数据结构域算法有一定的参考借鉴价...

必发88手机版 1

stack通常的操作:
Stack() 建立一个空的栈对象
push() 把一个元素添加到栈的最顶层
pop() 删除栈最顶层的元素,并返回这个元素
peek() 返回最顶层的元素,并不删除它
isEmpty() 判断栈是否为空
size() 返回栈中元素的个数

  栈结构实现

  栈可以用顺序表实现,也可以用链表实现。

简单案例以及操作结果:
[python] 
Stack Operation           Stack Contents     Return Value 
    s.isEmpty()     []                 True 
    s.push(4)       [4]   
    s.push('dog')       [4,'dog']     
    s.peek()        [4,'dog']          'dog' 
    s.push(True)        [4,'dog',True]    
    s.size()        [4,'dog',True]      3 
    s.isEmpty()     [4,'dog',True]      False 
    s.push(8.4)     [4,'dog',True,8.4]    
    s.pop()             [4,'dog',True]      8.4 
    s.pop()             [4,'dog']           True 
    s.size()        [4,'dog']           2 

  栈的操作

  • Stack() 创建一个新的空栈
  • push(item) 添加一个新的元素item到栈顶
  • pop() 弹出栈顶元素
  • peek() 返回栈顶元素
  • is_empty() 判断栈是否为空
  • size() 返回栈的元素个数

    class Stack(object):   def init(self):     self.item = []

      def is_empty(self):     return self.item == []

      def push(self,item):     self.item.append(item)

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

      def peek(self):     if self.is_empty():       print('stack is empty')     else:       return self.item[len(self.item)-1]

      def size(self):     return len(self.item)

    必发88手机版,  def travel(self):     for i in self.item:       print(i,end=' ')

 

Stack Operation           Stack Contents     Return Value
 s.isEmpty()     []                True
 s.push(4)     [4] 
 s.push('dog')     [4,'dog'] 
 s.peek()     [4,'dog']        'dog'
 s.push(True)     [4,'dog',True] 
 s.size()     [4,'dog',True]     3
 s.isEmpty()     [4,'dog',True]     False
 s.push(8.4)     [4,'dog',True,8.4] 
 s.pop()             [4,'dog',True]     8.4
 s.pop()             [4,'dog']         True
 s.size()     [4,'dog']         2

 

这里使用python的list对象模拟栈的实现:
[python] 
#coding:utf8  
class Stack: 
    """模拟栈""" 
    def __init__(self): 
        self.items = [] 
         
    def isEmpty(self): 
        return len(self.items)==0  
     
    def push(self, item): 
        self.items.append(item) 
     
    def pop(self): 
        return self.items.pop()  
     
    def peek(self): 
        if not self.isEmpty(): 
            return self.items[len(self.items)-1] 
         
    def size(self): 
        return len(self.items)  
     
     
s=Stack() 
print(s.isEmpty()) 
s.push(4) 
s.push('dog') 
print(s.peek()) 
s.push(True) 
print(s.size()) 
print(s.isEmpty()) 
s.push(8.4) 
print(s.pop()) 
print(s.pop()) 
print(s.size()) 

#coding:utf8
class Stack:
    """模拟栈"""
    def __init__(self):
        self.items = []
       
    def isEmpty(self):
        return len(self.items)==0
   
    def push(self, item):
        self.items.append(item)
   
    def pop(self):
        return self.items.pop()
   
    def peek(self):
        if not self.isEmpty():
            return self.items[len(self.items)-1]
       
    def size(self):
        return len(self.items)
   
   
s=Stack()
print(s.isEmpty())
s.push(4)
s.push('dog')
print(s.peek())
s.push(True)
print(s.size())
print(s.isEmpty())
s.push(8.4)
print(s.pop())
print(s.pop())
print(s.size())

 

Stack : LIFO last-in first-out 生活中的例子: 放书,浏览器记录等 stack通常的操作: Stack() 建立一个空的栈对象 push() 把一个元素添加...

本文由必发88手机版发布,转载请注明来源:python数据结构之栈,python算法入门