Anúncios

Uma pilha é um Tipo de Dados Abstrato (ADT), comumente utilizados na maioria das linguagens de programação. Ele é nomeado stack como se comporta como uma pilha do mundo real, por exemplo-um baralho de cartas ou uma pilha de placas, etc.

uma pilha real permite operações apenas numa extremidade. Por exemplo, podemos colocar ou remover um cartão ou placa do topo da pilha apenas., Da mesma forma, Stack ADT permite todas as operações de dados em um único fim. A qualquer momento, só podemos acessar o elemento superior de uma pilha.

Esta característica torna a sua estrutura de dados ao longo da vida. “LIFO” significa “Last-in-first-out”. Aqui, o elemento que é colocado (inserido ou adicionado) último, é acessado primeiro. Na terminologia da pilha, a operação de inserção é chamada operação PUSH e a operação de remoção é chamada Operação POP.,

representação na pilha

O diagrama seguinte mostra uma pilha e as suas operações −

uma pilha pode ser implementada através de uma lista, estrutura, ponteiro e lista ligada. Stack pode ser um tamanho fixo ou pode ter uma sensação de redimensionamento dinâmico. Aqui, vamos implementar stack usando arrays, o que faz com que seja uma implementação de stack de tamanho fixo.

Operações Básicas

as operações de pilha podem envolver a inicialização da pilha, usando-a e depois des-inicializando-a., Além destas coisas básicas, uma pilha é usada para as duas seguintes operações primárias −

  • push() − Pushing (armazenar) um elemento na pilha.

  • pop() − removendo (acessando) um elemento da pilha.

Quando os dados são empurrados para a pilha.

para usar uma pilha de forma eficiente, precisamos verificar o estado da pilha também. Para o mesmo propósito, a seguinte funcionalidade é adicionada às pilhas −

  • peek() − obter o elemento de dados de topo 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 empurrados na pilha. Como este ponteiro sempre representa o topo da pilha, daí chamado top. O ponteiro superior fornece o valor superior da pilha sem realmente removê-lo., suporte de pilha de funções −

peek()

Algoritmo de peek() função −

begin procedure peek return stackend procedure

Implementação de peek() função em linguagem de programação C −

Exemplo

int peek() { return stack;}

isfull()

Algoritmo de isfull() função −

begin procedure isfull if top equals to MAXSIZE return true else return false endif end procedure

Implementação de isfull() função em linguagem de programação C −

Exemplo

bool isfull() { if(top == MAXSIZE) return true; else return false;}

isempty()

Algoritmo de isempty() função −

begin procedure isempty if top less than 1 return true else return false endif end procedure

Implementação de isempty() função em C linguagem de programação é um pouco diferente., Inicializamos o topo em -1, como o índice na matriz começa a partir de 0. Então nós verificamos se o topo está abaixo de zero ou -1 para determinar se a pilha está vazia. Aqui está o código –

exemplo

bool isempty() { if(top == -1) return true; else return false;}

Push Operation

o processo de colocar um novo elemento de dados na pilha é conhecido como uma operação Push. A operação de Push envolve uma série de passos −

  • Passo 1 − verifica se a pilha está cheia.

  • Passo 2 − Se a pilha estiver cheia, produz um erro e sai.

  • Passo 3 − Se a pilha não estiver cheia, os incrementos vão de cima para o próximo espaço vazio.,

  • Passo 4-adiciona o elemento de dados à localização da pilha, onde o topo está a apontar.

  • Passo 5 − Devolve o sucesso.

Se a lista ligada for usada para implementar a pilha, então no Passo 3, precisamos alocar o espaço dinamicamente.

algoritmo para a operação PUSH

um algoritmo simples para a 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 ← dataend procedure

implementação deste algoritmo em C, é muito fácil., Veja o seguinte código

Exemplo

void push(int data) { if(!isFull()) { top = top + 1; stack = data; } else { printf("Could not insert data, Stack is full.\n"); }}

Operação Pop

Acessando o conteúdo ao removê-lo da pilha, é conhecido como uma Operação Pop. Em uma implementação de array da operação pop (), o elemento de dados não é realmente removido, em vez de top é decrementado para uma posição mais baixa na pilha para apontar para o próximo valor. Mas na implementação da lista ligada, pop() realmente remove o elemento de dados e desalocata o espaço de memória.

uma operação Pop pode envolver os seguintes passos −

  • Passo 1-verifica se a pilha está vazia.,

  • Passo 2 − Se a pilha estiver vazia, produz um erro e sai.

  • Passo 3 − Se a pilha não estiver vazia, acede ao elemento de dados em que o topo está a apontar.

  • Passo 4 − diminui o valor do topo em 1.

  • Passo 5 − Devolve o sucesso.,

Algorithm for Pop Operation

A simple algorithm for Pop operation can be derived as follows −

begin procedure pop: stack if stack is empty return null endif data ← stack top ← top - 1 return dataend procedure

Implementation of this algorithm in C, is as follows −

Example

int pop(int data) { if(!isempty()) { data = stack; top = top - 1; return data; } else { printf("Could not retrieve data, Stack is empty.\n"); }}

For a complete stack program in C programming language, please click here.

Advertisements