Uma PILHA é uma estrutura de dados “linear” na qual os elementos são inseridos por uma de suas extremidades (normalmente conhecida como “o topo”) e são removidos pela mesma.
Temos muitos exemplos de uso de pilhas no mundo real, como pilha de pratos numa cozinha, pilha de caixas num deposito, entre outras.
O que deve ser realizado na questão:
Esta questão visa verificar sua habilidade de fazer um teste de mesa para pilhas. No teste de mesa, devemos realizar as operações nós mesmos, com papel e caneta; ou no editor de texto, neste caso.
Faça uma sequencia de 15 operações de inserção e remoção de elementos, aleatoriamente, numa única pilha. Mostre o estado da pilha a cada passo. Se a pilha ficar vazia, não tem problema; apenas deixe isto indicado.
Por exemplo, se a sua pilha for de nomes:
Figura 1: exemplo de teste de mesa.
Dicas:
· Você deve escolher o tipo de elemento e a sequencia de operações.
· Procure deixar sua pilha com pelo menos 5 elementos em algum momento.
· O exercício pode terminar com a pilha contendo diversos elementos.
· As operações de inserção e remoção em pilha se chamam “push” e “pop” (em inglês).
· Assista às videoaulas 1.1, 1.2 e 2.1.
Respostas
Oi!
Para te ajudar a criar o seu próprio algoritmo, abaixo está descrita uma rotina, que serve de exemplo de programa que faz uma sequencia de 15 operações de inserção e remoção de elementos, aleatoriamente, numa única pilha.
Você pode fazer suas modificações, caso ache pertinente.
record Nodo {
data //informação a ser armazenada no nodo
próximo // referência ao próximo nodo; null para o último nodo
}
record Stack {
Node stackPointer // ponteiro para o nodo do topo; valor null para uma pilha vazia
}
function push(Stack stack, Element element) { // insere elemento em uma pilha
new(newNode) // Allocate memory to hold new node
newNode.data := element
newNode.next := stack.stackPointer
stack.stackPointer := newNode
}
function pop(Stack stack) { // retira o elemento do topo e retorna o nodo do topo agora
node := stack.stackPointer
stack.stackPointer := node.next
element := node.data
return element
}
function top(Stack stack) { // retorna o nodo no topo
return stack.stackPointer.data
}
function length(Stack stack) { // retorna a quantidade de nodos na pilha
length := 0
node := stack.stackPointer
while node not null {
length := length + 1
node := node.next
}
return length
}
QUESTÃO (A)
Operação 1 : push (“1”);
Pilha == topo: 1: Fundo
Operação 2 : push (“2”);
Pilha == topo: 2, 1 : Fundo
Operação 3 : push (“3”);
Pilha == topo: 3, 2, 1 : Fundo
Operação 4 : push (“4”);
Pilha == topo: 4, 3, 2, 1: Fundo
Operação 5 : push (“5”);
Pilha == topo: 5, 4, 3, 2, 1: Fundo
Operação 6 : push (“6”);
Pilha == topo: 6, 5, 4, 3, 2, 1 : Fundo
Operação 7 : push (“7”);
Pilha == topo: 7, 6, 5, 4, 3, 2, 1: Fundo
Operação 8 : pop ( );
Pilha == topo: 6, 5, 4, 3, 2, 1: Fundo
Operação 9 : push (“9”);
Pilha == topo: 9, 7, 6, 5, 4, 3, 2, 1: Fundo
Operação 10 : pop ( );
Pilha == topo: 7, 6, 5, 4, 3, 2, 1 : Fundo
Operação 11 : push (“11”);
Pilha == topo: 11, 7, 6, 5, 4, 3, 2, 1: Fundo
Operação 12 : push (“12”);
Pilha == topo: 12, 11, 7, 6, 5, 4, 3, 2, 1: Fundo
Operação 13 : push (“13”);
Pilha == topo: 13, 12, 11, 7, 6, 5, 4, 3, 2, 1: Fundo
Operação 14 : push (“14”);
Pilha == topo: 14, 13, 12, 11, 7, 6, 5, 4, 3, 2, 1: Fundo
Operação 15 : pop ( );
Pilha == topo: 13, 12, 11, 7, 6, 5, 4, 3, 2, 1: Fundo
QUESTÃO (B)
#include <stdio.h>
#include <conio.h>
#define TAM 5
struct tad_fila
{
int e[TAM];
int ini, fim;
};
struct tad_fila f;
void enfileirar()
void desenfileirar
void enqueue(int)
int dequeue();
void main()
{
f.ini = 0;
f.fim = -1;
enfileirar()
enfileirar()
enfileirar()
desenfileirar()
desenfileirar()
desenfileirar()
_getch();
}
void enfileirar()
{
int n;
printf("informe o numero :");
scanf_s("%d", &n);
enqueue(n);
}
void desenfileirar
{
int n;
n = dequeue();
printf("\n0 valor retirado da fila foi: %d", n);
}
void enqueue(int n)
{
if (f.fim < TAM - 1)
{
f.fim++;
f.e[f.fim] = n;
}
else
printf("fila cheia!");
}
int dequeue()
{
int n;
if (f.ini <= f fim)
{
n = f.e[f.ini];
f.ini++;
}
else
{
printf("fila vazia!");
n = 0;
}
return n;
}