Pilhas_Adiministracao e Estrutura de Dados

8/6/2019 Pilhas_Adiministracao e Estrutura de Dados

1/9

INSTITUTO MDIO POLITCNICO DE

COMPUTAO E GESTO

Disciplina de AED

Tema: Pilhas

Implementao de uma Stack

Interface

Discente:

Norberto Gatsi

15 de Maro de 2010


2/9

Disciplina de AED: Pilhas, Implementao de uma Stack, Interface.Realiza por Norberto Gatsi. Maro de 2010. 3 Trimestre

2

Introduo

Em Cincia da computao, uma estrutura de dados um modo

particular de armazenamento e organizao de dados em um

computador de modo que possam ser usados de modo eficiente.[1][2]

Estruturas de dados e algoritmos so temas fundamentais da

cincia da computao, sendo utilizados nas mais diversas reas do

conhecimento e com os mais diferentes propsitos de aplicao.

Sabe-se que algoritmos manipulam dados. Quando estes dados

esto organizados (dispostos) de forma coerente, caracterizam umaforma, uma estrutura de dados. A organizao e os mtodos para

manipular essa estrutura que lhe conferem singularidade.

O estudo das estruturas de dados est em constante

desenvolvimento (assim como o de algoritmos), mas, apesar disso,

existem certas estruturas clssicas que se comportam como

padres.


3/9


3

Desenvolvimento

Pilhas

As pilhas so estruturas baseadas no princpio LIFO (last in, first

out), na qual os dados que foram inseridos por ltimo na pilha sero

os primeiros a serem removidos. Existem duas funes que se

aplicam a todas as pilhas: PUSH, que insere um dado no topo da

pilha, e POP, que remove o item no topo da pilha.

Em cincia da computao, LIFO (acrnimo para a expressoinglesa Last In, First Out que, em portugus significa ltimo a

entrar, primeiro a sair) refere-se a estruturas de dados do tipo pilha.

equivalente a FILO, que significa First In, Last Out .

O conceito de pilha amplamente utilizado na informtica, como, por

exemplo, durante a execuo de um programa, para o

armazenamento de valores de varivel local a um bloco e tambmpara conter o endereo de retorno do trecho de programa que

chamou a funo ou procedimento actualmente em execuo.

Usa-se os termos push e pop para denominar a insero e remoo

de elementos da pilha, respectivamente. Usa-se o termo top para

consultar o elemento do topo da pilha, sem o remover.

Uma pilha uma lista linear na qual o primeiro elemento a entrar o

ltimo elemento a sair. Ela possui apenas uma entrada, chamada de

topo, a partir da qual os dados entram e saem dela.


4/9


4

Representao dinmica:typeTipoValor = . . . ;Pilha = Elemento;Elemento = recordvalor : TipoValor;ant : Pilha;

end;

Insero, remoo e consulta do elemento de topo

A insero (PUSH) o mtodo que insere um elemento no topo de

uma Pilha. J a remoo (POP) o mtodo que remove umelemento do topo de uma Pilha.

Em programao estruturada temos:

/** Prottipo Na Linguagem C

* Para uma PILHA de elementos inteiros

*/void PUSH(int * Pilha, int elemento);

int POP(int * Pilha);

int TOP(int * Pilha);


5/9


5

Implementao de uma Stack

Stack (Pilha)Esta estrutura um tipo especial de lista com acesso restrito aos

seus elementos. Na pilha os elementos so colocados e retirados por

um nico lado da lista, referenciado por topo. As operaes de inserir

e remover elementos da pilha so designadas por "push" e "pop"

respectivamente.

Este tipo de estrutura tem uma ordenao "LIFO- last in first out".Sempre que um elemento adicionado ou retirado da pilha o topo

alterado.

A Estrutura Stack (esttica)

Trata-se de uma estrutura que permite

guardar um conjunto de elementos domesmo tipo, encontrando-se estes

organizados pela ordem inversa da

qual foram inseridos na stack, (ou

seja, o primeiro elemento a ser

removido o ltimo elemento a ter sido inserido na stack).

Uma stack (esttica) pode ser implementada utilizando um array ou

vector, de tamanho suficientemente grande para conter todos os

elementos que seja necessrio armazenar e um apontador ou ndice

(Topo) que marca a localizao do elemento que est no topo da

stack. Caso a stack se encontre vazia, Topo tem o valor 0 (zero).

PUSH

POP


6/9


6

Para inicializar a stack, necessrio inicializar o apontador Topo

com o valor 0 (zero).

A insero (Push) de um novo elemento obriga a incrementar Topo

em 1 e s depois colocar o valor na stack, no entanto necessrioverificar se a stack est ou no cheia. A remoo remove o elemento

apontado por Topo, sendo necessrio verificar se a stack est ou

no vazia antes de tentar remover o elemento.

Os algoritmos correspondentes a estas operaes encontram-se nos

slides 4 e 5.

Outra forma de implementar stacks consiste em utilizar estruturas

dinmicas, como veremos adiante, no captulo das listas ligadas.

Interface

O termo interface uma referncia caracterstica que permite aconstruo de interfaces que isolam do mundo exterior os detalhes

de implementao de um componente de software.

Utilizao

Um exemplo clssico de utilizao de interfaces o sistema

operacional que, atravs de uma interface de programao deaplicativos, permite que os programas utilizem os recursos do

sistema (memria, cpu, ect) sem que os seus detalhes de

implementao sejam conhecidos do programador. Este esquema


7/9


7

isola e protege o sistema operacional de eventuais erros cometidos

pela aplicao.

Uma interface disponibiliza tipos variados de acesso entre

componentes, como por exemplo: constantes, tipos de dado,

procedimentos, especificao de excepes e assinaturas de

mtodos. Em alguns casos mais apropriado definir as variveis

como parte das interfaces. As interfaces tambm especificam a

funcionalidade disponibilizada atravs de comentrios ou atravs de

declaraes lgicas formais.

Linguagens

O princpio da interface um alicerce da programao modular que,

por sua vez, precursora e parte da programao orientada a

objecto. Na programao orientada a objecto, a interface de um

objecto consiste de um conjunto de mtodos que um objecto deve

suportar. importante notar que as variveis de instncia no fazemparte da interface de um objecto pois devem ser acessada somente

pelos "mtodos de acesso". Historicamente, as interfaces so

derivadas dos arquivos de cabealho da Linguagem C (normalmente

arquivos com extenso "h") que separam o contexto sintctico de um

mdulo (ou prottipos de funes) da sua implementao.

A linguagem de programao Java, que recebeu influncia da

Objective-C, utiliza outra abordagem para o conceito de interface,

assim como outras linguagens orientadas a objecto, onde a interface


8/9


8

especifica um conjunto de mtodos ou funcionalidades comuns a um

conjunto de classes.Ver interface na linguagem Java.

Algumas linguagens de programao como D, Java e Logtalk, por

exemplo, permitem a definio de "hierarquias de interfaces". A

linguagem Logtalk tambm suporta a implementao "privada" e

"protegida" dos mtodos de uma interface.

Suporte h interfaces

Em geral toda linguagem permite a implementao de interfaces.

Mas algumas linguagens possuem "construes" especficas para

esse fim. Por exemplo:

Java

Flash

Logtalk

PHP

Objective-C

Visual Basic


9/9


9

Bibliografia

http://pt.wikipedia.org/wiki/Estrutura_de_dadoshttp://pt.wikipedia.org/wiki/Interface_(programa%C3%A7%C3%A3o)

http://pt.wikipedia.org/wiki/Pilha

Documents

Pilhas_Adiministracao e Estrutura de Dados