精华内容
下载资源
问答
  • 2022-01-23 21:57:09

    关注公众号:AI悦创,阅读前面文章。

    你好,我是久远,上次我们进行了关于栈的讲解,我们先来对知识进行回顾:

    • 什么是栈

    栈是有序集合,队列元素的增添和移除总是发生在同一端的,这一端我们称之为栈顶,另一端称之为栈底,栈中的元素离底端越近,代表其在栈中的时间越长,最新添加的元素将被最先移除。这种排序原则被称作 LIFO(last-in first-out),即后进先出。它提供了一种基于在集合中的时间来排序的方式。最近添加的元素靠近顶端,旧元素则靠近底端。

    AI悦创·推出辅导班啦,包括「Python 语言辅导班、C++辅导班、算法/数据结构辅导班、少儿编程、pygame 游戏开发」,全部都是一对一教学:一对一辅导 + 一对一答疑 + 布置作业 + 项目实践等。QQ、微信在线,随时响应!V:Jiabcdefh

    • 栈的重要操作

    栈中最重要的两个操作是出栈和入栈,我们在 python 中一般通过列表来实现栈的出入。

    接下来我们来进行队列的学习,队列和栈一样,是非常简单的数据结构,但是也是非常常见的数据结构。


    什么是队列

    队列和栈一样,也是有序集合,但它不同于栈的地方在于,队列中的元素是从一端进入,另一端出去。添加操作发生在“尾部”,移除操作则发生在“头部”。新元素从尾部进入队列,然后一直向前移动到头部,直到成为下一个被移除的元素。最新添加的元素必须在队列的尾部等待,在队列中时间最长的元素则排在最前面。这种排序原则被称作 FIFO(first-in first-out),即先进先出,也称先到先得。

    队列字如其名,它的例子在生活中也是比比皆是的,我们现实中的排队即为队列的应用。

    日常生活中,我们进电影院要排队,在超市结账要排队,好的队列只允许一头进,另一头出,不可能发生插队或者中途离开的情况。

    队列的实现

    队列的实现分为队列的定义和操作,如前所述,队列是元素的有序集合,添加操作发生在其尾部,移除操作则发生在头部。队列的操作顺序是 先进先出(FIFO),它支持以下操作。

    • Queue() :创建一个空队列。它不需要参数,且会返回一个空队列。
    • enqueue( item ) :在队列的尾部添加一个元素。它需要一个元素作为参数,不返回任何值。
    • dequeue() :从队列的头部移除一个元素。它不需要参数,且会返回一个元素,并修改队 列的内容。
    • isEmpty() :检查队列是否为空。它不需要参数,且会返回一个布尔值。
    • size() : 返回队列中元素的数目。它不需要参数,且会返回一个整数。

    创建一个新类来实现队列抽象数据类型是十分合理的。像之前一样,我们利用简洁强大的列 表来实现队列。 既然要创建队列,我们首先要确认队列的头尾,在这里我们假设队列的尾部在列表的位置 0 处。

    首先我们对队列类进行定义,一个队列中最主要最核心的要素就是队列中的元素,而新生成一个队列时,这个队列中往往没有任何元素,因此我们对队列的初始化定义为:队列中的元素为空,即引用的列表为空列表。

    代码如下:

    class Queue:
        def __init__(self):
            self.items = []
    

    当一个队列生成以后,最常见的计算队列长度的操作是必不可少的,因此只需要计算引入列表的长度即可。

    代码如下:

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

    既然可以计算长度,那么我们也可以判断队列是否为空,通常我们只需判断引入的列表是否为空列表即可判断队列是否为空了。

    代码如下:

    def isEmpty(self):
            return self.items == []
    

    接下来就是我们似曾相识,但是又用途非常广泛的两种操作了,插入和删除,我们在前面讲解栈的时候进行了出栈和入栈的操作,而在队列中也有类似的操作,即入队和出队,而队列和栈最大的不同便是,入队和出队并不是在同一个地方执行的。添加操作发生在“尾部”,移除操作则发生在“头部”。

    我们在此设引入的列表的 0 号位为队列的尾部,传入要插入的元素 item ,默认将其插入到列表首位,即队列的入队操作,代码如下:

    def enqueue(self, item):
            self.items.insert(0,item)
    

    我们在此设引入的列表的表尾为队列的头部,要进行出队操作,只需删除列表的最后一个元素即可。代码如下:

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

    整体的代码如下:

    class Queue:
        def __init__(self):
            self.items = []
            
        def isEmpty(self):
            return self.items == []
        
        def size(self):
            return len(self.items)
        
        def enqueue(self, item):
            self.items.insert(0,item)
            
        def dequeue(self):
            return self.items.pop()
    

    总结

    恭喜你又学完了一个知识点,队列和栈的知识是不是很简单呢?只需要掌握列表的一些要点,就可以轻松的将队列和栈实现,我们在基础篇只讲解了最基础的实现方法,在后续的提高篇里会告诉大家在考试或者就业面试中,站和队列要怎么运用。

    流沙团队联合AI悦创|久远·推出辅导班啦,包括「Python 语言辅导班、C++ 辅导班、java 辅导班、算法/数据结构辅导班、少儿编程、pygame 游戏开发」,全部都是一对一教学:一对一辅导 + 一对一答疑 + 布置作业 + 项目实践等。QQ、微信在线,随时响应!

    更多相关内容
  • 你好我是久远,我们来复习一下上周我们讲的知识。 什么是链表? 在计算机科学中,链表是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针。 ...

    从博客查看此篇文章
    你好我是久远,我们先来复习一下上周我们讲的知识。

    • 什么是链表?

    在计算机科学中,链表是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针。

    • 链表的优点

    由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比数组快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而顺序表相应的时间复杂度分别是O(logn)和O(1)。使用链表结构可以克服数组链表需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大。

    什么是栈

    栈有时也被称作堆栈或者堆叠。栈是有序集合,它的添加,移除操作总是发生在同一端,设这一端为顶端,则未执行操作的一端为底端。
    栈中的元素离底端越近,代表其在栈中的时间越长,最新添加的元素将被最先移除。这种排序原则被称作 LIFO(last-in first-out),即后进先出。它提供了一种基于在集合中的时间来排序的方式。最近添加的元素靠近顶端,旧元素则靠近底端。

    生活中的例子:

    在我们的生活中也很常见关于栈的例子,假设我们有一个放羽毛球的球桶,我们只能从桶的上面取出球,底部是不能取的,靠近开口的球,更先被取到。

    既然有取出的先后,那么我们的栈也算是有顺序的,我们依旧使用列表来实现栈的一些操作。

    举例来说,对于列表[1, 5, 3, 7, 8, 6],只需要考虑将它的哪一边视为栈的顶端。一旦确定了顶端,所有的操作就可以利用 append 和pop 等列表方法来实现。

    在这里我们视列表的尾部为栈顶,因此当进行 push 操作时,新的元素会被添加到列表的尾部。pop 操作同样会修改这一端。

    栈的操作

    我们前面已经介绍了栈的基本情况,既然我们要实现栈的操作,那我们肯定要新建一个栈,有了这个栈,我们肯定要做一些彰显出栈特性的事情————出栈,入栈。还有我们常见的操作,判断是否为空,判断栈的大小等等。

    以下是我们要实现的方法:

    • Stack()创建一个空栈。不传任何参数,返回空栈。
    • push(item)将一个元素添加到栈的顶端。它需要一个参数 item,且无返回值。
    • pop()将栈顶端的元素移除。它不需要参数,但会返回顶端的元素,并且修改栈的内容。
    • peek()返回栈顶端的元素,但是并不移除该元素。它不需要参数,也不会修改栈的内容。
    • isEmpty()检查栈是否为空。它不需要参数,且会返回一个布尔值。
    • size()返回栈中元素的数目。它不需要参数,且会返回一个整数。

    栈的定义

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

    定义一个 stack 类来告诉计算机,我们现在定义了一个全新的类型叫做 stack ,每个类有一个定义方法即 init() ,我们使用 init 方法来定义栈的一些属性。我们新建一个栈,栈中最重要的就是元素,多个元素构成栈,而一开始当我们没有向栈中放入任何元素时,栈是空的,因此有 self.items = [],我们定义了一个空栈来作为栈的初始化。

    栈是否为空

    既然栈存在,我们就可以进行栈有无的判断,我们也像之前的数据结构类型一样,引入 isEmpty() 方法来判断栈中是否有元素,没有元素则为空栈,返回 true ;包含有元素,则说明栈不为空,返回 false。

    def isEmpty(self):
            return self.items == []
    

    栈的大小

    栈的大小实际上就是判断栈中有多少元素,而我们使用列表来进行栈的实现,因此我们只需要使用 len() 方法计算引入的列表的长度即可判断栈中元素的多少了,即栈的大小。

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

    入栈操作

    现在我们既可以判断栈中是否有元素,又可以判断栈的大小了,那么接下来就要实现栈最主要的两个操作了,入栈和出栈。

    进行入栈操作我们就要想到,既然要把元素加入到栈中,那么我们就要传入一个参数去表示要加入到栈中的元素,然后将这个参数加入到栈中即可。

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

    我们传入一个 item 参数,为我们要加入到栈中的元素,然后将其加入到我们引入的 items 列表中即可完成栈中元素的加入了。

    出栈操作

    既然有元素加入到栈中,那我们就可以将元素从栈中删除,因此我们有了出栈的操作,出栈操作一般的思维是这样的:我们让栈顶的元素弹出,同时也要告诉大家,我弹出的是哪个元素。

    因此要返回弹出的那个元素。

    代码实现为:

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

    使用列表中的 pop方法,返回列表末尾的那个元素,并将该元素从列表中删除,实现出栈。

    查看栈顶

    我们的栈操作中通常还包含一项查看栈顶元素的操作,因为我们在此将引入的列表末尾视为栈顶,因此我们只需要返回所引入的列表的最后一个元素即可。

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

    整体的代码如下:

    class Stack:
        def __init__(self):
            self.items = []
        def isEmpty(self):
            return self.items == []
        def size(self):
            return len(self.items)
        def push(self, item):
            self.items.append(item)
        def pop(self):
            return self.items.pop()
        def peek(self):
            return  self.items[len(self.items)-1]
    

    总结

    恭喜你又学完了一个知识点,栈是一个后进先出的数据类型,它有两个非常主要的操作,进栈和出栈:

    • 进栈:将资料放入栈的顶端,栈的顶端移到新放入的资料。
    • 出栈:将堆栈顶端资料移除,堆栈顶端移到移除后的下一笔资料。

    它可以用数组或者链表来实现,而由于 python 的特殊性,我们常使用列表来实现栈的操作。

    与栈相对的有队列,队列是一种先进先出的数据类型,我们下次会进行讲解。

    流沙团队联合AI悦创|久远·推出辅导班啦,包括「Python 语言辅导班、C++ 辅导班、java 辅导班、算法/数据结构辅导班、少儿编程、pygame 游戏开发」,全部都是一对一教学:一对一辅导 + 一对一答疑 + 布置作业 + 项目实践等。QQ、微信在线,随时响应!


    在这里插入图片描述

    展开全文
  • 实现数据结构中的栈---后进先出LIFO

    千次阅读 2020-06-18 12:17:21
    书本整齐跨一叠在一起,最后放在最上面的那本最先拿走,生活中有很多后进先出的列子,就不一一说明了,用图来说明应该很好理解。 放在最上面的那本书的位置叫栈顶,栈顶是可变的,比如说你拿走了西游记,那么栈顶...

    栈是什么?如果用生活中最常见的例子,我想到是书本的放置(当然这是部分人喜欢的做法)。但是给人的感觉是非常直接的,书本整齐跨一叠在一起,放在最上面的那本最先拿走,放在最底下那本书就最后拿走,形象吧,生活中有很多后进先出的栗子,就不一一说明了,用图来说明应该很好理解。
    在这里插入图片描述

    放在最上面的那本书的位置叫栈顶,栈顶是可变的,比如说你拿走了西游记,那么栈顶就是红楼梦得位置。相对应的栈底是不可操作的一端。
    栈是一种特殊的线性表,特殊之处在于只能在一端对其进行操作,把元素放到栈中,这操作叫压栈(push),压栈之后,栈顶指针就向上移动。把元素从栈顶弹出,这叫出栈(pop),出栈后栈顶指针向下移动。访问栈只能从栈顶元素进行。栈是很重要的数据结构,在很多算法都有应用,比如图的深度优先遍历算法(DFS),Dijkstra算法的中转站。

    栈的实现分为两种,一是顺序栈,用数组来实现,二是链式栈,用指针将结点串联起来,与链表相似,但仅能在栈顶进行操作。

    先实现简单的顺序栈,顺序栈简直不要太简单,上代码:

    #ifndef STATICSTACK_H
    #define STATICSTACK_H
    
    template <typename T, int N>
    class StaticStack
    {
    protected:
    	T array[N];	// 使用模板参数决定栈的大小
    	int m_top;	// 使用整型作为标记,相当于栈顶指针
    	int m_size;	// 栈中数据元素的个数
    public:
    	StaticStack()	// 初始化操作得做一下
    	{
    		m_top = -1;
    		m_size = 0;
    	}
    	
    	bool push(const T& obj)	// 压栈操作,就是往数组增加一个元素
    	{
    		bool ret = m_size < N;	// 满了就没办法了
    		
    		if( ret )
    		{
    			array[++m_top] = obj;
    			++m_size;
    		}
    		
    		return ret;
    	}
    	
    	bool pop()	// 出栈操作
    	{
    		bool ret = m_size > 0;
    		
    		if( ret )
    		{
    			--m_top;
    			--m_size;
    		}
    		
    		return ret;
    	}
    	
    	T top()	// 获取栈顶元素
    	{
    		return array[m_top];
    	}
    	
    	void clear()	// 把栈清空
    	{
    		m_top = -1;
    		m_size = 0;
    	}
    	
    	int size()	// 获取栈的大小
    	{
    		return m_size;
    	}
    	
    	~StaticStack()
    	{
    		clear();
    	}
    };
    
    #endif

    来用一下这个简单顺序栈。记住,后进先出!

    #include <iostream>
    #include "StaticStack.h"
    
    using namespace std;
    
    int main(int argc, const char* argv[])
    {
    	StaticStack<int, 10> stack;
    
    	for(int i = 0; i < 10; ++ i)
    	{
    		stack.push(i);
    	}
    	// 入栈的时候是 0123456789 的顺序
    	
    	for(int i = 0; i < 10; ++ i)
    	{
    		cout << stack.top() << endl;
    		stack.pop();
    	}
    	
    	return 0;
    }

    在这里插入图片描述

    输出正确。OK,顺序栈就可以跳过了,因为顺序栈的实现依赖于原生数组,所以在定义的时候必须给定大小,并且在使用的过程中不能动态改变其大小,这是顺序栈的一个缺点,另外,当顺序栈存放的元素是类类型,那么在定义顺序栈时就会自动调用类的构造函数,有多少个元素就会调用多少次,这样做显然会降低效率,所以顺序栈的使用相对较少。

    现在重点来实现链式栈吧,有了顺序栈的基础,实现链式栈也相当容易。
    直接上代码:

    #ifndef LINKSTACK_H
    #define LINKSTACK_H
    
    template <typename T>
    class LinkStack
    {
    protected:
    	struct Node
    	{
    		T data;
    		Node* next;
    	};
    	mutable Node header;	// 使用头节点会方便各种操作
    	int m_size;
    	
    public:
    	LinkStack()
    	{
    		header.next = NULL;
    		m_size = 0;
    	}
    	
    	bool push(const T& obj)	// 压栈操作
    	{
    		bool ret = true;	
    		Node* n = new Node();
    		
    		if( n != NULL )
    		{
    			n->data = obj;
    			Node* current = &header;	// 相当于链表的头插
    			n->next = current->next;
    			current->next = n;
    			++m_size;
    		}
    		else
    		{
    			ret = false;
    		}
    		
    		return ret;
    	}
    	
    	bool pop()	// 出栈操作
    	{
    		bool ret = true;
    		
    		if( m_size > 0 )
    		{
    			Node* current = &header;	// 相当于链表的头删
    			Node* todel = current->next;
    			current->next = todel->next;
    			--m_size;
    			delete todel;
    		}
    		else
    		{
    			ret = false;
    		}
    		
    		return ret;
    	}
    	
    	T top() const	// 获取栈顶元素
    	{
    		Node* current = header->next;
    		
    		return current->data;
    	}
    	
    	int size() const
    	{
    		return m_size;
    	}
    	
    	void clear()	// 清空栈
    	{
    		while( m_size > 0 )
    		{
    			pop();
    		}
    	}
    	
    	~LinkStack()
    	{
    		clear();
    	}
    };
    
    #endif

    仅仅是实现一个栈好像没有什么好玩的,顺序栈操作一个数组,链式就几个指针操作。现在用栈来实现一个扫描函数,将字符串中的左右符号进行匹配。举个栗子,“( a { b c [ d < e " f ’ g’ " h > i ] j } k)”,这样一个看起来复杂l凌乱的字符串,怎么知道它的左右符号匹不匹配呢?人工智能嘛,人工来数一下不就可以了吗?Good idea!简单的数几分钟就应该知道结果了,要是一本书那么多的字符串怎么来数?当然是把工作交给计算机!写个程序来检查左右符号是否匹配不就得了。主要注意的地方是左符号、右符号以及引号的处理,其他字符直接忽略。知道重点了,实现就容易了,说干就干,动手!

    #include <iostream>
    #include "LinkStack.h"
    
    // 需要提前准备相应的辅助函数
    bool is_Left(const char c)	// 判断是否为左符号
    {
    	return (c == '(') || (c == '{') || (c == '<') || (c == '[');
    }
    
    bool is_Right(const char c)	// 判断是否为右符号
    {	
    	return (c == ')') || (c == '}') || (c == '>') || (c == ']');
    }
    	
    bool is_Quot(const char c)	// 判断是否为引号
    {
    	return (c == '\'') || (c == '\"');
    }
    
    bool is_Match(const char l,const char r)	// 进行匹配判断
    {
    	bool ret = ( (l == '(') && (r == ')') )   ||
    		   ( (l == '{') && (r == '}') )   ||
    		   ( (l == '[') && (r == ']') )   ||
    		   ( (l == '<') && (r == '>') )   ||
    		   ( (l == '\'') && (r == '\'') ) ||
    		   ( (l == '\"') && (r == '\"') ) ;	
    		   
    	return ret;
    }
    
    bool scan_func(const char* str)	// 扫描字符串的函数
    {
    	bool ret = true;	
    	int i = 0;
    	str = str ? str : "";	// 参数合法性判断,如果参数为空,则用空字符串代替
    	LinkStack<char> stack;	// 看着怎么使用栈吧
    
    	while( ret && (str[i] != '\0') )	// 循环遍历字符串
    	{					// 如果有不匹配的字符就立即结束循环
    		if( is_Left(str[i]) )		// 左符号,直接入栈
    		{
    			stack.push(str[i]);
    		}
    		else if( is_Right(str[i]) )	// 右符号,判断栈是否为空
    		{				// 如果栈为空,结束循环
    			if( (stack.size() > 0) && (is_Match(stack.top(), str[i])) )		
    			{
    				stack.pop();	// 栈不为空,且与栈顶元素能匹配,那就把栈顶中的左符号出栈
    			}
    			else
    			{
    				ret = false;	
    			}
    		}
    		else if( is_Quot(str[i]) )	// 引号判断
    		{				// 如果栈为空或者与栈顶元素不匹配,入栈
    			if( (stack.size() == 0) || (!is_Match(stack.top(), str[i])) )
    			{
    				stack.push(str[i]);
    			}			// 与栈顶元素匹配,那就将栈顶的引号出栈
    			else if( is_Match(stack.top(), str[i]) )
    			{
    				stack.pop();
    			}
    		}
    	}
    	
    	return (ret && (stack.size() == 0) );
    }
    
    int main(int argc, const char* argv[])
    {
    	const char* str1 = " < ( [ { 123 } ] ) > ";
    	const char* str2 = " \" \' 123 \' \" ";
    	const char* str3 = "< 123 ";
    
    	cout << endl;
    	cout << str1 << " result of match : " << ( scan_func(str1) ? " true " : " false " ) << endl;
    	
    	cout << endl;
    	cout << str2 << " result of match : " << ( scan_func(str2) ? " true " : " false " ) << endl;
    	
    	cout << endl;
    	cout << str3 << " result of match : " << ( scan_func(str3) ? " true " : " false " ) << endl;
    	
    	
    	return 0;
    }

    看看输出结果,多easy,要是用人工的智能来数,得花点点点时间。

    在这里插入图片描述

    展开全文
  • 这种排序原则被称作 LIFO(last-in first-out),即后进先出。它提供了一种基于在集合中的时间来排序的方式。最近添加的元素靠近顶端,旧元素则靠近底端。 栈的重要操作 栈中最重要的两个操作是出栈和入栈,我们在...

    你好,我是久远,上次我们进行了关于栈的讲解,我们先来对知识进行回顾:

    • 什么是栈

    栈是有序集合,队列元素的增添和移除总是发生在同一端的,这一端我们称之为栈顶,另一端称之为栈底,栈中的元素离底端越近,代表其在栈中的时间越长,最新添加的元素将被最先移除。这种排序原则被称作 LIFO(last-in first-out),即后进先出。它提供了一种基于在集合中的时间来排序的方式。最近添加的元素靠近顶端,旧元素则靠近底端。

    • 栈的重要操作

    栈中最重要的两个操作是出栈和入栈,我们在 python 中一般通过列表来实现栈的出入。

    接下来我们来进行队列的学习,队列和栈一样,是非常简单的数据结构,但是也是非常常见的数据结构。


    什么是队列

    队列和栈一样,也是有序集合,但它不同于栈的地方在于,队列中的元素是从一端进入,另一端出去。添加操作发生在“尾部”,移除操作则发生在“头部”。新元素从尾部进入队列,然后一直向前移动到头部,直到成为下一个被移除的元素。最新添加的元素必须在队列的尾部等待,在队列中时间最长的元素则排在最前面。这种排序原则被称作 FIFO(first-in first-out),即先进先出,也称先到先得。

    队列字如其名,它的例子在生活中也是比比皆是的,我们现实中的排队即为队列的应用。

    日常生活中,我们进电影院要排队,在超市结账要排队,好的队列只允许一头进,另一头出,不可能发生插队或者中途离开的情况。

    队列的实现

    队列的实现分为队列的定义和操作,如前所述,队列是元素的有序集合,添加操作发生在其尾部,移除操作则发生在头部。队列的操作顺序是 先进先出(FIFO),它支持以下操作。

    • Queue() :创建一个空队列。它不需要参数,且会返回一个空队列。
    • enqueue( item ) :在队列的尾部添加一个元素。它需要一个元素作为参数,不返回任何值。
    • dequeue() :从队列的头部移除一个元素。它不需要参数,且会返回一个元素,并修改队 列的内容。
    • isEmpty() :检查队列是否为空。它不需要参数,且会返回一个布尔值。
    • size() : 返回队列中元素的数目。它不需要参数,且会返回一个整数。

    创建一个新类来实现队列抽象数据类型是十分合理的。像之前一样,我们利用简洁强大的列 表来实现队列。 既然要创建队列,我们首先要确认队列的头尾,在这里我们假设队列的尾部在列表的位置 0 处。

    首先我们对队列类进行定义,一个队列中最主要最核心的要素就是队列中的元素,而新生成一个队列时,这个队列中往往没有任何元素,因此我们对队列的初始化定义为:队列中的元素为空,即引用的列表为空列表。

    代码如下:

    class Queue:
        def __init__(self):
            self.items = []
    

    当一个队列生成以后,最常见的计算队列长度的操作是必不可少的,因此只需要计算引入列表的长度即可。

    代码如下:

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

    既然可以计算长度,那么我们也可以判断队列是否为空,通常我们只需判断引入的列表是否为空列表即可判断队列是否为空了。

    代码如下:

    def isEmpty(self):
            return self.items == []
    

    接下来就是我们似曾相识,但是又用途非常广泛的两种操作了,插入和删除,我们在前面讲解栈的时候进行了出栈和入栈的操作,而在队列中也有类似的操作,即入队和出队,而队列和栈最大的不同便是,入队和出队并不是在同一个地方执行的。添加操作发生在“尾部”,移除操作则发生在“头部”。

    我们在此设引入的列表的 0 号位为队列的尾部,传入要插入的元素 item ,默认将其插入到列表首位,即队列的入队操作,代码如下:

    def enqueue(self, item):
            self.items.insert(0,item)
    

    我们在此设引入的列表的表尾为队列的头部,要进行出队操作,只需删除列表的最后一个元素即可。代码如下:

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

    整体的代码如下:

    class Queue:
        def __init__(self):
            self.items = []
            
        def isEmpty(self):
            return self.items == []
        
        def size(self):
            return len(self.items)
        
        def enqueue(self, item):
            self.items.insert(0,item)
            
        def dequeue(self):
            return self.items.pop()
    

    总结

    恭喜你又学完了一个知识点,队列和栈的知识是不是很简单呢?只需要掌握列表的一些要点,就可以轻松的将队列和栈实现,我们在基础篇只讲解了最基础的实现方法,在后续的提高篇里会告诉大家在考试或者就业面试中,站和队列要怎么运用。

    流沙团队联合AI悦创|久远·推出辅导班啦,包括「Python 语言辅导班、C++ 辅导班、java 辅导班、算法/数据结构辅导班、少儿编程、pygame 游戏开发」,全部都是一对一教学:一对一辅导 + 一对一答疑 + 布置作业 + 项目实践等。QQ、微信在线,随时响应!

    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 概念很简单,栈 (Stack)是一种后进先出(last in first off,LIFO)的数据结构,而队列(Queue)则是一种先进先出 (fisrt in first out,FIFO)的结构,如下图: 2.实现 现在来看如何实现以上的两个数据...
  • 简单栈的两道例子

    千次阅读 2018-03-22 23:03:13
    引言 两道关于栈的简单例子: 1.单词逆序 用栈进行单词逆序:输入一个字符串,然后输出原...因为栈的后进先出的特性,所以字母的顺序就颠倒过来了。/** * @Description Reverse 栈单词逆序--栈 * @author whm...
  • 概念很简单,栈 (Stack)是一种后进先出(last in first off,LIFO)的数据结构,而队列(Queue)则是一种先进先出 (fisrt in first out,FIFO)的结构,如下图:     2. 实现   现在来看如何实现以上的两...
  • 栈(先进后

    千次阅读 2017-12-18 21:01:26
    今天刚学栈,就简单说一下自己的理解,首先,栈遵守一个原则,就是先进后出,后进先出。打个比方,就像一个水瓶,要想喝到最底部的水(在不打破瓶子本身的情况下),就必须先将上面的水喝掉,这就可以类似栈的作用...
  • 作者:小傅哥 ... 沉淀、分享、成长,让自己和他人都能有所收获!???? ...对于在校学习期间的计算机、软件...以我的学习经历来说,一个知识点是否能快速接受并学习到,往往是看有没有一个合适的场景和好的例子,来引导读者
  • 文章目录1 栈的概念(后进先出)1.1 顺序栈1.2 链栈2 队列的概念(先进先出)2.1 顺序队列2.2 链式队列 1 栈的概念(后进先出) 栈(stack),也称为堆栈,是运算受限的线性表,也是一种容器,可存入数据元素、访问...
  • 概念很简单,栈 (Stack)是一种后进先出(last in first off,LIFO)的数据结构,而队列(Queue)则是一种先进先出 (fisrt in first out,FIFO)的结构,如下图: 2.  实现 现在来看如何实现以上的两个数据结构...
  • 第七章:深度优先搜索

    千次阅读 2022-02-13 15:46:38
    不撞南墙不回头-深度优先搜索 广度优先搜索BFS是每次将当前状态能够一步拓展出的所有状态,...深度优先搜索(Depth First Search,DFS),简称深搜,其状态“退后一步”的顺序符合“后进先出”的特点,所以采用“..
  • 举个简单的例子,有一个图书馆,如何排放书本才能使书本找起来非常方便,而且有新书本的时候也能快速的放入到准确的位置。解决问题的方法,跟书本(数据)的组织方式有关,以什么样的方式来存储和组织我们的数据才能...
  • 该订单可以是LIFO(后进先出)或FILO(后进先出)。 有很多现实生活中的例子。 链接列表: 链接列表由节点组成,其中每个节点包含一个数据字段和一个指向列表中下一个节点的refernece(link)。
  • 数据结构在生活中的应用 数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同...
  • 原则:后进先出原则 相关名词 进栈(push):压入 出栈(pop):弹出 栈的实现 栈的常见操作 push 压入元素到栈顶 pop 弹出栈顶元素 peek 返回栈顶的元素 isEmpty 判断栈是否为空 size 返回栈的元
  • 栈(后进先出)可以用于字符匹配,数据反转等场景。 队列(先进先出)可以用于任务队列,共享打印机的场景。
  • 准确的讲,栈就是一种可以实现“先进后出(或者叫后进先出)”的存储结构。 学过数据结构的人都知道:栈可以用两种方式来实现,一种方法是用数组实现栈,这种栈成为静态栈;另外一种方法是用链表实现栈,这种栈叫做...
  • 有哪些让程序员受益终生的建议

    万次阅读 多人点赞 2019-10-28 07:11:59
    从业五年多,辗转两个大厂,过书,创过业,从技术小白成长为基层管理,联合几个业内大牛回答下这个问题,希望能帮到大家,记得帮我点赞哦。 敲黑板!!!读了这篇文章,你将知道如何才能进大厂,如何实现财务自由...
  • 栈的数据结点必须是后进先出。 宏观上来说,相比于数组或链表,栈的操作更为受限,但为什么要用到栈呢? 单纯从功能上讲,数组或链表可以替代栈。但问题也随之而来,数组或链表的操作过于灵活,这意味着,它们...
  • ArrayDeque作为堆栈 要在Java中实现LIFO(后进先出)堆栈,建议在Stack类上使用双端队列。该ArrayDeque类比Stack类快。 ArrayDeque 提供了以下可用于实现堆栈的方法。 push() - 在堆栈顶部添加一个元素 peek() - 从...
  • 栈及栈的应用举例

    千次阅读 2020-08-19 15:52:13
    看一个例子,请输入一个表达式 计算式:[7 * 2 * 25+1-5+3-3] 点击计算【如下图】 请问: 计算机底层是如何运算得到结果的? 注意不是简单的把算式列运算,因为我们看这个算式 7 * 2 * 2 - 5, 但是计算机怎么理解...
  • 马云996的言论一,关于奋斗与生活的话题,让平时沉默如金的同学群开始热闹起来。 以刘文为代表的加班派表示,现在大公司都是这样,劳动法确实规定了工作时长,但是公司的默认规定也无法不履行。要么忍、要么...
  • 马云996的言论一,关于奋斗与生活的话题,让平时沉默如金的同学群开始热闹起来。 以刘文为代表的加班派表示,现在大公司都是这样,劳动法确实规定了工作时长,但是公司的默认规定也无法不履行。要么忍、要么...
  • 因为栈仅能在表尾即栈顶对元素进行操作,因此,栈就是先进后出或后进先出的线性表。 重要知识点:出栈顺序计算:当有多个元素时,每个元素都有很多出栈顺序,但总体来看,出栈顺序满足卡特兰数,当然卡特兰数不能仅...
  • 生活,不分专业

    千次阅读 2011-10-09 14:36:09
    我仔细想一想,却觉得当年后进的同学,多半早早学会了学校以外的“生活课”,当生活的大幕一拉开,这些同学便立刻跃上舞台翻腾起来;而那些只学会语文数学英语的同学,一旦这些学习产品停产,变会出现对生活的各种不...
  • 题目 输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。...栈是一种“后进先出”的线性表,我们在线性表的尾部进行添加和删...
  • 1.1-1 给现实生活中需要排序的一个例子或者现实生活中需要计算凸壳的一个例子 答:排序比较多,比如商场产品单价、销量、总价的排序、全校学生的成绩登录系统需要排序,还有一些需要按一定属性排序的情况等。凸壳...
  • 数据结构 -- 栈举例

    2018-11-02 22:44:18
    这种排序原则有时被称为LIFO(Last In First Out),后进先出。它基于在集合内的时间长度做排序。较新的项靠近顶部,较旧的项靠近底部。 栈的底部很重要,因为在栈中靠近底部的项是存储时间最长的。 栈的例子很常见...
  • 栈的应用实例

    千次阅读 2020-07-11 17:13:55
    栈的一大特点是后进先出(last-in first-out),这样可以先判断最右边的左括号。故遍历字符串,将所有左括号压入栈底,当遇到右括号时拿出栈中顶端元素进行判断。若不能匹配则该字符串不满足要求,匹配则推出栈顶元素...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,920
精华内容 768
关键字:

后进先出的生活例子