DOUG LLOYD: Tudo bem, por isso, este ponto você está provavelmente bastante familiar com matrizes e listas ligadas que é a dois primário estruturas de dados que nós falou sobre por manter conjuntos de dados de tipos de dados semelhantes organizado. Agora nós estamos indo falar sobre um casal de variações em matrizes e listas ligadas. Neste vídeo nós vamos para falar sobre pilhas. Especificamente vamos falar sobre uma estrutura de dados denominada pilha. Lembre-se de discussões prévias sobre ponteiros e memória, que a pilha também o é nomear para um segmento de memória onde estaticamente declarado memória memory-- que você nome, variáveis ​​que você nome, et quadros cetera e função que também existem quadros de pilha de chamadas. Portanto, esta é uma estrutura de dados pilha não um segmento de pilha de memória. ESTÁ BEM. 

Mas o que é uma pilha? Por isso, é praticamente apenas um tipo especial de estrutura que mantém os dados de uma forma organizada. E há dois muito maneiras comuns para implementar pilhas usando duas estruturas de dados que já está familiarizado com, matrizes e listas ligadas. O que faz uma pilha especial é o maneira em que podemos colocar informações na pilha, ea maneira que nós remover a informação a partir da pilha. Em particular com as pilhas a regra é apenas o mais recentemente elemento adicionado pode ser removido. 

Então, pense nisso como se fosse uma pilha. Nós estamos acumulando informações em cima de si, e apenas a coisa no topo da pilha pode ser removida. Não podemos remover a coisa por baixo porque tudo o resto seria colapso e cair. Então, nós realmente estamos construindo uma pilha que então, temos que remover pedaço por pedaço. Devido a isso, geralmente se referem para uma pilha LIFO como uma estrutura, último a entrar, primeiro a sair. LIFO, último a entrar, primeiro a sair. 

Assim, devido a esta restrição como a informação pode ser adicionada aos e removido a partir de uma pilha, não há realmente apenas duas coisas que podemos fazer com uma pilha. Podemos empurrar, que é a termo que usamos para adicionar um novo elemento ao topo do pilha, a pilha ou se não existir e estamos a criar a partir do zero, criar a pilha em primeiro lugar seria empurrar. E em seguida, pop, que é o tipo de CS termo que usamos para remover o mais recentemente elemento adicionado a partir do topo da pilha. 

Então, vamos olhar para os dois implementações, com base tanto matriz e lista ligada baseado. E nós estamos indo para começar com matriz baseada. Então aqui está a idéia básica do que a estrutura de dados pilha matriz baseada seria semelhante. Nós temos uma definição digitado aqui. Dentro de que temos dois membros ou campos da estrutura. Nós temos uma matriz. E mais uma vez eu estou usando o valor tipo de dados arbitrário. 

Portanto, este pode ser qualquer tipo de dados, int char ou alguns outros dados o tipo que você criou anteriormente. Portanto, temos um conjunto de capacidade tamanho. Capacidade sendo uma libra constante definida, talvez em outro lugar em nosso arquivo. Então, observe já com este particular implementação estamos delimitadora nos como era tipicamente o caso com matrizes, que não pode redimensionar dinamicamente, onde há um certo número de elementos que máximo podemos colocar em nossa pilha. Neste caso, é elementos de capacidade. 

Nós também manter o controle de o topo da pilha. O elemento é o mais recentemente adicionado à pilha? E, assim, manter o controle de que em uma variável chamada superior. E tudo isso fica embrulhado em conjunto para um novo tipo de dados chamado uma pilha. E uma vez que são criados este novo tipo de dados podemos tratá-la como qualquer outro tipo de dados. Podemos declarar pilha s, assim como nós poderíamos fazer int x, y ou carvão. E quando dizemos empilhar s, bem o que acontece é que obter um conjunto de memória reservada para nós. 

Neste caso capacidade Eu aparentemente decidiu 10 é porque eu tenho um única variável do tipo de pilha que contém dois campos recordar. Uma matriz, neste caso vai para ser uma matriz de números inteiros como é o caso na maioria das minhas exemplos. E outra variável inteira capaz de armazenar o topo, o adicionado mais recentemente para o elemento de pilha. Assim, uma única pilha do que nós só olha como esta definido. É uma caixa contendo uma matriz de 10 o que serão inteiros, neste caso, e outra variável inteira lá em verde para indicar a parte superior da pilha. 

Para definir a parte superior da pilha nós apenas dizer s.top. Isso é como nós acessar um campo de um recall estrutura. s.top é igual a 0 efectivamente faz isso para a pilha. Então, novamente, temos duas operações que pode realizar-se agora. Nós podemos empurrar e podemos pop. Vamos começar com empurrão. Mais uma vez, empurrando é a adição de um novo elemento para o topo da pilha. 

Então, o que precisamos fazer em essa matriz implementação baseada? Bem, em geral, a função push vai a necessidade de aceitar um ponteiro para a pilha. Agora pegue um segundo e pensar sobre isso. Por que iríamos querer a aceitar um ponteiro para a pilha? Lembre-se de vídeos anteriores sobre escopo de variáveis ​​e ponteiros, o que aconteceria se nós apenas enviado pilha, s, em vez de como um parâmetro? O que seria realmente passou lá dentro? Lembre-se que estamos criando uma cópia quando passá-lo para uma função a não ser que usar ponteiros. E assim esta função empurrar necessidades para aceitar um ponteiro para a pilha de modo que nós estamos realmente mudando a pilha pretendemos mudar. 

A outra coisa impulso provavelmente quer aceitar é um elemento de dados de valor tipo. Neste caso, de novo, um número inteiro que nós estamos indo para adicionar ao topo da pilha. Então, nós temos nossos dois parâmetros. O que é que vamos agora fazer dentro de impulso? Bem, simplesmente, nós apenas estamos indo para adicionar que o elemento de topo da pilha e, em seguida, alterar o local onde o topo a pilha é, isso é ponto alto valor. Então é isso que uma função declaração para push pode parecer em um baseada em array implementação. 

Novamente, isto não é uma regra dura e rápida que você pode mudar isso e ter que variam de formas diferentes. Talvez s é declarado globalmente. E para que você não precisa mesmo para passá-lo é como um parâmetro. Esta é apenas uma outra vez caso geral para push. E há diferentes maneiras de implementá-lo. Mas, neste caso, o nosso empurrão vai levar dois argumentos, um ponteiro para uma pilha e um elemento de dados de valor tipo, número inteiro nesse caso. 

Por isso, declarou s, nós disse s.top é igual a 0. Agora vamos empurrar o número 28 na pilha. Bem, o que isso significa? Bem atualmente o parte superior da pilha é 0. E então o que é basicamente vai acontecer é nós estamos indo para furar o número 28 em array local 0. Bastante simples, certo, que foi a top e agora nós somos bons de ir. E então temos de mudar o que o topo da pilha será. De modo que a próxima vez que empurra um elemento, nós estamos indo para armazená-lo em localização matriz, provavelmente não 0. Nós não queremos substituir o que acabamos de colocar lá. E por isso vamos mover a parte superior para 1. Isso provavelmente faz sentido. 

Agora, se queremos colocar outro elemento na pilha, dizer que nós queremos empurrar 33, bem, agora nós estamos apenas vai levar 33 e colocá-lo em número de localização matriz 1, e, em seguida, alterar o topo da nossa empilhar para ser matriz número local dois. Então, se a próxima vez que quiser empurrar um elemento na pilha, ele vai ser colocado no local da matriz 2. E vamos fazer isso mais uma vez. Vamos empurrar 19 fora das pilhas. Nós vamos colocar 19 em localização matriz 2 e altere o topo da nossa pilha para ser localização matriz 3 por isso, se a próxima vez nós precisa fazer um esforço que está pronto para ir. 

OK, de modo que levando em poucas palavras. O que sobre o estalo? Então popping é o tipo de contrapartida para empurrar. É assim que remover os dados da pilha. E em necessidades pop gerais para fazer o seguinte. É necessário aceitar um ponteiro para o Pilha, de novo, no caso geral. Em algum outro caso, você pode ter declarado a pilha globalmente, caso em que você não precisa passá-lo no sistema porque ele já tem acesso a ele como uma variável global. Mas então o que mais fazer o que precisamos fazer? Bem, fomos incrementando o topo da pilha no impulso, assim que nós estamos provavelmente vai querer para diminuir o topo da pilha no pop, certo? E depois, claro nós estamos também vai querer para retornar o valor que nós remover. Se estamos adicionando elementos, queremos para obter elementos para fora mais tarde, nós provavelmente verdade deseja armazená-los por isso, não apenas excluí-los do empilhar e depois não fazer nada com eles. Geralmente, se nós somos empurrando e estalando aqui queremos armazenar este informações de uma forma significativa e por isso não faz sentido apenas descartá-lo. Assim, esta função deve provavelmente retornar um valor para nós. 

Então é isso que uma declaração de pop pode parecer que há na parte superior esquerda. Esta função retorna dados de valor tipo. Mais uma vez nós estivemos usando inteiros todo. E aceita um ponteiro para uma pilha como seu único argumento ou parâmetro único. Então, o que é pop vai fazer? Vamos dizer que nós queremos agora pop um elemento fora de s. Então lembre-se, eu disse que pilhas são passado in, first out, estruturas de dados LIFO. Qual elemento está indo ser removido da pilha? Será que você adivinha 19? Porque você estaria certo. 19 foi o último elemento que adicionado ao empilhar quando estávamos empurrando elementos em, e por isso vai para o primeiro elemento que é removido. É como se disséssemos 28, e então vamos colocar 33 em cima dela, e nós colocamos 19 em cima disso. O único elemento que podemos tirar é de 19. 

Agora no diagrama aqui o que eu fiz é uma espécie de deletada 19 a partir da matriz. Isso não é verdade, o que vamos fazer. Nós apenas estamos indo para tipo de fingir que não está lá. Ele ainda está lá em que a localização de memória, mas nós apenas estamos indo para ignorá-lo alterando o topo da pilha nosso sendo de 3 para 2. Então, se nós estávamos a empurrar agora outro elemento na pilha, que iria sobre escrever 19. 

Mas não vamos passar pela dificuldade exclusão de 19 a partir da pilha. Nós podemos apenas fingir que não está lá. Para fins da pilha é ido se mudarmos a top para ser 2 em vez de 3. Tudo bem, então isso foi muito bonito isso. Isso é tudo o que precisamos fazer a pop um elemento fora. Vamos fazer de novo. Então, eu tenho realçado em vermelho aqui para indicam que estamos a fazer outra chamada. Nós vamos fazer a mesma coisa. 

Então, o que vai acontecer? Bem, nós estamos indo para armazenar 33 em x e vamos para alterar o topo da pilha para 1. Assim que, se fôssemos agora a empurrar um elemento na pilha que nós somos vai fazer agora, o que vai acontecer é que vamos sobrescrever matriz número de localização 1. Assim que 33 que era uma espécie de esquerda atrás de que nós apenas fingiu não está mais lá, nós apenas estamos indo a espancar-lo e colocar lá em vez de 40. E depois, claro, desde que fizemos um empurrão, vamos incrementar o topo da pilha a partir de 1 para 2 de modo que se acrescentam-se agora outro elemento que vai entrar em matriz número local dois. 

Agora listas ligadas são outro forma de implementar pilhas. E, se esta definição no tela aqui parece familiar para você, é porque parece quase exactamente a mesma, na verdade, ele praticamente é exatamente o mesmo como uma lista vinculada isoladamente, se você se lembra de nossa discussão sobre listas individualmente ligados no outro vídeo. A única restrição aqui é para nós como programadores, nós não estamos autorizados a inserir ou excluir aleatoriamente da lista vinculada isoladamente que anteriormente podiam fazer. Nós agora só pode inserir e excluir da da frente ou a parte superior do ligada Lista. Isso é realmente a única diferença embora. Esta é outra forma de uma lista vinculada isoladamente. É só a restrição substituindo em nós mesmos como programadores que muda-lo em uma pilha. 

A regra aqui é manter sempre uma Ponteiro para a cabeça de uma lista ligada. Este é, naturalmente, um geral regra importante em primeiro lugar. Para isoladamente lista ligada de qualquer maneira só precisa de um ponteiro para a cabeça de modo a que têm cadeia de ser capaz de encaminhá para todos os outros elementos na lista vinculada. Mas é particularmente importante com uma pilha. E de modo geral, você é vai realmente querem este ponteiro para ser uma variável global. Ele provavelmente vai ser ainda mais fácil dessa maneira. Então, quais são os análogos de push e pop? Certo. Então, empurrando de novo é a adição de um elemento novo para a pilha. Em uma lista vinculada que significa que nós vamos ter para criar um novo nó que nós somos vai adicionar na lista ligada, e, em seguida, siga os passos cuidadosos que temos delineado anteriormente em listas individualmente ligados ao adicioná-lo à a cadeia sem quebrar a cadeia e perder ou orfandade qualquer elementos da lista ligada. E isso é basicamente o que isso pouco blob de texto lá resume. E vamos dar uma olhada para ele como um diagrama. 

Então aqui está a nossa lista ligada. Ele contém quatro elementos simultaneamente. E mais perfeitamente aqui está a nossa empilhar contendo quatro elementos. E digamos que queremos agora empurrar um novo item para esta pilha. E eu quero empurrar um novo item cujo valor de dados é de 12. Bem, o que vamos fazer? Bem, primeiro vamos espaço malloc, dinamicamente alocar espaço para um novo nó. E, claro, imediatamente após fazemos uma chamada para malloc sempre certifique-se de verificar para null, porque se nós ficássemos nula de volta houve algum tipo de problema. Nós não queremos excluir a referência que nulo ponteiro ou você vai sofrer uma falha seg. Isso não é bom. Então, nós temos malloced do nó. Vamos assumir que tivemos sucesso aqui. Nós vamos colocar 12 em o campo de dados desse nó. Agora você se lembra qual dos nossos ponteiros move seguinte portanto, não quebrar a cadeia? Nós temos um par de opções aqui, mas o único que vai ser seguro é definir notícia próximo ponteiro para aponte para o antigo chefe da lista ou o que em breve será o antigo cabeça da lista. E agora que todo o nosso elementos são encadeados, podemos lista apenas mover para apontar para o mesmo lugar que faz novo. E nós temos agora efetivamente empurrou um novo elemento para a frente da pilha. 

Para pop nós só queremos excluir esse primeiro elemento. E assim, basicamente o que nós temos que fazer aqui, bem temos de encontrar o segundo elemento. Eventualmente, que se tornará o novo cabeça depois de excluir o primeiro. Então, só precisamos começar a partir de o início, mova um para a frente. Uma vez que temos um porão em um para a frente de onde estamos atualmente somos nós pode excluir a primeira com segurança e então podemos simplesmente mover a cabeça para apontar para o que era o segundo mandato e, em seguida, agora é a primeira que depois nó foi excluído. 

Então, novamente, dando uma olhada para ele como um diagrama de nós quer agora um pop elemento fora desta pilha. Então, o que fazemos? Bem, vamos primeiro a criar um novo ponteiro que está acontecendo para apontar para o mesmo local como a cabeça. Nós estamos indo para movê-lo uma posição para a frente dizendo iguais trav trav próxima, por exemplo, que avançaria a um ponteiro trav posição para a frente. Agora que temos um segurar o primeiro elemento através da lista ponteiro chamado, ea segundo elemento por meio de um chamado ponteiro trav, podemos excluir com segurança que primeiro elemento a partir da pilha sem perder o resto da cadeia porque tem uma maneira de se referir para o segundo elemento transmitir através do ponteiro chamado trav. 

Então agora podemos liberar esse nó. Podemos libertar lista. E então tudo o que precisamos fazer agora é lista mover para apontar para o mesmo lugar trav que faz, e nós somos tipo de volta onde começamos antes que empurrou 12 sobre, em primeiro lugar, à direita. Este é exatamente onde estávamos. Nós tivemos essa pilha de quatro elementos. Nós adicionamos um quinto. Nós empurramos um quinto elemento, e então nós estalou que, mais recentemente, elemento adicionado de volta ao largo. 

Isso é realmente muito bonito tudo o que há para pilhas. Você pode implementá-las como matrizes. Você pode implementá-las como listas ligadas. Existem, naturalmente, outros maneiras de implementá-las também. Basicamente, a razão nós usaríamos pilhas é manter os dados, de tal maneira o que mais recentemente acrescentado elemento é a primeira coisa que nós somos vai querer voltar. Eu sou Doug Lloyd, este é CS50.