Estrutura de Dados - Pilha
- 4 mins Descrição
Uma Pilha é uma coleção ordenada de itens que obedece ao LIFO (Last In First Out). A adição ou remoção de itens ocorre na mesma extremidade. O final é conhecido como topo e o oposto de base. Os elementos mais recentes ficam próximos ao topo, e os antigos próximos a base.
Um Exemplo de pilha na vida real é uma “Pilha de Livros”.
Exemplos
Pilha com Arrays
class Stack {
public items: number[];
constructor() {
this.items = [];
}
push(element: number[]) {
this.items.push(...element);
}
pop() {
return this.items.pop();
}
peek() {
const length = this.items.length;
return this.items[length - 1];
}
isEmpty() {
return this.items.length === 0;
}
size() {
return this.items.length;
}
clear() {
this.items = [];
}
}
Pilha com Objetos
class Stack {
public items: { [key: number]: number };
private count: number;
constructor() {
this.count = 0;
this.items = {};
}
push(element: number) {
this.items[this.count] = element;
this.count++;
}
pop() {
if (this.isEmpty()) {
return undefined;
}
this.count--;
const value = this.items[this.count];
delete this.items[this.count];
return value;
}
peek() {
if (this.isEmpty()) {
return undefined;
}
const value = this.items[this.count - 1];
return value;
}
toString() {
if (this.isEmpty()) {
return '';
}
let objString = `${this.items[0]}`;
for (let i = 1; i < this.count; i++) {
objString = `${objString},${this.items[i]}`;
}
return objString;
}
size() {
return this.count;
}
isEmpty() {
return this.count === 0;
}
clear() {
this.items = {};
this.count = 0;
}
}
Exercícios
Decimal para Binário
function decimalToBinary(decNumber: number): string {
const stack = new Stack();
let binaryString = '';
let number = decNumber;
while (number > 0) {
stack.push(Math.floor(number % 2));
number = Math.floor(number / 2);
}
while (!stack.isEmpty()) {
binaryString += stack.pop().toString();
}
return binaryString;
}
Converter Bases
function baseConverter(decNumber: number, base: number): string {
const stack = new Stack();
let binaryString = '';
let number = decNumber;
const digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';
if (!(base >= 2 && base <= 36)) {
return '';
}
while (number > 0) {
stack.push(Math.floor(number % base));
number = Math.floor(number / base);
}
while (!stack.isEmpty()) {
binaryString += digits[stack.pop()];
}
return binaryString;
}