O Stack (pilha) é como um tubo fechado de um lado e aberto de outro, onde o primeiro elemento inserido é o último a sair e vice-versa. Alguns dos exemplos em que uma pilha pode ser usada é em mecanismos de desfazer/refazer de editores, navegação entre páginas web, etc.
Veja como implementamos uma pilha em C:
Estruturas e chamadas das funções:
struct pilha {
int topo; // Posição do elemento.
int capa;
float *prElem;
};
void criarPilha(struct pilha *p, int c);
int estaVazia(struct pilha *p);
int estaCheia(struct pilha *p);
void empilhar(struct pilha *p, float v);
float desempilhar(struct pilha *p);
float retornaTopo(struct pilha *p);
Implementações das funções:
void criarPilha(struct pilha *p, int c) {
p->topo = -1;
p->capa = c;
p->prElem = (float*)malloc(c * sizeof(float));
}
int estaVazia(struct pilha *p) {
if(p->topo == -1) {
return 1;
}
return 0;
}
int estaCheia(struct pilha *p) {
if(p->topo == p->capa - 1) {
return 1;
}
return 0;
}
void empilhar(struct pilha *p, float v) {
p->topo++;
p->prElem[p->topo] = v;
}
float desempilhar(struct pilha *p) {
float aux = p->prElem[p->topo];
p->topo--;
return aux;
}
float retornaTopo(struct pilha *p) {
return p->prElem[p->topo];
}
Código principal:
struct pilha pl;
int capac, op;
float valor;
printf("Capacidade da pilha? ");
scanf("%d", &capac);
criarPilha(&pl, capac);
while(1) { // Loop infinito
printf("\n1 - Empilhar (push)");
printf("\n2 - Desempilhar (pop)");
printf("\n3 - Mostrar o Topo (top)");
printf("\n4 - Sair (exit)\n");
printf("\nOpção? ");
scanf("%d", &op);
switch(op) {
case 1: // push
if(estaCheia(&pl) == 1) {
printf("\nPILHA CHEIA!\n");
}
else {
printf("\nValor? ");
scanf("%f", &valor);
empilhar(&pl, valor);
}
break;
case 2: // pop
if(estaVazia(&pl) == 1) {
printf("\nPILHA VAZIA!\n");
}
else {
valor = desempilhar(&pl);
printf("\n%.1f desempilhado!\n", valor);
}
break;
case 3: // top
if(estaVazia(&pl) == 1) {
printf("\nPILHA VAZIA!\n");
}
else {
valor = retornaTopo(&pl);
printf("\nTopo: %.1f\n", valor);
}
break;
case 4:
exit(0);
break;
default:
printf("\nOPÇÃO INVÁLIDA!\n");
break;
}
}
PS: Podemos mudar o tipo de float para qualquer outro.
Diferente das pilhas, que funcionam como um "tubo", onde o último elemento é adicionado e somado até encher o tubo, as filas, os primeiros elementos saem à medida que entram novos, na verdade, as filas funcionam como "túneis". Em resumo, nas pilhas o último elemento é o primeiro a sair e vice-versa, nas filas o primeiro que entra é o primeiro que sai. Alguns dos exemplos em que uma fila pode ser usada é em controle de documentos (para impressão, por exemplo), troca de mensagem entre dispositivos numa rede, etc.
Veja como implementamos uma fila em C:
Estruturas e chamadas das funções:
struct fila {
int capac;
float *dados;
int prim;
int ult;
int itens;
};
void criarFila(struct fila *f, int c);
void inserir(struct fila *f, int v);
int remover(struct fila *f);
int estaVazia(struct fila *f);
int estaCheia(struct fila *f);
void mostrarFila(struct fila *f);
Implementações das funções:
void criarFila(struct fila *f, int c) {
f->capac = c;
f->dados = (float*)malloc(f->capac * sizeof(float));
f->prim = 0;
f->ult = -1;
f->itens = 0;
}
void inserir(struct fila *f, int v) {
if(f->ult == f->capac - 1) {
f->ult = -1;
}
f->ult++;
f->dados[f->ult] = v;
f->itens++; // Item inserido
}
int remover(struct fila *f) {
int temp = f->dados[f->prim++];
if(f->prim == f->capac) {
f->prim = 0;
}
f->itens--; // Item retirado
return temp;
}
int estaVazia(struct fila *f) {
return f->itens == 0;
}
int estaCheia(struct fila *f) {
return f->itens == f->capac;
}
void mostrarFila(struct fila *f) {
int cont, i;
for(cont = 0, i = f->prim; cont < f->itens; cont++) {
printf("%.2f\t", f->dados[i++]);
if(i == f->capac) {
i = 0;
}
}
printf("\n\n");
}
Código principal:
int op, capa;
float valor;
struct fila fl;
printf("Capacidade da fila? ");
scanf("%d", &capa);
criarFila(&fl, capa);
while(1) { // Loop infinito
printf("\n1 - Inserir Elemento (enqueue)");
printf("\n2 - Remover Elemento (dequeue)");
printf("\n3 - Mostrar Fila (peek)");
printf("\n4 - Sair (exit)\n");
printf("\nOpção? ");
scanf("%d", &op);
switch(op) {
case 1: // enqueue
if(estaCheia(&fl)) {
printf("\nFILA CHEIA!\n");
}
else {
printf("\nValor? ");
scanf("%f", &valor);
inserir(&fl, valor);
}
break;
case 2: // dequeue
if(estaVazia(&fl)) {
printf("\nFILA VAZIA!\n");
}
else {
valor = remover(&fl);
printf("\n%.1f removido!\n", valor);
}
break;
case 3: // peek
if(estaVazia(&fl)) {
printf("\nFILA VAZIA!\n");
}
else {
printf("\nConteúdo da fila: ");
mostrarFila(&fl);
}
break;
case 4:
exit(0);
break;
default:
printf("\nOPÇÃO INVÁLIDA!\n");
break;
}
}
PS: Podemos mudar o tipo de float para qualquer outro.
No C, temos a biblioteca string.h que permite manipular arrays de char (já que string mesmo não existe em C).
Vamos supor esse código aqui:
// Isso dará erro:
char frase[20] = "Isso é uma string";
char copia[20] = *frase;
printf("%s\n", copia);
Por serem arrays, não é possível copiar conteúdos de um array de char para outro. Nesse caso usamos o método strcpy, assim:
char frase[20] = "Isso é uma string";
char copia[20];
strcpy(copia, frase); // Inclua string.h
printf("%s\n", copia);
Para concatenar, fazemos assim, usando o strcat:
char frase[50] = "Isso é uma string";
strcat(frase, " com mais alguma coisa!"); // Inclua string.h
printf("%s\n", frase);
E para retornar a quantidade de caracteres usamos o strlen, assim:
char frase[20] = "Isso é uma string";
int tam = strlen(frase);
printf("Tamanho do array de char: %d\n", tam);
Para ver se uma string está vazia, use a função strlen(), assim:
char* nome = "";
printf("Nome está vazio? %s\n", !strlen(nome) ? "true" : "false");
Podemos usar o strcmp para comparar conteúdos de strings:
char *f1 = "Frase 1";
char *f2 = "Frase 2";
char *resul = !strcmp(f1, f2) ? "iguais" : "diferentes";
printf("As frases são %s.\n", resul);
Se o resultado de strcmp for zero, as strings são iguais, se for menor o conteúdo é menor e se for maior que 0 o conteúdo é maior.
Para encontrar uma palavra numa string, fazemos assim, com o método strstr:
char frase[20] = "Isso é uma string";
char *resul = strstr(frase, "string");
if(resul != NULL) {
printf("A palavra foi encontrada!\n");
}
else {
printf("Não existe essa palavra na string!\n");
}
Para dividir uma string, usamos o método strtok assim:
char frase[20] = "Isso é uma string";
char *divi;
divi = strtok(frase, " ");
while(divi != NULL) {
printf("%s\n", divi);
divi = strtok(NULL, " ");
}
Para inverter, não usamos essa biblioteca, mas um algoritmo, como podemos ver:
char frase[20] = "Isso é uma string";
char invert[20];
int tam = strlen(frase) - 1;
int j = 0;
for(int i = tam; i >= 0; i--) {
invert[j] = frase[i];
j++;
}
invert[j] = '\0'; // Finaliza string
printf("%s\n", invert);
E para eliminar espaços excessivos de uma string, implementamos essa função simples:
char* trim(char *s) {
int i;
while(isspace(*s)) s++;
for(i = strlen(s) - 1; isspace(s[i]); i--);
s[i + 1] = '\0';
return s;
}
E usamos assim:
char frase[20] = "Isso é uma string";
printf("%s\n", trim(frase));
Podemos criar funções com o toupper() para transformar o texto em maiúscula, podemos fazer o mesmo com minúsculas usando tolower(), assim:
// Inclua string.h e ctype.h
char* maiuscula(char* texto);
char* minuscula(char* texto);
int main() {
setlocale(LC_ALL, "portuguese");
char *frase = "Uma Frase";
char *maius, *minus;
printf("%s\n", frase);
maius = maiuscula(frase);
printf("%s\n", maius);
minus = minuscula(frase);
printf("%s\n", minus);
return 0;
}
char* maiuscula(char* texto) {
unsigned long int tam = strlen(texto);
char aux[tam];
for(int i = 0; i < tam; i++) {
aux[i] = toupper(texto[i]);
}
aux[tam] = '\0';
texto = aux;
return texto;
}
char* minuscula(char* texto) {
unsigned long int tam = strlen(texto);
char aux[tam];
for(int i = 0; i < tam; i++) {
aux[i] = tolower(texto[i]);
}
aux[tam] = '\0';
texto = aux;
return texto;
}