Estrutura de dados e algoritmos - pilha
Uma pilha é um tipo abstrato de dados (ADT), comumente usado na maioria das linguagens de programação. É denominado pilha, pois se comporta como uma pilha do mundo real, por exemplo - um baralho de cartas ou uma pilha de pratos, etc.
Uma pilha do mundo real permite operações em apenas uma extremidade. Por exemplo, podemos colocar ou remover um cartão ou prato apenas do topo da pilha. Da mesma forma, Stack ADT permite todas as operações de dados em apenas uma extremidade. A qualquer momento, podemos acessar apenas o elemento superior de uma pilha.
Este recurso torna a estrutura de dados LIFO. LIFO significa Last-in-first-out. Aqui, o elemento que é colocado (inserido ou adicionado) por último é acessado primeiro. Na terminologia da pilha, a operação de inserção é chamadaPUSH operação e operação de remoção é chamada POP Operação.
Representação de pilha
O diagrama a seguir descreve uma pilha e suas operações -
Uma pilha pode ser implementada por meio de Array, Structure, Pointer e Linked List. A pilha pode ser de tamanho fixo ou pode ter uma sensação de redimensionamento dinâmico. Aqui, vamos implementar a pilha usando arrays, o que a torna uma implementação de pilha de tamanho fixo.
Operações básicas
As operações de pilha podem envolver inicializar a pilha, usá-la e, em seguida, desinicializá-la. Além desses itens básicos, uma pilha é usada para as duas operações principais a seguir -
push() - Empurrar (armazenar) um elemento na pilha.
pop() - Remover (acessar) um elemento da pilha.
Quando os dados são colocados na pilha.
Para usar uma pilha de forma eficiente, precisamos verificar o status da pilha também. Para o mesmo propósito, a seguinte funcionalidade é adicionada às pilhas -
peek() - obtém o elemento de dados superior da pilha, sem removê-lo.
isFull() - verifique se a pilha está cheia.
isEmpty() - verifique se a pilha está vazia.
Em todos os momentos, mantemos um ponteiro para os últimos dados PUSHed na pilha. Como este ponteiro sempre representa o topo da pilha, portanto denominadotop. otop O ponteiro fornece o valor do topo da pilha sem realmente removê-lo.
Primeiro devemos aprender sobre os procedimentos para suportar funções de pilha -
olhadinha()
Algoritmo da função peek () -
begin procedure peek
return stack[top]
end procedureImplementação da função peek () na linguagem de programação C -
Example
int peek() {
return stack[top];
}está cheio()
Algoritmo da função isfull () -
begin procedure isfull
if top equals to MAXSIZE
return true
else
return false
endif
end procedureImplementação da função isfull () na linguagem de programação C -
Example
bool isfull() {
if(top == MAXSIZE)
return true;
else
return false;
}está vazia()
Algoritmo da função isempty () -
begin procedure isempty
if top less than 1
return true
else
return false
endif
end procedureA implementação da função isempty () na linguagem de programação C é um pouco diferente. Inicializamos top em -1, pois o índice na matriz começa em 0. Portanto, verificamos se top está abaixo de zero ou -1 para determinar se a pilha está vazia. Aqui está o código -
Example
bool isempty() {
if(top == -1)
return true;
else
return false;
}Operação Push
O processo de colocar um novo elemento de dados na pilha é conhecido como Operação Push. A operação push envolve uma série de etapas -
Step 1 - Verifica se a pilha está cheia.
Step 2 - Se a pilha estiver cheia, produz um erro e sai.
Step 3 - Se a pilha não estiver cheia, incrementos top para apontar o próximo espaço vazio.
Step 4 - Adiciona elemento de dados ao local da pilha, para onde o topo está apontando.
Step 5 - Retorna sucesso.
Se a lista vinculada for usada para implementar a pilha, na etapa 3, precisamos alocar o espaço dinamicamente.
Algoritmo para Operação PUSH
Um algoritmo simples para operação Push pode ser derivado da seguinte forma -
begin procedure push: stack, data
if stack is full
return null
endif
top ← top + 1
stack[top] ← data
end procedureA implementação deste algoritmo em C é muito fácil. Veja o seguinte código -
Example
void push(int data) {
if(!isFull()) {
top = top + 1;
stack[top] = data;
} else {
printf("Could not insert data, Stack is full.\n");
}
}Operação Pop
Acessar o conteúdo removendo-o da pilha é conhecido como Operação Pop. Em uma implementação de array da operação pop (), o elemento de dados não é realmente removido, em vez dissotopé diminuído para uma posição inferior na pilha para apontar para o próximo valor. Mas na implementação de lista vinculada, pop () realmente remove o elemento de dados e desaloca o espaço da memória.
Uma operação Pop pode envolver as seguintes etapas -
Step 1 - Verifica se a pilha está vazia.
Step 2 - Se a pilha estiver vazia, produz um erro e sai.
Step 3 - Se a pilha não estiver vazia, acessa o elemento de dados no qual top está apontando.
Step 4 - Diminui o valor do topo em 1.
Step 5 - Retorna sucesso.
Algoritmo para Operação Pop
Um algoritmo simples para a operação Pop pode ser derivado da seguinte maneira -
begin procedure pop: stack
if stack is empty
return null
endif
data ← stack[top]
top ← top - 1
return data
end procedureA implementação deste algoritmo em C é a seguinte -
Example
int pop(int data) {
if(!isempty()) {
data = stack[top];
top = top - 1;
return data;
} else {
printf("Could not retrieve data, Stack is empty.\n");
}
}Para um programa de pilha completo em linguagem de programação C, clique aqui .