A pilha nada mais é do que a estrutura de dados linear onde a inserção e a exclusão ocorrem apenas em uma extremidade. A operação de inserção tem um nome especial conhecido como PUSH e a operação de exclusão também tem um nome especial conhecido como POP. O PUSH e o POP são duas operações fundamentais que podem ser realizadas apenas em uma determinada pilha. É um grupo de locais de memória e os locais de memória estão relacionados à memória de leitura ou memória de gravação. Isso é usado para armazenar informações binárias durante a execução do programa; quando estivermos executando qualquer programa, o conteúdo desse programa será armazenado na pilha. Segue-se Ultimo a entrar primeiro a sair (UEPS) e é usado apenas para armazenar e recuperar os dados, mas não é usado para armazenar os dados. A breve explicação do stack / stack pointer é discutida abaixo.
O que é Stack / Stack Pointer?
Definição: A pilha é um dispositivo de armazenamento, usado para armazenar informações ou dados na forma de LIFO (Last In First Out). Sempre que inserimos os dados na forma LIFO, o elemento que deve ser excluído primeiro é o último elemento de inserção, portanto, o último elemento inserido é retirado primeiro. É a unidade de memória dentro de um registrador de endereço chamado stack pointer (SP). O ponteiro da pilha sempre indica o elemento superior da pilha, o que significa em qual local os dados devem ser inseridos.
Tipos de pilha
Existem dois tipos de pilhas: pilha de registro e pilha de memória.
Registrar pilha
A pilha de registros também é um dispositivo de memória presente na unidade de memória, mas trata apenas de uma pequena quantidade de dados. A profundidade da pilha é sempre limitada na pilha de registros porque o tamanho da pilha de registros é muito pequeno em comparação com a memória.
Operação push na pilha de registro
Passo 1: O ponteiro da pilha é incrementado em 1.
SP ← SP + 1
Passo 2: Insira os dados na pilha.
1000 [SP] ← CT
Onde DR é o registro de dados
Etapa 3: Verifique se a pilha está cheia ou não
if (sp = 0) then (full ← 1)
Passo 4: Marca não vazia
vazio ← 0
Operação pop na pilha de registro
Passo 1: Leia os dados da pilha.
DR ← M [SP]
Passo 2: Diminuir o ponto da pilha.
SP ← SP-1
Etapa 3: Verifique se a pilha está vazia ou não
se sp = 0 então vazio ← 1
A organização da pilha de registro de 64 bits é mostrada na figura abaixo.
Registrar organização de pilha
Pilha de Memória
Na pilha de memória, a profundidade da pilha é flexível. Ele ocupa uma grande quantidade de dados da memória, enquanto na pilha de registros apenas um número finito de palavras da memória será armazenado.
Operação push na pilha de memória
Passo 1: SP ← SP-1
Passo 2: 1000 [SP] ← CT
Operação pop na pilha de memória
Passo 1: DR ← M [SP]
Passo 2: SP ← SP-1
Compare com a unidade de registro, a unidade de memória armazena uma grande quantidade de dados. A figura da pilha de memória é mostrada na figura abaixo.
Pilha de Memória
A unidade de memória total é dividida em três partes, a primeira unidade de memória contém o programa (nada além de instruções), a segunda parte são dados (operandos) e a terceira parte é pilha. As instruções do programa sempre são armazenadas no contador do programa (PC), os registros de dados são identificados pelo registro de endereço (AR). O endereço 3000 a 4001 usado para a pilha e o primeiro item ou elemento é armazenado em 4001.
Stack / Stack Pointer no microprocessador 8085
A visão do programador de 8085 microprocessador contém registros de uso geral e registros de uso especial . Os registradores de propósito geral são A, B, C, D, E, H, L e os registradores de propósito especial são SP (Stack Pointer) e PC (Program Counter). A visão do programador do microprocessador 8085 é mostrada na figura abaixo.
Visão do programador de 8085
O ponteiro da pilha é um registro de 16 bits que contém o endereço da memória, suponha que o conteúdo do ponteiro da pilha (SP) seja FC78H, então o microprocessador 8085 o interpreta. Os locais de memória têm informações úteis de FC78H a FFFH e de FC77H a 0000H o local de memória não tem informações úteis. A interpretação do ponteiro da pilha é mostrada na figura abaixo.
Interpretação do Stack Pointer
Operações básicas de Stack / Stack Pointer
Existem duas operações da pilha: operação PUSH e operação POP.
Operação PUSH
O PUSH significa empurrar ou inserir um elemento na pilha. A operação PUSH sempre incrementa o ponteiro da pilha e a operação POP sempre diminui o ponteiro da pilha. No caso de uma operação push, temos que verificar se há espaço livre disponível ou não. Se houver espaço livre disponível, podemos ir para a operação push; se o espaço livre não estiver disponível, ocorrerá uma mensagem de erro de estouro. O estouro deve ser verificado no caso de operação push respectivamente. A operação básica de push and pop é mostrada na figura abaixo.
Operação básica de PUSH e POP
A Figura (a) é a pilha. Se você quiser empurrar o elemento que está inserindo o elemento na pilha, você deve empurrar (s, a), onde 's' nada mais é do que uma pilha. Na pilha, estamos colocando o elemento 'a' e esta operação é mostrada na figura (b). Veja a figura (3), suponha que a pilha contenha três elementos a, b, c, e a pilha seja preenchida com um elemento.
Se você deseja inserir um quarto elemento-'d' usando push (s, d), mas não há espaço disponível para inserir o elemento, isso indica que a pilha está sobrecarregada. A terminologia de estouro é usada quando a pilha está cheia e o algoritmo de operação push é mostrado abaixo.
empurrar (pilha [], topo, pilha máxima, item)
if (top == maxstack-1)
{
imprimir “estouro”
}
outro
{
top = top + 1
empilhar [topo] = item
}
fim
Operação POP
O POP significa excluir o elemento no topo da pilha. No caso da operação pop, temos que verificar se a pilha está inicialmente vazia ou não. Se a pilha estiver inicialmente vazia, ocorre uma situação de estouro negativo. Suponha que a pilha esteja vazia, mas você deseja estourar os elementos na pilha, mas não há elementos na pilha, então isso leva ao estouro negativo da pilha.
O estouro negativo deve ser verificado no caso de operação pop, respectivamente. Na operação pop, seja qual for o elemento superior presente na pilha que deve ser exibido ou excluído, não há necessidade de mencionar qual elemento será exibido, por padrão, o elemento superior será exibido. O algoritmo de operação pop é mostrado abaixo.
pop (pilha [], topo, item)
if (topo == - 1)
{
imprimir “underflow”
}
outro
{
item = pilha [topo]
top = top-1
}
Exemplo
Os elementos são inseridos na ordem de A, B, C, D, E, que representa a pilha de cinco elementos. Na figura (a), queremos empurrar o elemento 'A' na pilha, então o topo se torna zero (topo = 0), da mesma forma o topo = 1 quando o elemento 'B' é pressionado, topo = 2 quando o elemento 'C' é pressionado, top = 3 quando o elemento 'D' é pressionado e top = 4 quando o elemento 'E' é pressionado.
Portanto, quaisquer elementos que peguei são colocados na pilha, agora a pilha está cheia. Se você quiser empurrar outro elemento, não há lugar na pilha, então isso indica o estouro. Agora a pilha está cheia se você quiser abrir o elemento ‘E’, o elemento deve ser excluído primeiro. A operação de push é mostrada na figura abaixo.
Operação Push
Temos que usar a operação pop para excluir os elementos da pilha. Portanto, apenas mencione pop (), não escreva argumentos no pop porque, por padrão, ele exclui o elemento superior. O primeiro elemento ‘E’ é excluído próximo elemento ‘D’… .. ’A’. Quando os elementos superiores estão sendo excluídos, o valor superior diminui. Quando top = -1 a pilha indica underflow. A operação pop é mostrada na figura abaixo.
Operação POP
Portanto, esta é a explicação de como os elementos são inseridos e excluídos da pilha usando a operação push e pop.
Formulários
As aplicações do stack / stack pointer são
- Reversão da corda
- Parênteses equilibrado
- DESFAZER / DEDO
- Pilha do sistema para registros de ativação
- Infix, prefix, postfix, expression
FAQs
1). Qual é o ponteiro da pilha no braço?
O registrador de ponteiro de pilha (R13) usado como um ponteiro para a pilha ativa no ARM.
2). Por que o ponteiro da pilha é de 16 bits?
O ponteiro da pilha (SP) e o contador do programa (PC) utilizados para armazenar a localização anterior e o endereço da localização da memória é de 16 bits, então o ponteiro da pilha (SP) também é de 16 bits.
3). Qual é a função do ponteiro da pilha?
A função do ponteiro da pilha (SP) é indicar o topo do elemento na pilha.
4). Qual pilha é usada em 8085?
A pilha usada em 8085 é Last In First Out (LIFO).
5). O ponteiro da pilha é um registro?
Sim, o stack pointer (SP) é um registrador de endereço que sempre indica o topo do elemento na pilha.
