TechCodeview

Em vez de usar array, também podemos usar lista vinculada para implementar pilha. A lista vinculada aloca a memória dinamicamente. No entanto, a complexidade do tempo em ambos os cenários é a mesma para todas as operações, ou seja, push, pop e peek.

Na implementação de pilha de lista vinculada, os nós são mantidos de forma não contígua na memória. Cada nó contém um ponteiro para seu nó sucessor imediato na pilha. Diz-se que a pilha está sobrecarregada se o espaço restante na pilha de memória não for suficiente para criar um nó.

padrões de design em java

O nó superior da pilha sempre contém nulo em seu campo de endereço. Vamos discutir a maneira como cada operação é executada na implementação de lista vinculada de pilha.

Adicionando um nó à pilha (operação Push)

Adicionar um nó à pilha é conhecido como empurrar Operação. Enviar um elemento para uma pilha na implementação de lista vinculada é diferente de uma implementação de array. Para colocar um elemento na pilha, as etapas a seguir estão envolvidas.

1. Crie um nó primeiro e aloque memória para ele.
2. Se a lista estiver vazia, o item deverá ser enviado como o nó inicial da lista. Isso inclui atribuir valor à parte de dados do nó e atribuir nulo à parte de endereço do nó.
3. Se já existirem alguns nós na lista, então temos que adicionar o novo elemento no início da lista (para não violar a propriedade da pilha). Para isso, atribua o endereço do elemento inicial ao campo de endereço do novo nó e faça do novo nó o nó inicial da lista.

Complexidade de tempo: o(1)





Implementação C:

 void push () { int val; struct node *ptr =(struct node*)malloc(sizeof(struct node)); if(ptr == NULL) { printf('not able to push the element'); } else { printf('Enter the value'); scanf('%d',&val); if(head==NULL) { ptr->val = val; ptr -> next = NULL; head=ptr; } else { ptr->val = val; ptr->next = head; head=ptr; } printf('Item pushed'); } } 

Excluindo um nó da pilha (operação POP)

Excluir um nó do topo da pilha é conhecido como pop Operação. A exclusão de um nó da implementação da lista vinculada da pilha é diferente daquela da implementação da matriz. Para retirar um elemento da pilha, precisamos seguir as seguintes etapas:

Verifique a condição de underflow:A condição de underflow ocorre quando tentamos sair de uma pilha já vazia. A pilha estará vazia se o ponteiro principal da lista apontar para nulo.Ajuste o ponteiro principal de acordo:Na pilha, os elementos são removidos apenas de uma extremidade, portanto, o valor armazenado no ponteiro principal deve ser excluído e o nó deve ser liberado. O próximo nó do nó principal agora se torna o nó principal.

Complexidade de tempo: o (n)

string java cmp

Implementação C

 void pop() { int item; struct node *ptr; if (head == NULL) { printf('Underflow'); } else { item = head->val; ptr = head; head = head->next; free(ptr); printf('Item popped'); } } 

Exibir os nós (Traversing)

A exibição de todos os nós de uma pilha precisa percorrer todos os nós da lista vinculada organizada na forma de pilha. Para isso, precisamos seguir os seguintes passos.

1. Copie o ponteiro principal em um ponteiro temporário.
2. Mova o ponteiro temporário por todos os nós da lista e imprima o campo de valor anexado a cada nó.

Complexidade de tempo: o (n)

Implementação C

 void display() { int i; struct node *ptr; ptr=head; if(ptr == NULL) { printf('Stack is empty
'); } else { printf('Printing Stack elements 
'); while(ptr!=NULL) { printf('%d
',ptr->val); ptr = ptr->next; } } } 

Programa baseado em menu em C implementando todas as operações de pilha usando lista vinculada:

 #include #include void push(); void pop(); void display(); struct node { int val; struct node *next; }; struct node *head; void main () { int choice=0; printf('
*********Stack operations using linked list*********
'); printf('
----------------------------------------------
'); while(choice != 4) { printf('

Chose one from the below options...
'); printf('
1.Push
2.Pop
3.Show
4.Exit'); printf('
 Enter your choice 
'); scanf('%d',&choice); switch(choice) { case 1: { push(); break; } case 2: { pop(); break; } case 3: { display(); break; } case 4: { printf('Exiting....'); break; } default: { printf('Please Enter valid choice '); } }; } } void push () { int val; struct node *ptr = (struct node*)malloc(sizeof(struct node)); if(ptr == NULL) { printf('not able to push the element'); } else { printf('Enter the value'); scanf('%d',&val); if(head==NULL) { ptr->val = val; ptr -> next = NULL; head=ptr; } else { ptr->val = val; ptr->next = head; head=ptr; } printf('Item pushed'); } } void pop() { int item; struct node *ptr; if (head == NULL) { printf('Underflow'); } else { item = head->val; ptr = head; head = head->next; free(ptr); printf('Item popped'); } } void display() { int i; struct node *ptr; ptr=head; if(ptr == NULL) { printf('Stack is empty
'); } else { printf('Printing Stack elements 
'); while(ptr!=NULL) { printf('%d
',ptr->val); ptr = ptr->next; } } }