Implementação da pilha em C

Podemos implementar a estrutura de dados através da linguagem C. Existem vários tipos de estrutura de dados disponíveis para armazenar e acessar os dados de uma maneira eficiente. Stack é um deles.

Uma pilha é uma versão modificada da matriz. Podemos adicionar ou remover um elemento no final da pilha. Este fim está no Principal da pilha.

Stack é uma maneira especializada de manusear, armazenar, inserir, excluir, acessar os dados. É abstrato de natureza.

Array e pilha

1. Há um pouco de diferença entre a matriz e a pilha em termos de acessibilidade. Podemos acessar qualquer elemento da matriz em qualquer condição, mas no caso da pilha, podemos inserir ou excluir o elemento de uma extremidade um por um. Este fim é chamado de topo. Em termos de acessibilidade, a matriz é mais rápida que a pilha.
2. Stack tem duas funções principais chamadas push e pop.
3. A função push é usada para inserir em uma pilha e a função pop é usada para remover um elemento da pilha.

Representação

Só podemos acessar o último elemento inserido na pilha. Este é o topo da pilha. Podemos inserir ou remover de cima.

Isso é conhecido como o último em Fast Out (LIFO) e o Fast In Last Out (filo).

Implementação

A pilha pode ser implementada da seguinte maneira:

-> Array -> Array Dynamic -> Lista de links

Operação

-> Push -> pop

Push de algoritmo: push (pilha, top, maxstk, item)

1. [Stack está cheia]

Se top == maxstk

Mostrar mensagem: Transbordar e retornar

2. Set top = top + 1
3. Definir pilha [top] = item
4. Retornar

Algoritmo pop: pop (pilha, top, item)

1. [Elemento removido da pilha]

Se top == -1

Mostrar mensagem: Subfluir e retornar

2. Definir item = pilha [topo]
3. TOP: TOP -1
4. Retornar

Empilhe usando a matriz

Struct ArrayStack

int top;
capacidade não assinada;
Array int *;

Aqui, definimos um tipo de dados definido pelo usuário chamado ArrayStack. Possui três membros de dados chamados top, capacidade e um ponteiro chamado *Array.

Notação polonesa

A notação polonesa é escrever operadores de uma expressão antes ou depois do seu operando.

Maneiras de escrever:

Infix 2. Prefixo 3. Postfix

Infixo

Os operadores são mantidos entre os dois operandos.

Exemplo: A + B

Prefixo

Os operadores são mantidos antes de seus operando.

Exemplo: + A B

Postfix

Os operadores são mantidos após seus operandos.

Exemplo: A B +

Converter

1.

Infixo:
(A + b) * C
Prefixo:
* + A B C
Postfix:
A B + C *

2.

Infixo:
A + (b * c)
Prefixo:
+ A * b c
Postfix:
A B C * +

3.

Infix :( a + b) / (c - d)
Prefixo:/ + a b - c d
Postfix: A B + C D - /

Toda essa conversão pode ser feita usando a pilha. Agora, queremos mostrar como uma pilha pode ser criada e como o elemento ou dados é inserido. Os elementos podem ser removidos da pilha através da programação.

Exemplo de programação

#incluir
#incluir
Int item;
struct ArrayStack // define um tipo de dados;

int top;
capacidade int;
Array int *;
;
struct ArrayStack *CreateStack (int cap) // Crie uma pilha;

Struct ArrayStack *pilha;
pilha = malloc (sizeof (struct ArrayStack));
pilha-> top = - 1;
pilha-> capacidade = cap;
pilha-> array = malloc (sizeof (int) * pilha-> capacidade);
retornar (pilha);

int completo (struct ArrayStack *pilha) // Verificando a pilha está cheia ou não.

if (pilha-> top == pilha-> capacidade-1)
retornar (1);
outro
retornar (0);

int em vazio (struct arraystack *pilha) // verificando a pilha está vazia ou não.

if (pilha-> top == -1)
retornar (1);
outro
retornar (0);

Void Push (Struct ArrayStack *Stack, int item) // Insira elementos na pilha;

se ( !pilha completa ) )

pilha-> top ++;
Stack-> Array [Stack-> top] = Item;


int pop (struct ArrayStack *pilha) // remove os elementos da pilha;

se ( !vazio (pilha))

Item = Stack-> Array [Stack-> Top];
pilha-> top--;
devolver item ) ;

retornar (-1);

int main ()

int escolha;
Struct ArrayStack *pilha;
Stack = CreateStack (4);
enquanto (1)

printf ("\ n 1 . empurrar " ) ;
printf ("\ n 2 . pop ");
printf ("\ n 3 . saída \ n ");
printf ("Digite sua escolha \ n");
scanf ("%d", & escolha);
Switch (escolha)

caso 1:
printf ("Digite um número \ n");
scanf (" %d", & item);
push (pilha, item);
quebrar ;
Caso 2:
item = pop (pilha);
if (item == - 1)
printf ("pilha está vazia");
outro
printf ("valor popped é %d", item);
quebrar ;
Caso 3:
saída (0);


retornar 0;

Saída:

Explicação

Como dissemos anteriormente, definimos um tipo de dados definido pelo usuário chamado ArrayStack. Possui três membros de dados chamados top, capacidade e uma matriz de ponteiro. Em seguida, definimos uma função chamada CreateStack, onde passamos um valor que o bloco total de matriz é criado. A função MALLOC () cria essa matriz e retorna o endereço para a pilha variável, que é o tipo ArrayStack. A pilha-> Array mantém o endereço da matriz que é criada pela função Malloc ().

Em seguida, definimos outra função chamada completa () para verificar se a pilha está cheia ou não.

Crie outra função chamada vazia para verificar se a pilha está vazia.

Em seguida, definimos outra função chamada push (), onde inserimos os elementos um por um na pilha de uma extremidade chamada top. Para inserir o elemento na pilha, primeiro verificamos se a pilha está cheia.

Em seguida, definimos outra função chamada pop (), onde excluímos os elementos um por um da pilha de uma extremidade chamada top. Para remover o elemento na pilha, primeiro verificamos se a pilha está vazia.

Em seguida, dentro da função Main (), escrevemos o estojo para dar ao usuário uma opção de menu para selecionar sua escolha se o elemento é inserido ou excluído na pilha.

Conclusão

Desde a discussão sobre a pilha, chegamos a chegar a essa conclusão de que a pilha é uma estrutura de dados bem definida, usada para gerenciar os dados de uma maneira estrutural. Nossa pilha de vida diária é implementada em vários campos para armazenar, inserir ou excluir elementos.