Queues - Stacks and Queues | Coursera

For EnterprisePara alunos

Navegar
Os melhores cursos
Entrar
Inscreva-se gratuitamente

Queues

Loading...

Algoritmos, Parte I

Universidade de Princeton

4.9 (7,747 classificações) | 730K alunos inscritos

Cadastre-se gratuitamente

This course covers the essential information that every serious programmer needs to know about algorithms and data structures, with emphasis on applications and scientific performance analysis of Java implementations. Part I covers elementary data structures, sorting, and searching algorithms. Part II focuses on graph- and string-processing algorithms. All the features of this course are available for free. It does not offer a certificate upon completion.

Visualizar o programa do curso

Habilidades que você aprenderá

Data Structure, Algorithms, Java Programming

Avaliações

4.9 (7,747 classificações)

5 stars
91.50%
4 stars
7.12%
3 stars
0.78%
2 stars
0.18%
1 star
0.40%

RP

Jun 11, 2017

Incredible learning experience. Every programmer in industry should take this course if only to dispel the idea that with the advent of cloud computing exponential algorithms can still ruin your day!

GG

Nov 01, 2016

Extremely well designed course. The assignments touch all the concepts taught in the class. Lot of concepts get clarified when you try to reach 100% on each assignment. Highly recommend this course.

Na lição

Stacks and Queues

We consider two fundamental data types for storing collections of objects: the stack and the queue. We implement each using either a singly-linked list or a resizing array. We introduce two advanced Java features—generics and iterators—that simplify client code. Finally, we consider various applications of stacks and queues ranging from parsing arithmetic expressions to simulating queueing systems.

Resizing Arrays9:56

Stack and Queue Applications (optional)13:24

Ministrado por

Kevin Wayne
Phillip Y. Goldman '86 Senior Lecturer
Robert Sedgewick
William O. Baker *39 Professor of Computer Science

Experimente o curso Gratuito

Transcrição

Okay, next we'll briefly consider queue implementations using the same basic underlying data structures. So here's the corresponding API for QueueOfStrings. Actually it's the same API as for stacks, just the names are different. Instead of push we have enqueue instead of pop we have dequeue. And the semantics is different, for enqueue we add an item say at the end of the queue, and for dequeue we remove an item from the beginning. It's as if you're waiting in line to buy a ticket. When you're enqueue you go at the end, and when the one that's been in there the longest is the one that comes off. So lets look at how we implement those, first using linked list and then arrays. So now our representation of a queue with a length list, we need to maintain two pointers, references. One, to the first item in the list and the other to the last item in the list. When we insert, we're going to add the item at the end of the list instead of at the beginning. And when we remove, we'll do the same, we'll take it off at the front. So here's the implementation of dequeue. It's identical to the code for pop for a stack. We save away the item, we delete the first node by advancing the reference and then we return the item, so identical. To add a note, or enqueue, add a new note to a linked-list. We want to put it at the end, so that will be the last one returned. So we, to add it at the end, so first thing we need to do is save a link, the last node. We're going to need that because we need to change it's reference from null to point to the new node. Then we'll create a new node for the end of the list. We'll populate its fields and then that old link will change that from null to a pointer to the new node. So again, just a few lines of code, [COUGH] that's basic linked-list processing. Actually years ago when we taught courses in algorithms and data structures, much of the course would be about this kind of pointer manipulation. But nowadays that's restricted to just a few implementations like stack and queue and a few other fundamental data structures. So we don't need so much any more general programs for manipulating linked-lists. We encapsulate them in basic data types like these. All right, so let's go back to our full implementation and this is just taking care of collecting the code from the previous slides. But also taking care of special cases when the queue is empty. To make sure that if the queue is empty after we move an item we gotta set last to null. Make sure that both first and last are always what we want them to be. So those are details that are easy to check. Okay, what about arrays? Well, we won't do the details, but it's not difficult to implement queues with resizing arrays as well. Not difficult, but a definitely tricky programming exercise that people are welcome to try. So we'll maintain two pointers, the first item in the queue and the tail, which is the position for the next item to appear. So for enqueue, you add a new item a tail. And for dequeue you remove an item for a head. And the trick is that once you get past the capacity, you have to reset back to zero. And so that's a little extra code, and then you have to add the resizing capability as well to implement the data structure the same as for stack. And we'll leave that as an exercise.

Explore nosso catálogo

Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.

Os melhores cursos on-line

Como encontrar propósito e sentido na vida
Compreendendo a pesquisa médica
Japonês para iniciantes
Introdução à computação em nuvem
Fundamentos de Mindfulness
Fundamentos de Finanças
Aprendizagem Automática
Aprendizagem automática usando o Sas Viya
A ciência do bem-estar
Rastreamento de Contato com a Covid-19
IA para todos
Mercados Financeiros
Introdução à Psicologia
Introdução à AWS
Marketing internacional
C++
Análise Preditiva e Mineração de Dados
Aprendendo a Aprender da UCSD
Programação para todos da Universidade do Michigan
Linguagem R da JHU
Treinamento de CPI do Google CBRS

Principais programas de cursos integrados on-line

Processamento da Linguagem Natural (PLN)
IA para Medicina
Bom com palavras: escrita e edição
Modelagem de doenças infecciosas
A pronúncia do inglês americano
Automatização de teste de software
Aprendizagem profunda
Python para todosPython para todos
Ciência de Dados
Fundamentos de negóciosFundamentos dos Negócios
Habilidades em Excel para negócios
Ciência de Dados com Python
Finanças para todos
Habilidades de comunicação para engenheiros
Treinamento de vendas
Desenvolvimento e gestão de marca pessoal
Análise de Dados de Negócios da Wharton
Psicologia Positiva da Universidade da Pensilvânia
Aprendizagem Automática da Universidade de Washington
Design Gráfico da CalArts

Certificados on-line

Certificados profissionais
Certificados MasterTrack
Suporte de TI do Google
Ciência de dados da IBM
Engenharia de Dados do Google Cloud
IA aplicada da IBM
Arquitetura do Google Cloud
Analista de Cibersegurança da IBM
Automação da TI do Google com Python
Profissional de Mainframe do IBM z/OS
Gestão aplicada de projetos da UCI
Certificado em Design Instrucional
Certificado em Engenharia e Gerenciamento de Construção
Certificado de Big Data
Certificado de Aprendizagem Automática em Análise de Dados
Certificado em Gestão de Inovação e Empreendedorismo
Certificado de Sustentabilidade e Desenvolvimento
Certificado de Serviço Social
Certificado de IA e Aprendizagem Automática
Certificado de Análise e Visualização de Dados Espaciais

Programa de graduação on-line

Graduações em Ciência da Computação
Graduações em Negócios
Graduações em Saúde Pública
Graduações em Ciência de Dados
Bacharelados
Bacharelado em Ciência da Computação
Mestrado em Engenharia Elétrica
Conclusão de bacharelado
Mestrado em Gestão
Mestrado em Ciência da Computação
Mestrado em Saúde Pública
Mestrado em Contabilidade
Mestrado em Tecnologia da Computação e da Informação
MBA On-line
Mestrado em Ciência de Dados Aplicada
MBA Global
Mestrado em Inovação e Empreendedorismo
Mestrado em Ciência de Dados
Mestrado em Ciência da Computação
Mestrado em saúde pública

Coursera

Sobre
Liderança
Carreiras
Lista de cursos
Certificados
Certificados MasterTrack™
Notas
For Enterprise
Para Governos
For Campus
Combate ao Coronavírus

Comunidade

Aprendizes
Parceiros
Desenvolvedores
Testadores beta
Tradutores
Blog
Tech Blog

Mais

Termos
Privacidade
Ajuda
Acessibilidade
Imprensa
Contato
Diretório
Afiliados

Baixar no Google Play

© 2020 Coursera Inc. Todos os direitos reservados.