Doug LLOYD: Todo ben, por iso, este punto está probablemente bastante familiar con matrices e listas ligadas que é a dous primario estruturas de datos que nós falou por manter conxuntos de datos de tipos de datos similares organizado. Agora imos falar sobre unha parella de variacións en matrices e listas ligadas. Neste vídeo imos para falar pilas. Especificamente imos falar sobre unha estrutura de datos denominada pila. Teña en conta que de discusións previas sobre punteiros e memoria, que a pila tamén o é nomear a un segmento de memoria onde estaticamente declarado memoria memory-- que nome, variables que nome, et cadros cetera e función que tamén hai cadros de pila de chamadas. Polo tanto, esta é unha estrutura de datos pila non un segmento de pila de memoria. Aceptar. 

Pero o que é unha pila? Por iso, é practicamente só un tipo especial de estrutura que mantén os datos de forma organizada. E hai dous moi formas comúns para poñer en práctica pilas usando dúas estruturas de datos que xa está familiarizado con, matrices e listas ligadas. O que fai unha pila especial é o xeito en que podemos poñer información na pila, eo xeito que eliminar a información a partir do conxunto. En particular coas pilas a regra é só o máis recentemente elemento engadido pode ser eliminado. 

Entón, pense nisto como se fose unha pila. Estamos acumulando información enriba de si, e só a cousa na parte superior do conxunto pode ser borrada. Non podemos eliminar a cousa por baixo porque todo o demais sería colapso e caer. Entón, nós realmente estamos a construír unha pila que entón, temos que eliminar peza por peza. Debido a iso, xeralmente se refiren para unha pila LIFO como unha estrutura, último a entrar, primeiro en saír. LIFO, último a entrar, primeiro en saír. 

Así, debido a esta restrición como a información pode ser engadida aos e eliminar a partir dunha pila, non hai realmente só dúas cousas que podemos facer cunha pila. Podemos empurrar, que é a termo que usan para engadir un novo elemento ao cume do pila, a pila ou se non existe e estamos a crear a partir de cero, crear a pila primeiro sería empurrar. E logo, pop, que é o tipo de CS termo que usan para eliminar o máis recentemente elemento engadido dende o principio da pila. 

Entón, imos ollar para os dous implementacións, en base tanto matriz e lista ligada baseado. E nós estamos indo a comezar matriz baseada. Entón aquí está a idea básica que a estrutura de datos pila matriz baseada sería semellante. Temos unha definición ingresaran aquí. Dentro de que temos dous membros ou campos da estrutura. Temos unha matriz. E unha vez máis está a usar o valor tipo de datos arbitrario. 

Polo tanto, este pode ser calquera tipo de datos, int char ou algúns outros datos o tipo que creou anteriormente. Polo tanto, temos un conxunto de capacidade tamaño. Capacidade sendo unha libra constante definida, quizais noutro lugar na nosa arquivo. Entón, observe xa con este particular implantación estamos delimitador nos como era tipicamente o caso matrices, que non pode cambiar o tamaño dinamicamente, onde hai un número de elementos que máximo podemos poñer na nosa pila. Neste caso, é elementos de capacidade. 

Tamén manter o control de o principio da pila. O elemento é o máis recentemente engadido á pila? E, así, manter o control de que nunha variable chamada superior. E todo iso queda envolto en conxunto para un novo tipo de datos chamado unha pila. E xa que son creados este novo tipo de datos podemos tratala como calquera outro tipo de datos. Podemos declarar pila s, así como poderíamos facer int x, y ou carbón. E cando dicimos apilar s, así que pasa é que obter un conxunto de memoria reservada para nós. 

Neste caso capacidade Eu parecer decidiu 10 é porque eu teño un única variable do tipo de pila que contén dous campos recordar. Unha matriz, neste caso vai para ser unha matriz de números enteiros como é o caso na maioría das miñas exemplos. E outra variable enteira capaz de almacenar o cumio, o engadido máis recentemente para o elemento de pila. Así, unha única pila que nós só mira como esta definido. É unha caixa que contén unha matriz de 10 que serán enteiros, neste caso, e outra variable enteira alí en verde para indicar a parte superior do conxunto. 

Para axustar a parte superior da pila nós só dicir s.top. Isto é como nós acceder a un campo dun recall estrutura. s.top é igual a 0 efectivamente fai isto para a pila. Entón, de novo, temos dúas operacións que pode realizar-se agora. Podemos empurrar e podemos pop. Imos comezar con pulo. Unha vez máis, empurrando é a adición dun novo elemento para arriba da pila. 

Entón, o que necesitamos facer en esa matriz implementación baseada? Ben, en xeral, a función push vai a necesidade de aceptar un punteiro para a pila. Agora tome un segundo e pensar sobre iso. Por que iríamos querer aceptar un punteiro para a pila? Teña en conta que de vídeos anteriores sobre ámbito de variables e punteiros, o que acontecería se nós só enviado pila, s, no canto de como un parámetro? O que sería realmente pasou alí dentro? Lembre que estamos creando unha copia cando pasalo a unha función a menos que usar punteiros. E así esta función empurrar necesidades para aceptar un punteiro para a pila de xeito que estamos realmente cambiando a pila pretendemos cambiar. 

A outra cousa impulso probablemente quere aceptar é un elemento de datos do valor tipo. Neste caso, de novo, un número enteiro que nós estamos indo a engadir ao principio da pila. Entón, nós temos os nosos dous parámetros. Que imos agora facer dentro impulso? Ben, simplemente, nós só estamos indo para engadir que o elemento de parte superior do conxunto e, a continuación, cambiar o lugar onde a parte superior a pila é, iso é punto alto valor. Entón é iso que unha función declaración para push pode parecer nun baseada en array implementación. 

De novo, isto non é unha regra dura e rápida que pode cambiar iso e ter que varían de formas diferentes. Quizais s é declarado globalmente. E para que non precisa aínda para pasalo é como un parámetro. Esta é só unha outra vez caso xeral para push. E hai diferentes formas de implementar lo. Pero, neste caso, o noso pulo levará dous argumentos, un punteiro para unha pila e un elemento de datos do valor tipo, número enteiro neste caso. 

Por iso, declarou s, nós dixo s.top é igual a 0. Agora imos empurrar o número 28 na pila. Ben, o que significa isto? Ben actualmente o parte superior da pila é 0. E entón o que é basicamente ocorrerá é nós estamos indo a furar o número 28 en array local 0. Moi sinxelo, non, que foi a top e agora somos bos de ir. E entón temos que cambiar o que o principio da pila será. De xeito que a próxima vez que empurra un elemento, nós estamos indo a almacena-lo localización matriz, probablemente non 0. Non queremos substituír o que acabamos de poñer alí. E por iso imos mover a parte superior a 1. Isto probablemente ten sentido. 

Agora, se queremos poñer outro elemento na pila, dicir que queremos empurrar 33, ben, agora estamos só vai levar 33 e poñelas en número de localización matriz 1, e, a continuación, cambiar o cume da nosa apilar para ser matriz número local dous. Entón, se a próxima vez que quere empurrar un elemento na pila, vai ser colocadas no lugar da matriz 2. E imos facelo unha vez máis. Imos empurrar 19 fóra das pilas. Nós imos poñer 19 en situación matriz 2 e cambie o principio da nosa pila para ser localización matriz 3 por iso, a próxima vez nós cómpre facer un esforzo que está preparado para ir. 

OK, así que tendo en poucas palabras. O que sobre o estalo? Entón popping é o tipo de contrapartida para empurrar. É así que eliminar os datos do conxunto. E en necesidades pop xerais para facer o seguinte. Debes aceptar un punteiro para o Pila, de novo, no caso xeral. Nalgún outro caso, pode declarar a pila globalmente, caso en que non precisa pasalo no sistema porque xa ten acceso a el como unha variable global. Pero entón o que máis facer o que necesitamos facer? Ben, fomos incrementando o principio da pila no impulso, así que estamos probablemente vai querer para diminuír o principio da pila no pop, non? E despois, claro estamos tamén vai querer para voltar o valor que eliminar. Se estamos engadindo elementos, queremos para obter elementos para fóra máis tarde, nós probablemente verdade quere almacena-los polo que non só borralos do apilar e despois non facer nada con eles. Xeralmente, se somos empurrando e estalado aquí queremos almacenar este información de forma significativa e por iso non fai sentido só descartalo lo. Así, esta función debe probablemente voltar un valor para nós. 

Entón é iso que unha declaración de pop pode parecer que hai na parte superior esquerda. Esta función devolve datos de valor tipo. Unha vez máis nós estivemos usando enteiros todo. E acepta un punteiro para unha pila como o seu único argumento ou parámetro único. Entón, o que é pop vai facer? Digamos que queremos agora pop un elemento fóra de s. Entón lembre, eu dixen que pilas son pasado in, first out, estruturas de datos LIFO. Cal elemento vai ser eliminado da pila? Será que adiviña 19? Porque estaría ben. 19 foi o último elemento que engade ao apilar cando estabamos empurrando elementos, e por iso vai para o primeiro elemento que é eliminado. É coma se dixésemos 28, e entón imos poñer 33 enriba dela, e poñemos 19 enriba diso. O único elemento que podemos sacar é de 19. 

Agora no diagrama aquí o que eu fixen é unha especie de borrada 19 desde a matriz. Iso non é certo, o que imos facer. Nós só estamos indo a tipo de finxir que non está alí. El aínda está alí en que a localización de memoria, pero nós só estamos indo a ignore-lo cambiando o principio da pila noso sendo de 3 a 2. Entón, se nós estabamos a empurrar agora outro elemento na pila, que ía sobre escribir 19. 

Pero non imos pasar pola dificultade exclusión de 19 desde a pila. Podemos só finxir que non está alí. Para fins da pila é ir se mudarmos a top para ser 2 en vez de 3. Todo ben, entón iso foi moi bonito iso. Isto é todo o que necesitamos facer a pop un elemento fóra. Imos facelo de novo. Entón, eu teño resaltado en vermello aquí para indican que estamos a facer outra chamada. Nós imos facer o mesmo. 

Entón, o que vai pasar? Ben, nós estamos indo a almacenar 33 en x e imos para cambiar o cume da pila para 1. Así que, se fósemos agora a empurrar un elemento na pila que somos vai facer agora, o que vai pasar é que imos eliminar matriz número de localización 1. Así que 33 que era unha especie de esquerda detrás de que só finxiu non está alí, nós só estamos indo a espancar-lo e poñer alí en vez de 40. E despois, claro, sempre que fixemos un empurrón, imos incrementar o parte superior do conxunto a partir do 1 de 2 de xeito que se engaden-se agora outro elemento que vai entrar matriz número local dous. 

Agora listas ligadas son outro forma de aplicar pilas. E, se esta definición no pantalla aquí parece familiar para ti, é porque parece case exactamente o mesmo, de feito, el practicamente é o mesmo como unha lista vinculada illadamente, se se lembra da nosa discusión sobre listas individualmente ligados no outro vídeo. A única limitación aquí é para nós como programadores, non estamos autorizados a inserir ou eliminar azar da lista vinculada illadamente que anteriormente podían facer. Agora só pode inserir e eliminar da dianteira ou a parte superior do ligada lista. Isto é realmente o único diferenza aínda. Esta é outra forma de lista vinculada illadamente. É só a restrición substituíndo en nós mesmos como programadores que cambia-lo nunha pila. 

A regra aquí é manter sempre unha Punteiro para a cabeza dunha lista ligada. Este é, naturalmente, un xeral regra importante en primeiro lugar. Para illadamente lista ligada de forma só precisa dun punteiro para a cabeza de xeito que teñen cadea de poder encamiñar para todos os outros elementos na lista vinculada. Pero é especialmente importante cunha pila. E de modo xeral, é vai realmente queren este punteiro para ser unha variable global. El probablemente vai ser aínda máis fácil desa maneira. Entón, cales son os análogos de push e pop? Dereita. Entón, empurrando de novo é a suma de un elemento novo para a pila. Nunha lista vinculada que significa que nós imos ter para crear un novo nodo que somos vai engadir na lista ligada, e, a continuación, siga os pasos coidadosos que temos delineado anteriormente en listas individualmente ligados ao engadir lo á a cadea sen romper a cadea e perder ou orfandade calquera elementos da lista ligada. E iso é basicamente o que iso pouco blob de texto alí resume. E imos dar un ollo para el como un diagrama. 

Entón aquí está a nosa lista ligada. Contén catro elementos simultaneamente. E máis perfectamente aquí está a nosa apilar contén catro elementos. E digamos que queremos agora empurrar un novo elemento para esta pila. E quero empurrar un novo elemento cuxo valor de datos é de 12. Ben, o que imos facer? Ben, primeiro imos espazo malloc, dinamicamente reservar espazo para un novo nodo. E, por suposto, inmediatamente despois facemos unha chamada a malloc sempre asegúrese de comprobar a null, porque se nós ficássemos nula de volta houbo algún tipo de problema. Non queremos eliminar a referencia que nulo punteiro ou vai sufrir un fallo seg. Iso non é bo. Entón, nós temos malloced do nó. Imos asumir que tivemos éxito aquí. Nós imos poñer 12 en O campo de datos dese nodo. Agora se lembra cal dos nosos punteiros move seguinte polo tanto, non romper a cadea? Temos un par de opcións aquí, pero o único que vai ser seguro é definir noticia próximo punteiro para apunte ao antigo xefe da lista ou o que en breve será o antigo cabeza da lista. E agora que todo o noso elementos son encadeados, podemos lista só mover apuntar para o mesmo lugar que fai novo. E nós temos agora efectivamente empurrou un novo elemento para a fronte da pila. 

Para pop nós só queremos eliminar ese primeiro elemento. E así, basicamente o que temos que facer aquí, ben temos que atopar o segundo elemento. Finalmente, que se converteu no novo cabeza despois de eliminar a primeira. Entón, só necesitamos comezar a partir de o inicio, move un para adiante. Unha vez que temos un soto nun á fronte de onde estamos actualmente somos nós pode eliminar a primeira con seguridade e entón podemos simplemente mover a cabeza para apuntar para o que era o segundo mandato e, a continuación, agora é a primeira que despois nó foi eliminado. 

Entón, de novo, dando un ollo para el como un diagrama de nós quere agora un pop elemento fora da pila. Entón, o que facemos? Ben, imos primeiro en crear un novo punteiro que está pasando para apuntar para o mesmo lugar como a cabeza. Estamos indo para movelo unha posición para adiante dicindo iguais trav trav próxima, por exemplo, que avanzaría a un punteiro trav posición para adiante. Agora que temos un soster o primeiro elemento a través da lista punteiro chamado, ea segundo elemento a través dun chamado punteiro trav podemos eliminar con seguridade que primeiro elemento a partir do conxunto sen perder o resto da cadea porque ten un xeito de referirse para o segundo elemento transmitir a través do punteiro chamado trav. 

Entón agora podemos liberar ese nó. Podemos liberar lista. E entón todo o que necesitamos facer agora é lista mover apuntar ao mesmo lugar trav que fai, e nós somos tipo de volta onde comezamos antes que empuxou 12 sobre, en primeiro lugar, á dereita. Este é onde estabamos. Tivemos esa pila de catro elementos. Nós engadimos un quinto. Nós empurramos unha quinta elemento, e entón nós estalou que, máis recentemente, elemento engadido de volta ao ancho. 

Isto é realmente moi bonito todo o que hai para pilas. Pode implementar las como matrices. Pode implementar las como listas ligadas. Existen, por suposto, outros formas de implementar las tamén. Basicamente, a razón nós usariamos pilas é manter os datos, de tal xeito o que máis recentemente engadido elemento é o primeiro que somos Vai querer volver. Eu son Doug Lloyd, este é CS50.