网站 › 『申请专区』 › 申请会员ID：luyi0405【冒充他人作品申请】

发表于 2019-10-28 11:47

申请会员ID：luyi0405【冒充他人作品申请】

1、申请ID：luyi0405
2、个人邮箱：164196046@qq.com      
3、原创技术文章：   
# 栈和队列

## 栈

```
特性：先进后出的数据结构
应用：每个web浏览器都有一个返回按钮，当你浏览网页时，这些网页被放置在一个栈中(网页的网址)。你现在查看网页的地址存储在栈的顶部，你第一个查看网页的地址存储在栈的底部。如果按"返回"按钮，将按相反的顺序浏览刚才的页面。
```

### 栈的方法

```
Stack()   创建一个空的新栈。他不需要参数，返回创建的新栈
push(item)将一个新数据添加到栈的顶部,他需要item参数，并且不返回任何内容
pop()   从栈中删除顶部项，他不需要参数并返回item。栈被修改
peek()    从栈返回顶部项，但不会删除它，不需要参数，不修改栈
isEmpty() 测试栈是否为空。不需要参数，返回布尔值
size()    返回栈中item数量。不需要参数，并返回一个整数
```

### python第三方库栈的实现

```
from pythonds.basic.stack import Stack
s=Stack()       #实例化创建一个栈

s.push("11")    #向栈顶部放入数据
s.push("22")
s.push("33")
s.push("44")
print(s.size())   #查看栈中有多少个元素
print(s.pop())    #取出栈顶部第一个元素
print(s.peek())   #返回栈顶第一个元素
print(s.isEmpty())#判断栈是否为空
```

### 自定义栈的实现

```
class Stack():
    def __init__(self):                        #使用列表实现栈
      self.li=[]
    def push(self,item):               #向栈顶部放入数据
      self.li.append(item)
    def pop(self):                              #取出栈顶部第一个元素
      ret=self.li.pop()
      return ret
    def peek(self):                              #返回栈顶第一个元素
      ret=self.li[-1]
      return ret
    def size(self):                              #查看栈中有多少个元素
      ret=len(self.li)
      return ret
    def isEmpty(self):                        #判断栈是否为空
      return self.li==[]

s=Stack()
s.push(1)
s.push("11")    #向栈顶部放入数据
s.push("111")
s.push("33")
s.push("44")
print(s.size())   #查看栈中有多少个元素
print(s.pop())    #取出栈顶部第一个元素
print(s.peek())   #返回栈顶第一个元素
print(s.isEmpty())#判断栈是否为空
```

## 队列

```
队列：先进先出
应用场景：我们的计算机实验室有 30 台计算机与一台打印机联网。当学生想要打印时，他们的打印任务与正在等待的所有其他打印任务“一致”。第一个进入的任务是先完成。如果你是最后一个，你必须等待你前面的所有其他任务打印
```

### 队列的方法

```
Queue() 创建一个空的新队列。 它不需要参数，并返回一个空队列。
put(item) 将新项添加到队尾。 它需要 item 作为参数，并不返回任何内容。
get() 从队首移除项。它不需要参数并返回 item。 队列被修改。
empty() 查看队列是否为空。它不需要参数，并返回布尔值。
qsize() 返回队列中的项数。它不需要参数，并返回一个整数。
```

### python第三方库中的队列方法

```
from queue import Queue
q=Queue()         #实例化一个队列
q.put("sss")      #向队列里放入一个元素
q.put("aaa")
q.put("ddd")

print(q.get())      #从队列取出第一个元素
print(q.empty())    #判断队列是否为空
print(q.qsize())    #查看队列的长度
```

### 自定义队列

```
class Queue():
    def __init__(self):                        #使用列表完成队列的实现
      self.li=[]
    def put(self,item):                        #向队列里放入一个元素
      self.li.append(item)
    def get(self):                              #从队列取出第一个元素
      return self.li.pop(0)
    def empty(self):                        #判断队列是否为空
      return self.li==[]
    def qsize(self):                        #查看队列的长度
      return len(self.li)

q=Queue()                        #实例化一个队列
q.put('11')
q.put('22')
q.put('33')

print(q.get())                #从队列取出第一个元素
print(q.empty())      #判断队列是否为空
print(q.qsize())      #查看队列的长度
```

## 双端队列

```
同队列相比，有两个头部和尾部。可以在双端进行数据的插入和删除，提供了单数据结构中栈和队列的特性
```

### 双端队列的方法

```
append()                在双端队列队尾添加一个元素
appendleft()      在双端队列队首添加一个元素
pop()                        删除双端队列队尾的元素
popleft()                删除双端队列队首的元素
reverse()                将双端队列反转(无返回值)
clear()                        清空双端队列(无返回值)
```

### python第三方库中的双端队列

```
from collections import deque

dq=deque(['1','2','3'])         #实例化一个双端队列

print(dq)                   #查看双端队列
dq.append("aa")             #在双端队列队尾添加一个元素
print(dq)
dq.appendleft("bb")         #在双端队列队首添加一个元素
print(dq)
print(dq.pop())             #删除双端队列队尾的元素
print(dq.popleft())         #删除双端队列队首的元素
dq.reverse()         #将双端队列反转(无返回值)
dq.clear()         #清空双端队列(无返回值)
print(dq)
```

### 自定义双端队列

```
class Dequeue():
    def __init__(self,*args,**kwargs):
      if args:                              #方便用户通过实例化时传值直接创建双端队列
            self.li=list(args)
      else:
            self.li=list(kwargs)

    def __str__(self):                        #打印队列时，返回字符串形式的队列
      return str(self.li)


    def append(self,item):                #在双端队列队尾添加一个元素
      self.li.append(item)

    def appendleft(self,item):      #在双端队列队首添加一个元素
      self.li.insert(0,item)

    def pop(self):                              #删除双端队列队尾的元素
      return self.li.pop()

    def popleft(self):                        #删除双端队列队首的元素
      return self.li.pop(0)

    def reverse(self):                        #将双端队列反转(无返回值)
      self.li.reverse()

    def clear(self):                        #清空双端队列(无返回值)
      self.li=[]

dq=Dequeue()
dq.append("11")                #在双端队列队尾添加一个元素
dq.append("22")
dq.append("33")
print(dq)                        #查看双端队列
dq.append("aa")
dq.appendleft("bb")                #在双端队列队首添加一个元素

print(dq.pop())                        #删除双端队列队尾的元素
print(dq.popleft())                #删除双端队列队首的元素
dq.reverse()                        #将双端队列反转(无返回值)
print(dq)
dq.clear()                              #清空双端队列(无返回值)
print(dq)
```

## 优先级队列

```
import heapq

#利用heapq实现一个简答的优先级队列
class PriorityQueue:
    def __init__(self):
      self._queue=[]
      self._index=0
    def push(self,item,priority):
      heapq.heappush(self._queue,(-priority,self._index,item))
      self._index+=1
    def pop(self):
      return heapq.heappop(self._queue)[-1]

class Item:
    def __init__(self,name):
      self.name=name

    def __repr__(self):
      return 'Item({!r})'.format(self.name)

if __name__ == '__main__':
    q=PriorityQueue()
    q.push(Item('foo'),1)
    q.push(Item('bar'),5)
    q.push(Item('spam'),4)
    q.push(Item('grok'),1)

    print(q.pop())
    print(q.pop())
    #具有相同优先级的两个元素，返回的顺序同它们插入到队列时的顺序相同
    print(q.pop())
    print(q.pop())
```

## 线程安全的栈

```
from queue import LifoQueue #LIFO队列
lifoQueue = LifoQueue()
lifoQueue.put(1)
lifoQueue.put(2)
lifoQueue.put(3)
print('LIFO队列',lifoQueue.queue)
lifoQueue.get() #返回并删除队列尾部元素
lifoQueue.get()
print(lifoQueue.queue)
```

Hmily 发表于 2019-10-28 14:31

随手搜到处都是，是你原创？https://www.cnblogs.com/konghui/p/10876850.html

深巷丶 发表于 2019-11-4 23:27

又是你，整天复制粘贴过来申请账号，真当管理是傻的？

错过了一个亿 发表于 2019-11-27 16:50

连标题都一样

ivyboy 发表于 2019-12-30 16:07

查看完整版本: 申请会员ID：luyi0405【冒充他人作品申请】