4

栈和队列精华解析

 3 years ago
source link: https://blog.csdn.net/weixin_46297209/article/details/112253867
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

一：栈和队列简介

栈和队列是使用频率最高的数据结构。栈和队列是指插入和删除只能在表的一端进行的线性表。

从数据结构的角度来看，栈和队列也是线性表，其特殊性在于栈和队列的基本操作是线性表操作的子集，它们是操作受限的线性表，因此可称为限定性的数据结构。

先进后出（限定性操作）

栈具有后进先出的特性，如果问题解决具有先进后出的天然特性的话，则求解的算法就要使用栈。比如：进制转换，括号匹配，表达式求值，函数调用，递归调用，八皇后问题，迷宫求解等。

队列（限定性操作）

队列具有先进先出的特性，如果问题解决具有先进先出的特性的话，则求解的算法就要使用队列。比如：脱机打印操作，进程按等待时间创建优先级队列，信号按接受的先后顺序依次处理。

(一)：栈的介绍

栈：限制在表的一端进行插入和删除运算的线性表

栈顶和栈底：允许插入、删除的一端称为栈顶，另一端称为栈底。

空栈：表中没有元素称为空栈

栈的运算规则：后进先出

添加元素时我们称之为入栈或压栈(push);删除元素称之为出栈(pop)

栈与一般线性表的区别：

一般线性表栈逻辑结构一对一一对一存储结构顺序表、链表顺序栈、链栈运算规则任意位置插入和删除只能在表尾插入和删除，先进后出

(二)：栈的存储

栈的存储分为顺序存储和链式存储

  1. ​ 栈的本质是线性表，线性表的存储结构对栈也适用，栈的顺序存储结构称为顺序栈。与顺序表类似，在python中使用列表来实现顺序栈，其它的语言使用数组来实现顺序栈。

    ​ 栈底位置固定不变，栈顶位置随着入栈和出栈操作而变化。用一个整型变量top存储栈顶的位置，通常称top为栈顶指针（实际是小标）。

在这里插入图片描述

代码实现：

功能函数编写

初始化一个空列表

def __init__():
	self.lst = []

def is_empty(self):
	if self.lst = []:
		return True
	return False

时间复杂度：O(1)

因为list采用的是动态顺序表技术，所以不需要判断表会不会满

def pushstack(self,item):
	self.append(item)
 	return item

时间复杂度：O(1)

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

读取栈顶元素

时间复杂度：O(1)

def peek(self):
	item = self.lst[-1]
	return item

完整代码：

class Stack:

    def __init__():
        self.lst = []

    def is_empty(self):
        if self.lst = []:
            return True
        return False

    def pushstack(self,item):
        self.append(item)
        return item

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

     def peek(self):
        item = self.lst[-1]
        return item

​ 栈的链式存储结构称为链栈，它是运算受限的单链表，插入和删除操作仅限制在表头位置上进行。

​ 在内存中开辟不连续的内存空间，元素之间的关系是通过指针的指引来实现它前继和后继的关系。

​ 时间复杂度为O(1)

在这里插入图片描述

# 定义节点类
class Node:
    def __init__(self,item):
        self.item = item
        self.next = None

# 定义栈类
class LinkTack:
    def __init__(self,node=None):
        self._top = node

def is_empty(self):
	if self._top == None:
		return True
	return False

def push(self,item):
	node = Node(item)
	node.next = self._top
	self._top = node

def pop(self):
	if self.is_empty():
		return
	else:
		p = self._top
		self._top = p.next
		return p.item

完整代码：

# 定义节点类
class Node:
    def __init__(self,item):
        self.item = item
        self.next = None

# 定义栈类
class LinkTack:
    def __init__(self,node=None):
        self._top = node

    def is_empty(self):
        if self._top == None:
            return True
        return False

    def push(self,item):
        node = Node(item)
        node.next = self._top
        self._top = node

    def pop(self):
        if self.is_empty():
            return
        else:
            p = self._top
            self._top = p.next
            return p.item

(三)：链式存储应用

    • 算法思想：若 N != 0，则将 N % r 压入栈中，即将N除进制的余数压入栈中
    • 用 N // r 代替 N
    • 若N=0，则将栈中的内容依次出栈，算法结束
    # 定义栈类
class LinkStack:
    def __init__(self,node=None):
        self._top = node

    def is_empty(self):
        if self._top == None:
            return True
        return False

    def push(self,item):
        node = Node(item)
        node.next = self._top
        self._top = node

    def pop(self):
        if self.is_empty():
            return
        else:
            p = self._top
            self._top = p.next
            return p.item

if __name__ == "__main__":
    N = int(input("输入一个待转换的十进制数："))
    r = int(input("输入要转换的进制："))
    s = LinkStack()
    while N != 0:
        s.push(N % r)
        N = N // r
    while N == 0:
        item = s.pop()
        print(item,end="")
        if s.is_empty():
            break
    print()

（四）：栈与递归

​ 栈里面每一层都装函数的栈就是函数栈，调用一个函数的时候，这个函数就入栈，这个函数调用完成了(执行到了函数的最后一个语句或者说return)，就出栈。

栈与子程序的调用：

​ 在高级语言和汇编语言编制的程序中，子程序(函数等)的调用和返回处理，在编译系统中都是采用栈来实现的。

​ 当在一个主程序调用一个子程序时，在运行该主程序前，需先将子程序之前的所有中间结果、返回地址等保存在栈中，子程序调用结束后将栈中的数据取出

​ 多个子程序嵌套调用的规则是：后调用-先返回，内存管理实行栈式管理

在这里插入图片描述

def fuc(n):
    if n == 1:
        return 1
    else:
        return fuc(n-1) * n

if __name__ == "__main__":
    print(fuc(4))

(一)：队列的定义及运算

队列(Queue)：运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。

队头(front)和队尾(rear)：允许删除的一端称为队头，允许插入的一端称为队尾

队列的运算规则：先进先出(FIFO)

队列的存储结构：

  • 顺序对垒-----循环队列

(二)：顺序队列基本操作----循环队列

​ 队列的顺序存储结构与顺序表相似，用连续的存储空间存放当前队列中的元素，另设两个指针分别指示队头和队尾元素在最烈中的位置。

​ 通常顺序存储的队列采用循环队列结构

​ 队头指针(front)：指向队头元素所在的位置。初始为空时，队头指针为0；出队时，取出队头元素，然后将队头指针加1(并返回被删元素)

​ 队尾指针(rear)：指向队尾元素。初始为空时，队头指针为0；入队时，先将新元素插入到队尾，再将队尾指针加1

入队过程：先将入队元素放在rear指针的位置，然后再将rear指针向上移动一位

出队过程：先将队头元素取出，然后将front指针向上移动一位

创建一个3个长度的对列，当对列的长度占满后，新进入的变量会存放到对列已出去元素的位置上，这就称为循环队列。

在这里插入图片描述

顺序队列结构存在的问题：

  • 设顺序表容量为M，则：
  • 当front=0,rear=M-1时，再有元素入队发生溢出-------真溢出
  • 当front=0,rear=M-1时，再有元素入队发生溢出-------假溢出

循环队列：

​ 将队列首尾连接成环形进行使用，让queue[0]接在queue[M-1]之后，若rear+1 == M，则令rear = 0

​ 在循环队列中进行出队/入队操作时，头尾指针仍要加1，向上移动。只不过头/尾指针指向队列上界(M-1)时，其加1操作的结果是指向向量的下界0。

​ 用代码描述为：

if i+1 == M:
	i=0
else:
	i += 1

​ 利用模运算可将其简化为：

i = (i+1) % M

利用求模运算表示入队、出队时指针的变化：

  • 入队：rear = (rear+1) % M
  • 出队：front = (front+1) % M

判断队列为空或满

在这里插入图片描述

如上图所示，队列为空或满时的front和rear的指针都指向同一个空间，是无法判断是空还是满的。

少用一个元素空间，即

  • 队空：front == rear
  • 队满：(rear+1)%M == front

在这里插入图片描述

代码实现循环队列：

class Queue:
    # 初始化
    def __init__(self,maxsize):
        # 定义一个一定空间的列表
        self.queue = [None] * maxsize
        # 列表的最大值
        self.maxsize = maxsize
        # 头指针初始值为0
        self.front = 0
        # 尾指针初始值为0
        self.rear = 0

    # 入队
    # 时间复杂度为O(1)
    def in_queue(self,item):
        # 判断队是否为满
        if (self.rear+1) % self.maxsize == self.front:
            print("队已满，无法插入")
        else:
            # 队尾指针处插入元素
            self.queue[self.rear] = item
            # 指针向上移动一位
            self.rear = (self.rear +1) % self.maxsize
    
    # 出队
    def out_queue(self):
        # 判断队是否为空
        if self.rear == self.front:
            print("队已空，无法取出元素")
        else:
            # 取队头元素
            front_item = self.queue[self.front]
            # 指针向后移动一位
            self.front = (self.front + 1) % self.maxsize
            # 返回队头元素
            return front_item

    # 求队中元素的个数
    def queue_nums(self):
        nums = (self.front + self.maxsize - self.rear) % self.maxsize
        return nums

    # 遍历队列
    def serch(self):
        # 新设一个队头指针
        cur = self.front
        # 队头和队尾是否相遇
        while cur != self.rear:
            print(self.queue[cur])
            # 指针后移
            cur = (cur + 1) % self.maxsize

(三)：链队列基本操作

链队列：限制仅在表头进行删除和表尾进行插入的单链表。一个链队列由一个头指针和尾指针唯一确定。

在这里插入图片描述

定义链队列中的数据节点类

# 定义节点类
class QueueNode:
    def __init__(self.item):
        self.item = item
        self.next = None

定义链队列中的表头节点类

# 定义链表头节点类
class QueueHead:
    def __init__(self):
        self.front = None
        self.rear = None

定义一个链队列类

# 定义一个链队列类
class QueueLink:
    def __init__(self):
        self._head = QueueHead()

判断队列是否为空

在这里插入图片描述

代码实现：

def is_empty(self):
	if self._head.front == self._head_rear and self._head.front == None:
		return True
	else:
		return False

在队尾添加元素，修改队尾指针

特殊情况：当队列为空时，不仅要修改队尾指针也要修改队头指针

在这里插入图片描述

代码实现：

def in_queue(self):
	# 创建节点
	node = QueueNode()
	# 判断是否为空
	if self.is_empty():
	# 如果为空则队头和队尾指针都指向这个节点
		self._head.front = node
		self._head.rear = node
	else:
		# 添加元素
		self._head.rear.next = node
		# 移动指针
		self._head.rear = node

将头指针指向头部元素的next即可完成出队

特殊情况：当队内只有一个元素时，需同时修改队头和队尾元素的指针为空

在这里插入图片描述

代码实现：

def out_queue(self):
	# 队空
	if self.is_empty():
	print("队列已空")
    
	# 队中只含一个元素
	if self._head.front == self._head.rear and self._head.front != None:
		# 取对头元素
		p = self._head.front 
		# 将头指针和尾指针指向None
		self._head.front = None
		self._head.rear = None
		return p.item
	else:  # 含有多个节点
		# 取队头元素
		p = self._head.front
		# 移动指针
		self._head.front = self._head.front.next
		return p.item

完整代码：

class QueueNode:
    def __init__(self,item):
        self.item = item
        self.next = None

class QueueHead:
    def __init__(self):
        self.front = None
        self.rear = None

class QueueLink:
    def __init__(self):
        self._head = QueueHead()

    def is_empty(self):
        if self._head.front == self._head.rear and self._head.front == None:
            return True
        else:
            return False

    def in_queue(self,item):
        node = QueueNode(item)
        if self.is_empty():
            self._head.front = node
            self._head.rear = node
        else:
            self._head.rear.next = node
            self._head.rear = node
    
    def out_queue(self):
        if self.is_empty():
            print("队列已空")        
        if self._head.front == self._head.rear and self._head.front != None:
            p = self._head.front 
            self._head.front = None
            self._head.rear = None
            return p.item
        else:  # 含有多个节点
            p = self._head.front
            self._head.front = self._head.front.next
            return p.item

_head.front = node
self._head.rear = node
else:
self._head.rear.next = node
self._head.rear = node

def out_queue(self):
    if self.is_empty():
        print("队列已空")        
    if self._head.front == self._head.rear and self._head.front != None:
        p = self._head.front 
        self._head.front = None
        self._head.rear = None
        return p.item
    else:  # 含有多个节点
        p = self._head.front
        self._head.front = self._head.front.next
        return p.item

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK