stak datastruktur er en lineær datastruktur der følger LIFO-princippet (Last In First Out). , så det sidst indsatte element er det første, der poppes ud. I denne artikel vil vi dække alt det grundlæggende i Stack, Operations on Stack, dets implementering, fordele, ulemper, som vil hjælpe dig med at løse alle problemer baseret på Stack.
Indholdsfortegnelse
- Hvad er stakdatastruktur?
- Grundlæggende handlinger på stakdatastruktur
- Kompleksitetsanalyse af operationer på stakdatastruktur
- Fordele ved stak datastruktur
- Ulemper ved stak datastruktur
- Anvendelser af stak datastruktur
Hvad er stakdatastruktur?
Stak er en lineær datastruktur baseret på LIFO (Last In First Out) princippet hvor indsættelse af et nyt element og fjernelse af et eksisterende element sker i samme ende repræsenteret som top af stakken.
For at implementere stakken er det nødvendigt at vedligeholde markøren til toppen af stakken , som er det sidste element, der skal indsættes pga vi kan kun få adgang til elementerne på toppen af stakken.
Repræsentation af stakdatastruktur:
Stack følger LIFO (Last In First Out) princippet, så det element, der skubbes sidst, poppes først.
Stabel i fast størrelse : Som navnet antyder, har en stabel med fast størrelse en fast størrelse og kan ikke vokse eller krympe dynamisk. Hvis stakken er fuld, og der gøres et forsøg på at tilføje et element til den, opstår der en overløbsfejl. Hvis stakken er tom, og der gøres et forsøg på at fjerne et element fra den, opstår der en underløbsfejl.
Grundlæggende handlinger på stak Datastruktur :
For at lave manipulationer i en stak, er der visse operationer, som vi får tilsendt.
læse fra csv java
- skubbe() at indsætte et element i stakken
- pop() at fjerne et element fra stakken
- top() Returnerer det øverste element i stakken.
- er tom() returnerer sand, hvis stakken er tom ellers falsk.
- er fuld() returnerer sand, hvis stakken er fuld ellers falsk.
Algoritme for push-operation:
- Før vi skubber elementet til stakken, tjekker vi om stakken er fuld .
- Hvis stakken er fuld (øverst == kapacitet-1) , derefter Stack Overflows og vi kan ikke indsætte elementet i stakken.
- Ellers øger vi værdien af top med 1 (øverst = øverst + 1) og den nye værdi indsættes kl topplacering .
- Elementerne kan skubbes ind i stakken, indtil vi når kapacitet af stakken.
Algoritme for pop-operation:
- Før vi springer elementet fra stakken, tjekker vi om stakken er tom .
- Hvis stakken er tom (øverst == -1), så Stakunderløb og vi kan ikke fjerne noget element fra stakken.
- Ellers gemmer vi værdien øverst, sænker værdien af top med 1 (øverst = øverst – 1) og returner den gemte topværdi.
Algoritme for topdrift:
- Inden vi returnerer det øverste element fra stakken, tjekker vi om stakken er tom.
- Hvis stakken er tom (øverst == -1), udskriver vi simpelthen Stakken er tom.
- Ellers returnerer vi elementet gemt kl indeks = top .
Algoritme for isEmpty Operation :
- Tjek for værdien af top i stakken.
- Hvis (øverst == -1) , så er stakken tom så vend tilbage rigtigt .
- Ellers er stakken ikke tom, så vend tilbage falsk .
Algoritme for isFull Operation:
- Tjek for værdien af top i stakken.
- Hvis (øverst == kapacitet-1), så er stakken fuld så vend tilbage rigtigt .
- Ellers er stakken ikke fuld, så vend tilbage falsk .
Implementering af Stack Datastruktur :
De grundlæggende handlinger, der kan udføres på en stak, inkluderer push, pop og kig. Der er to måder at implementere en stak –
- Brug af Array
- Brug af linket liste
I en array-baseret implementering implementeres push-operationen ved at øge indekset for det øverste element og gemme det nye element ved det indeks. Pop-operationen implementeres ved at returnere værdien, der er gemt ved det øverste indeks og derefter dekrementere indekset for det øverste element.
I en linket listebaseret implementering implementeres push-operationen ved at skabe en ny node med det nye element og sætte den næste pointer for den aktuelle topknude til den nye node. Pop-operationen implementeres ved at sætte den næste pointer for den aktuelle topknude til den næste node og returnere værdien af den aktuelle topknude.
/* C++ program til at implementere grundlæggende stak operationer */ #omfatte #omfatte ved brug af navneområde std; #define MAX 1000 klasse Stak { int top; offentlig: int -en[MAKS]; // Maksimal størrelse af stak Stak() { top = -1; } bool skubbe(int x); int pop(); int kig(); bool er tom(); }; bool Stack::skub(int x) { hvis (top >= (MAKS - 1)) { cout << ' stack='' overløb'<='' span=''>; Vend tilbage falsk; } andet { -en[++top] = x; cout << x << ' skubbet ind i stakken
'; Vend tilbage rigtigt; } } int Stack::pop() { hvis (top < 0) { cout << 'Stack Underflow'; Vend tilbage 0; } andet { int x = -en[top--]; Vend tilbage x; } } int Stack::kig() { hvis (top < 0) { cout << 'Stakken er tom'; Vend tilbage 0; } andet { int x = -en[top]; Vend tilbage x; } } bool Stack::er Empty() { Vend tilbage (top < 0); } // Driverprogram til at teste ovenstående funktioner int vigtigste() { klasse Stak s; s.skubbe(10); s.skubbe(tyve); s.skubbe(30); cout << s.pop() << ' Sprang fra stakken
'; //print det øverste element i stakken efter popning cout << 'Topelement er:' << s.kig() << endl; //udskriv alle elementer i stakken: cout <<'Elementer til stede i stakken:'; mens(!s.er tom()) { // print topelement i stak cout << s.kig() <<' '; // fjern det øverste element i stakken s.pop(); } Vend tilbage 0; } //Koden er ændret af Vinay PandeyC // C program for array implementation of stack #include #include #include // A structure to represent a stack struct Stack { int top; unsigned capacity; int* array; }; // function to create a stack of given capacity. It initializes size of // stack as 0 struct Stack* createStack(unsigned capacity) { struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack)); stack->kapacitet = kapacitet; stak->top = -1; stack->array = (int*)malloc(stack->kapacitet * sizeof(int)); retur stak; } // Stakken er fuld, når toppen er lig med det sidste indeks int isFull(struct Stack* stack) { return stack->top == stack->capacity - 1; } // Stack er tom, når top er lig med -1 int isEmpty(struct Stack* stack) { return stack->top == -1; } // Funktion til at tilføje et element til stakken. Det øger toppen med 1 void push(struct Stack* stack, int item) { if (isFull(stack)) return; stack->array[++stack->top] = element; printf('%d skubbet til stak
', element); } // Funktion til at fjerne et element fra stakken. Det formindsker toppen med 1 int pop(struct Stack* stack) { if (isEmpty(stack)) return INT_MIN; returner stak->array[stak->top--]; } // Funktion til at returnere toppen fra stakken uden at fjerne den int peek(struct Stack* stack) { if (isEmpty(stack)) return INT_MIN; returner stak->array[stak->top]; } // Driverprogram til at teste ovenstående funktioner int main() { struct Stack* stack = createStack(100); push(stak, 10); push(stak, 20); push(stak, 30); printf('%d poppet fra stak
', pop(stak)); retur 0; }> Java /* Java program to implement basic stack operations */ class Stack { static final int MAX = 1000; int top; int a[] = new int[MAX]; // Maximum size of Stack boolean isEmpty() { return (top < 0); } Stack() { top = -1; } boolean push(int x) { if (top>= (MAX - 1)) { System.out.println('Stack Overflow'); returnere falsk; } andet { a[++top] = x; System.out.println(x + ' skubbet ind i stakken'); returnere sandt; } } int pop() { if (top< 0) { System.out.println('Stack Underflow'); return 0; } else { int x = a[top--]; return x; } } int peek() { if (top < 0) { System.out.println('Stack Underflow'); return 0; } else { int x = a[top]; return x; } } void print(){ for(int i = top;i>-1;i--){ System.out.print(' '+ a[i]); } } } // Driverkodeklasse Main { public static void main(String args[]) { Stack s = new Stack(); s.push(10); s. push(20); s.push(30); System.out.println(s.pop() + ' Poppet fra stak'); System.out.println('Topelement er :' + s.peek()); System.out.print('Elementer til stede i stakken :'); s.print(); } } //Denne kode er ændret af Vinay Pandey> Python # Python program for implementation of stack # import maxsize from sys module # Used to return -infinite when stack is empty from sys import maxsize # Function to create a stack. It initializes size of stack as 0 def createStack(): stack = [] return stack # Stack is empty when stack size is 0 def isEmpty(stack): return len(stack) == 0 # Function to add an item to stack. It increases size by 1 def push(stack, item): stack.append(item) print(item + ' pushed to stack ') # Function to remove an item from stack. It decreases size by 1 def pop(stack): if (isEmpty(stack)): return str(-maxsize -1) # return minus infinite return stack.pop() # Function to return the top from stack without removing it def peek(stack): if (isEmpty(stack)): return str(-maxsize -1) # return minus infinite return stack[len(stack) - 1] # Driver program to test above functions stack = createStack() push(stack, str(10)) push(stack, str(20)) push(stack, str(30)) print(pop(stack) + ' popped from stack')>
C# // C# program to implement basic stack // operations using System; namespace ImplementStack { class Stack { private int[] ele; private int top; private int max; public Stack(int size) { ele = new int[size]; // Maximum size of Stack top = -1; max = size; } public void push(int item) { if (top == max - 1) { Console.WriteLine('Stack Overflow'); return; } else { ele[++top] = item; } } public int pop() { if (top == -1) { Console.WriteLine('Stack is Empty'); return -1; } else { Console.WriteLine('{0} popped from stack ', ele[top]); return ele[top--]; } } public int peek() { if (top == -1) { Console.WriteLine('Stack is Empty'); return -1; } else { Console.WriteLine('{0} popped from stack ', ele[top]); return ele[top]; } } public void printStack() { if (top == -1) { Console.WriteLine('Stack is Empty'); return; } else { for (int i = 0; i <= top; i++) { Console.WriteLine('{0} pushed into stack', ele[i]); } } } } // Driver program to test above functions class Program { static void Main() { Stack p = new Stack(5); p.push(10); p.push(20); p.push(30); p.printStack(); p.pop(); } } }> Javascript /* javascript program to implement basic stack operations */ var t = -1; var MAX = 1000; var a = Array(MAX).fill(0); // Maximum size of Stack function isEmpty() { return (t < 0); } function push(x) { if (t>= (MAX - 1)) { console.log('Stack Overflow'); returnere falsk; } andet {t+=1; a[t] = x; console.log(x + ' skubbet ind i stakken '); returnere sandt; } } funktion pop() { if (t< 0) { console.log('Stack Underflow'); return 0; } else { var x = a[t]; t-=1; return x; } } function peek() { if (t < 0) { console.log('Stack Underflow'); return 0; } else { var x = a[t]; return x; } } function print() { for (i = t; i>-1; i--) { console.log(' ' + a[i]); } } push(10); push(20); push(30); console.log(pop() + ' Sprunget fra stak'); console.log(' Øverste element er :' + peek()); console.log(' Elementer til stede i stakken: '); Print(); // Denne kode er bidraget af Rajput-Ji>
Produktion 10 pushed into stack 20 pushed into stack 30 pushed into stack 30 Popped from stack Top element is : 20 Elements present in stack : 20 10>
Fordele ved Array-implementering:
- Let at implementere.
- Hukommelsen gemmes, da pointere ikke er involveret.
Ulemper ved Array-implementering:
- Det er ikke dynamisk, dvs. det vokser og krymper ikke afhængigt af behov under kørsel. [Men i tilfælde af arrays i dynamisk størrelse som vektor i C++, liste i Python, ArrayList i Java, kan stakke også vokse og krympe med array-implementering].
- Den samlede størrelse af stakken skal være defineret på forhånd.
// C program for array implementation of stack #include #include #include // A structure to represent a stack struct Stack { int top; unsigned capacity; int* array; }; // function to create a stack of given capacity. It initializes size of // stack as 0 struct Stack* createStack(unsigned capacity) { struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack)); stack->kapacitet = kapacitet; stak->top = -1; stack->array = (int*)malloc(stack->kapacitet * sizeof(int)); retur stak; } // Stakken er fuld, når toppen er lig med det sidste indeks int isFull(struct Stack* stack) { return stack->top == stack->capacity - 1; } // Stack er tom, når top er lig med -1 int isEmpty(struct Stack* stack) { return stack->top == -1; } // Funktion til at tilføje et element til stakken. Det øger toppen med 1 void push(struct Stack* stack, int item) { if (isFull(stack)) return; stack->array[++stack->top] = element; printf('%d skubbet til stak
', element); } // Funktion til at fjerne et element fra stakken. Det formindsker toppen med 1 int pop(struct Stack* stack) { if (isEmpty(stack)) return INT_MIN; returner stak->array[stak->top--]; } // Funktion til at returnere toppen fra stakken uden at fjerne den int peek(struct Stack* stack) { if (isEmpty(stack)) return INT_MIN; returner stak->array[stak->top]; } // Driverprogram til at teste ovenstående funktioner int main() { struct Stack* stack = createStack(100); push(stak, 10); push(stak, 20); push(stak, 30); printf('%d poppet fra stak
', pop(stak)); retur 0; }> /* Java program to implement basic stack operations */ class Stack { static final int MAX = 1000; int top; int a[] = new int[MAX]; // Maximum size of Stack boolean isEmpty() { return (top < 0); } Stack() { top = -1; } boolean push(int x) { if (top>= (MAX - 1)) { System.out.println('Stack Overflow'); returnere falsk; } andet { a[++top] = x; System.out.println(x + ' skubbet ind i stakken'); returnere sandt; } } int pop() { if (top< 0) { System.out.println('Stack Underflow'); return 0; } else { int x = a[top--]; return x; } } int peek() { if (top < 0) { System.out.println('Stack Underflow'); return 0; } else { int x = a[top]; return x; } } void print(){ for(int i = top;i>-1;i--){ System.out.print(' '+ a[i]); } } } // Driverkodeklasse Main { public static void main(String args[]) { Stack s = new Stack(); s.push(10); s. push(20); s.push(30); System.out.println(s.pop() + ' Poppet fra stak'); System.out.println('Topelement er :' + s.peek()); System.out.print('Elementer til stede i stakken :'); s.print(); } } //Denne kode er ændret af Vinay Pandey> # Python program for implementation of stack # import maxsize from sys module # Used to return -infinite when stack is empty from sys import maxsize # Function to create a stack. It initializes size of stack as 0 def createStack(): stack = [] return stack # Stack is empty when stack size is 0 def isEmpty(stack): return len(stack) == 0 # Function to add an item to stack. It increases size by 1 def push(stack, item): stack.append(item) print(item + ' pushed to stack ') # Function to remove an item from stack. It decreases size by 1 def pop(stack): if (isEmpty(stack)): return str(-maxsize -1) # return minus infinite return stack.pop() # Function to return the top from stack without removing it def peek(stack): if (isEmpty(stack)): return str(-maxsize -1) # return minus infinite return stack[len(stack) - 1] # Driver program to test above functions stack = createStack() push(stack, str(10)) push(stack, str(20)) push(stack, str(30)) print(pop(stack) + ' popped from stack')>
// C# program to implement basic stack // operations using System; namespace ImplementStack { class Stack { private int[] ele; private int top; private int max; public Stack(int size) { ele = new int[size]; // Maximum size of Stack top = -1; max = size; } public void push(int item) { if (top == max - 1) { Console.WriteLine('Stack Overflow'); return; } else { ele[++top] = item; } } public int pop() { if (top == -1) { Console.WriteLine('Stack is Empty'); return -1; } else { Console.WriteLine('{0} popped from stack ', ele[top]); return ele[top--]; } } public int peek() { if (top == -1) { Console.WriteLine('Stack is Empty'); return -1; } else { Console.WriteLine('{0} popped from stack ', ele[top]); return ele[top]; } } public void printStack() { if (top == -1) { Console.WriteLine('Stack is Empty'); return; } else { for (int i = 0; i <= top; i++) { Console.WriteLine('{0} pushed into stack', ele[i]); } } } } // Driver program to test above functions class Program { static void Main() { Stack p = new Stack(5); p.push(10); p.push(20); p.push(30); p.printStack(); p.pop(); } } }> /* javascript program to implement basic stack operations */ var t = -1; var MAX = 1000; var a = Array(MAX).fill(0); // Maximum size of Stack function isEmpty() { return (t < 0); } function push(x) { if (t>= (MAX - 1)) { console.log('Stack Overflow'); returnere falsk; } andet {t+=1; a[t] = x; console.log(x + ' skubbet ind i stakken '); returnere sandt; } } funktion pop() { if (t< 0) { console.log('Stack Underflow'); return 0; } else { var x = a[t]; t-=1; return x; } } function peek() { if (t < 0) { console.log('Stack Underflow'); return 0; } else { var x = a[t]; return x; } } function print() { for (i = t; i>-1; i--) { console.log(' ' + a[i]); } } push(10); push(20); push(30); console.log(pop() + ' Sprunget fra stak'); console.log(' Øverste element er :' + peek()); console.log(' Elementer til stede i stakken: '); Print(); // Denne kode er bidraget af Rajput-Ji> // C++ program til linked list implementering af stak #omfatte ved brug af navneområde std; // En struktur til at repræsentere en stak klasse StackNode { offentlig: int data; StackNode* Næste; }; StackNode* nyNode(int data) { StackNode* stackNode = ny StackNode(); stackNode->data = data; stackNode->Næste = NUL; Vend tilbage stackNode; } int er tom(StackNode* rod) { Vend tilbage !rod; } ugyldig skubbe(StackNode** rod, int data) { StackNode* stackNode = nyNode(data); stackNode->Næste = *rod; *rod = stackNode; cout << data << ' pushed='' til ='' stak<='' span=''>
'; } int pop(StackNode** rod) { hvis (er tom(*rod)) Vend tilbage INT_MIN; StackNode* Midlertidig = *rod; *rod = (*rod)->Næste; int poppede = Midlertidig->data; gratis(Midlertidig); Vend tilbage poppede; } int kig(StackNode* rod) { hvis (er tom(rod)) Vend tilbage INT_MIN; Vend tilbage rod->data; } // Driverkode int vigtigste() { StackNode* rod = NUL; skubbe(&rod, 10); skubbe(&rod, tyve); skubbe(&rod, 30); cout << pop(&rod) << ' sprang fra stakken
'; cout << 'Topelement er' << kig(rod) << endl; cout <<'Elementer til stede i stakken:'; //udskriv alle elementer i stakken: mens(!er tom(rod)) { // print topelement i stak cout << kig(rod) <<' '; // fjern det øverste element i stakken pop(&rod); } Vend tilbage 0; } // Denne kode er bidraget af rathbhupendraC // C program for linked list implementation of stack #include #include #include // A structure to represent a stack struct StackNode { int data; struct StackNode* next; }; struct StackNode* newNode(int data) { struct StackNode* stackNode = (struct StackNode*) malloc(sizeof(struct StackNode)); stackNode->data = data; stackNode->next = NULL; returner stackNode; } int isEmpty(struct StackNode* root) { return !root; } void push(struct StackNode** root, int data) { struct StackNode* stackNode = newNode(data); stackNode->next = *root; *root = stackNode; printf('%d skubbet til stak
', data); } int pop(struct StackNode** root) { if (erEmpty(*root)) returner INT_MIN; struct StackNode* temp = *rod; *rod = (*rod)->næste; int popped = temp->data; gratis(temp); retur poppet; } int peek(struct StackNode* root) { if (erEmpty(root)) return INT_MIN; returnere root->data; } int main() { struct StackNode* root = NULL; push(&root, 10); push(&root, 20); push(&root, 30); printf('%d poppet fra stak
', pop(&root)); printf('Topelement er %d
', kig(rod)); retur 0; }> Java // Java Code for Linked List Implementation public class StackAsLinkedList { StackNode root; static class StackNode { int data; StackNode next; StackNode(int data) { this.data = data; } } public boolean isEmpty() { if (root == null) { return true; } else return false; } public void push(int data) { StackNode newNode = new StackNode(data); if (root == null) { root = newNode; } else { StackNode temp = root; root = newNode; newNode.next = temp; } System.out.println(data + ' pushed to stack'); } public int pop() { int popped = Integer.MIN_VALUE; if (root == null) { System.out.println('Stack is Empty'); } else { popped = root.data; root = root.next; } return popped; } public int peek() { if (root == null) { System.out.println('Stack is empty'); return Integer.MIN_VALUE; } else { return root.data; } } // Driver code public static void main(String[] args) { StackAsLinkedList sll = new StackAsLinkedList(); sll.push(10); sll.push(20); sll.push(30); System.out.println(sll.pop() + ' popped from stack'); System.out.println('Top element is ' + sll.peek()); sll.push(10); sll.push(20); sll.push(30); System.out.println(sll.pop() + ' popped from stack'); System.out.println('Top element is ' + sll.peek()); } }> Python # Python program for linked list implementation of stack # Class to represent a node class StackNode: # Constructor to initialize a node def __init__(self, data): self.data = data self.next = None class Stack: # Constructor to initialize the root of linked list def __init__(self): self.root = None def isEmpty(self): return True if self.root is None else False def push(self, data): newNode = StackNode(data) newNode.next = self.root self.root = newNode print ('% d pushed to stack' % (data)) def pop(self): if (self.isEmpty()): return float('-inf') temp = self.root self.root = self.root.next popped = temp.data return popped def peek(self): if self.isEmpty(): return float('-inf') return self.root.data # Driver code stack = Stack() stack.push(10) stack.push(20) stack.push(30) print ('% d popped from stack' % (stack.pop())) print ('Top element is % d ' % (stack.peek())) # This code is contributed by Nikhil Kumar Singh(nickzuck_007)> C# // C# Code for Linked List Implementation using System; public class StackAsLinkedList { StackNode root; public class StackNode { public int data; public StackNode next; public StackNode(int data) { this.data = data; } } public bool isEmpty() { if (root == null) { return true; } else return false; } public void push(int data) { StackNode newNode = new StackNode(data); if (root == null) { root = newNode; } else { StackNode temp = root; root = newNode; newNode.next = temp; } Console.WriteLine(data + ' pushed to stack'); } public int pop() { int popped = int.MinValue; if (root == null) { Console.WriteLine('Stack is Empty'); } else { popped = root.data; root = root.next; } return popped; } public int peek() { if (root == null) { Console.WriteLine('Stack is empty'); return int.MinValue; } else { return root.data; } } // Driver code public static void Main(String[] args) { StackAsLinkedList sll = new StackAsLinkedList(); sll.push(10); sll.push(20); sll.push(30); Console.WriteLine(sll.pop() + ' popped from stack'); Console.WriteLine('Top element is ' + sll.peek()); } } /* This code contributed by PrinciRaj1992 */> Javascript >
Produktion 10 pushed to stack 20 pushed to stack 30 pushed to stack 30 popped from stack Top element is 20 Elements present in stack : 20 10>
Fordele ved implementering af linkede lister:
- Den linkede listeimplementering af en stak kan vokse og krympe i overensstemmelse med behovene under kørsel.
- Det bruges i mange virtuelle maskiner som JVM.
Ulemper ved implementering af linkede lister:
- Kræver ekstra hukommelse på grund af involvering af pointere.
- Tilfældig adgang er ikke mulig i stakken.
// C program for linked list implementation of stack #include #include #include // A structure to represent a stack struct StackNode { int data; struct StackNode* next; }; struct StackNode* newNode(int data) { struct StackNode* stackNode = (struct StackNode*) malloc(sizeof(struct StackNode)); stackNode->data = data; stackNode->next = NULL; returner stackNode; } int isEmpty(struct StackNode* root) { return !root; } void push(struct StackNode** root, int data) { struct StackNode* stackNode = newNode(data); stackNode->next = *root; *root = stackNode; printf('%d skubbet til stak
', data); } int pop(struct StackNode** root) { if (erEmpty(*root)) returner INT_MIN; struct StackNode* temp = *rod; *rod = (*rod)->næste; int popped = temp->data; gratis(temp); retur poppet; } int peek(struct StackNode* root) { if (erEmpty(root)) return INT_MIN; returnere root->data; } int main() { struct StackNode* root = NULL; push(&root, 10); push(&root, 20); push(&root, 30); printf('%d poppet fra stak
', pop(&root)); printf('Topelement er %d
', kig(rod)); retur 0; }> // Java Code for Linked List Implementation public class StackAsLinkedList { StackNode root; static class StackNode { int data; StackNode next; StackNode(int data) { this.data = data; } } public boolean isEmpty() { if (root == null) { return true; } else return false; } public void push(int data) { StackNode newNode = new StackNode(data); if (root == null) { root = newNode; } else { StackNode temp = root; root = newNode; newNode.next = temp; } System.out.println(data + ' pushed to stack'); } public int pop() { int popped = Integer.MIN_VALUE; if (root == null) { System.out.println('Stack is Empty'); } else { popped = root.data; root = root.next; } return popped; } public int peek() { if (root == null) { System.out.println('Stack is empty'); return Integer.MIN_VALUE; } else { return root.data; } } // Driver code public static void main(String[] args) { StackAsLinkedList sll = new StackAsLinkedList(); sll.push(10); sll.push(20); sll.push(30); System.out.println(sll.pop() + ' popped from stack'); System.out.println('Top element is ' + sll.peek()); sll.push(10); sll.push(20); sll.push(30); System.out.println(sll.pop() + ' popped from stack'); System.out.println('Top element is ' + sll.peek()); } }> # Python program for linked list implementation of stack # Class to represent a node class StackNode: # Constructor to initialize a node def __init__(self, data): self.data = data self.next = None class Stack: # Constructor to initialize the root of linked list def __init__(self): self.root = None def isEmpty(self): return True if self.root is None else False def push(self, data): newNode = StackNode(data) newNode.next = self.root self.root = newNode print ('% d pushed to stack' % (data)) def pop(self): if (self.isEmpty()): return float('-inf') temp = self.root self.root = self.root.next popped = temp.data return popped def peek(self): if self.isEmpty(): return float('-inf') return self.root.data # Driver code stack = Stack() stack.push(10) stack.push(20) stack.push(30) print ('% d popped from stack' % (stack.pop())) print ('Top element is % d ' % (stack.peek())) # This code is contributed by Nikhil Kumar Singh(nickzuck_007)> // C# Code for Linked List Implementation using System; public class StackAsLinkedList { StackNode root; public class StackNode { public int data; public StackNode next; public StackNode(int data) { this.data = data; } } public bool isEmpty() { if (root == null) { return true; } else return false; } public void push(int data) { StackNode newNode = new StackNode(data); if (root == null) { root = newNode; } else { StackNode temp = root; root = newNode; newNode.next = temp; } Console.WriteLine(data + ' pushed to stack'); } public int pop() { int popped = int.MinValue; if (root == null) { Console.WriteLine('Stack is Empty'); } else { popped = root.data; root = root.next; } return popped; } public int peek() { if (root == null) { Console.WriteLine('Stack is empty'); return int.MinValue; } else { return root.data; } } // Driver code public static void Main(String[] args) { StackAsLinkedList sll = new StackAsLinkedList(); sll.push(10); sll.push(20); sll.push(30); Console.WriteLine(sll.pop() + ' popped from stack'); Console.WriteLine('Top element is ' + sll.peek()); } } /* This code contributed by PrinciRaj1992 */> >
Kompleksitetsanalyse af operationer på stakdatastruktur:
| Operationer | Tidskompleksitet | Rumkompleksitet |
|---|---|---|
| skubbe() | O(1) | O(1) |
| pop() | O(1) | O(1) |
top() eller tisse k() | O(1) | O(1) |
| er tom() | O(1) | O(1) java forekomst af |
| er fuld() | O(1) | O(1) |
Fordele ved Stack Datastruktur :
- Enkelhed: Stabler er en enkel og letforståelig datastruktur, hvilket gør dem velegnede til en lang række applikationer.
- Effektivitet: Push og pop operationer på en stak kan udføres i konstant tid (O(1)) giver effektiv adgang til data.
- Sidst ind, først ud (LIFO): Stabler følger LIFO-princippet, hvilket sikrer, at det sidste element, der tilføjes til stakken, er det første, der fjernes. Denne adfærd er nyttig i mange scenarier, såsom funktionskald og udtryksevaluering.
- Begrænset hukommelsesforbrug: Stabler behøver kun at gemme de elementer, der er blevet skubbet på dem, hvilket gør dem hukommelseseffektive sammenlignet med andre datastrukturer.
Ulemper ved Stack Datastruktur :
- Begrænset adgang: Elementer i en stak kan kun tilgås fra toppen, hvilket gør det vanskeligt at hente eller ændre elementer i midten af stakken.
- Potentiale for overløb: Hvis der skubbes flere elementer på en stak, end den kan holde, vil der opstå en overløbsfejl, hvilket resulterer i tab af data.
- Ikke egnet til tilfældig adgang: Stak s tillader ikke tilfældig adgang til elementer, hvilket gør dem uegnede til applikationer, hvor elementer skal tilgås i en bestemt rækkefølge.
- Begrænset kapacitet: Stabler har en fast kapacitet, hvilket kan være en begrænsning, hvis antallet af elementer, der skal opbevares, er ukendt eller meget varierende.
Anvendelser af stakdatastruktur:
- Infix til Postfix /Prefikskonvertering
- Fortryd-fortryd funktioner mange steder som redaktører, photoshop.
- Frem og tilbage funktioner i webbrowsere
- I hukommelsesstyring bruger enhver moderne computer en stak som den primære styring til et kørende formål. Hvert program, der kører i et computersystem, har sine egne hukommelsestildelinger.
- Stack hjælper også med at implementere funktionskald på computere. Den sidst kaldte funktion fuldføres altid først.
Relaterede artikler:
- Implementer en stak ved hjælp af en enkelt linket liste
- Grundlæggende operationer i stakdatastruktur med implementeringer
- Top 50 problemer om stakdatastruktur spurgt i SDE-interviews
- Anvendelser, fordele og ulemper ved Stack
- Stak til konkurrencedygtig programmering