Stack datastruktur är en linjär datastruktur som följer LIFO-principen (Last In First Out). , så det sista elementet som infogas är det första som tas ut. I den här artikeln kommer vi att täcka alla grunderna i Stack, Operations on Stack, dess implementering, fördelar, nackdelar som hjälper dig att lösa alla problem baserade på Stack.

Innehållsförteckning

• Vad är Stack Data Structure?
• Grundläggande funktioner för stackdatastruktur
• isEmpty Operation i Stack Data Structure
• Implementering av stackdatastruktur med länkad lista
• Komplexitetsanalys av operationer på stackdatastruktur
• Fördelar med Stack Data Structure
• Nackdelar med Stack Data Structure
• Tillämpningar av stackdatastruktur

Vad är Stack Data Structure?

Stack är en linjär datastruktur baserat på LIFO-principen (Last In First Out). där införandet av ett nytt element och avlägsnande av ett befintligt element sker i samma ände som representeras som topp av stapeln.

För att implementera stacken krävs det att underhålla pekaren till toppen av stapeln , vilket är det sista elementet som infogas eftersom vi kan bara komma åt elementen på toppen av stapeln.

Representation av stackdatastruktur:

Stack följer LIFO-principen (Last In First Out) så att elementet som trycks sist trycks först.

Stack med fast storlek : Som namnet antyder har en stack med fast storlek en fast storlek och kan inte växa eller krympa dynamiskt. Om stacken är full och ett försök görs att lägga till ett element till den, uppstår ett spillfel. Om stacken är tom och ett försök görs att ta bort ett element från den, uppstår ett underflödesfel.

Dynamisk storlek Stack : En stack med dynamisk storlek kan växa eller krympa dynamiskt. När högen är full, ökar den automatiskt sin storlek för att rymma det nya elementet, och när högen är tom, minskar den sin storlek. Denna typ av stack implementeras med hjälp av en länkad lista, eftersom det gör det enkelt att ändra storlek på stacken.

Grundläggande operationer på Stack Datastruktur :

För att göra manipulationer i en stack finns det vissa operationer som tillhandahålls oss.

java arkitektur

• skjuta på() för att infoga ett element i stapeln
• pop() för att ta bort ett element från stapeln
• topp() Returnerar det översta elementet i stacken.
• är tom() returnerar sant om stacken är tom annars false.
• är full() returnerar sant om stacken är full annars falskt.

Algoritm för push-operation:

• Innan vi skjuter elementet till stapeln kontrollerar vi om stapeln är full .
• Om stapeln är full (överst == kapacitet-1) , då Stack overflows och vi kan inte infoga elementet i stacken.
• Annars ökar vi värdet på topp med 1 (överst = topp + 1) och det nya värdet infogas vid topposition .
• Elementen kan tryckas in i stapeln tills vi når kapacitet av stapeln.

Algoritm för popoperation:

• Innan vi tar upp elementet från stapeln kontrollerar vi om stapeln är det tömma .
• Om stacken är tom (överst == -1), då Stack Underflows och vi kan inte ta bort något element från stacken.
• Annars lagrar vi värdet överst, minskar värdet på topp med 1 (överst = topp – 1) och returnera det lagrade högsta värdet.

Algoritm för toppdrift:

• Innan vi returnerar det översta elementet från stapeln kontrollerar vi om stapeln är tom.
• Om stacken är tom (överst == -1), skriver vi helt enkelt ut Stacken är tom.
• Annars returnerar vi elementet lagrat på index = topp .

Algoritm för isEmpty Operation :

• Kontrollera värdet på topp i stack.
• Om (överst == -1) , då är stacken tömma så återvänd Sann .
• Annars är stapeln inte tom så återvänd falsk .

Algoritm för isFull Operation:

• Kontrollera värdet på topp i stack.
• Om (överst == kapacitet-1), då är stacken full så återvänd Sann .
• Annars är stapeln inte full så återvänd falsk .

Implementering av Stack Datastruktur :

De grundläggande operationerna som kan utföras på en stack inkluderar push, pop och peek. Det finns två sätt att implementera en stack –

• Använder Array
• Använder länkad lista

I en array-baserad implementering implementeras push-operationen genom att öka indexet för toppelementet och lagra det nya elementet vid det indexet. Pop-operationen implementeras genom att returnera värdet som lagrats i det översta indexet och sedan minska indexet för det översta elementet.

I en länkad listbaserad implementering implementeras push-operationen genom att skapa en ny nod med det nya elementet och sätta nästa pekare för den nuvarande toppnoden till den nya noden. Popoperationen implementeras genom att sätta nästa pekare för den aktuella toppnoden till nästa nod och returnera värdet för den aktuella toppnoden.

/* C++-program för att implementera grundläggande stack operationer */ #omfatta #omfatta använder sig av namnutrymme std; #define MAX 1000 klass Stack { int topp; offentlig: int a[MAX]; // Maximal storlek på Stack Stack() { topp = -1; } bool skjuta på(int x); int pop(); int titt(); bool är tom(); }; bool Stack::push(int x) { om (topp >= (MAX - 1)) { cout << ' stack='' overflow'<='' span=''>; lämna tillbaka falsk; } annan { a[++topp] = x; cout << x << ' tryckte in i högen '; lämna tillbaka Sann; } } int Stack::pop() { om (topp < 0) { cout << 'Stack Underflow'; lämna tillbaka 0; } annan { int x = a[topp--]; lämna tillbaka x; } } int Stack::peek() { om (topp < 0) { cout << 'Stacken är tom'; lämna tillbaka 0; } annan { int x = a[topp]; lämna tillbaka x; } } bool Stack::isEmpty() { lämna tillbaka (topp < 0); } // Drivrutinsprogram för att testa ovanstående funktioner int huvud() { klass Stack s; s.skjuta på(10); s.skjuta på(tjugo); s.skjuta på(30); cout << s.pop() << ' Poppade från högen '; //skriv ut det översta elementet i högen efter att ha poppat cout << 'Översta elementet är:' << s.titt() << endl; //skriv ut alla element i stack: cout <<'Element som finns i stack:'; medan(!s.är tom()) { // skriv ut toppelementet i stack cout << s.titt() <<' '; // ta bort toppelementet i stack s.pop(); } lämna tillbaka 0; } //Koden är modifierad av 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;  stack->top = -1;  stack->array = (int*)malloc(stack->capacity * sizeof(int));  returstack; } // Stacken är full när toppen är lika med det sista indexet int isFull(struct Stack* stack) { return stack->top == stack->capacity - 1; } // Stacken är tom när toppen är lika med -1 int isEmpty(struct Stack* stack) { return stack->top == -1; } // Funktion för att lägga till ett objekt i stack. Den ökar toppen med 1 void push(struct Stack* stack, int item) { if (isFull(stack)) return;  stack->array[++stack->top] = objekt;  printf('%d skickas till stack
', objekt); } // Funktion för att ta bort ett objekt från stacken. Den minskar toppen med 1 int pop(struct Stack* stack) { if (isEmpty(stack)) return INT_MIN;  return stack->array[stack->top--]; } // Funktion för att returnera toppen från stack utan att ta bort den int peek(struct Stack* stack) { if (isEmpty(stack)) return INT_MIN;  return stack->array[stack->top]; } // Drivrutinsprogram för att testa ovanstående funktioner int main() { struct Stack* stack = createStack(100);  push(stack, 10);  push(stack, 20);  push(stack, 30);  printf('%d poppade från stack
', pop(stack));  returnera 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');  returnera falskt;  } annat { a[++top] = x;  System.out.println(x + ' inskjuten i stack');  returnera sant;  } } 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]);  } } } // Driver code class 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() + ' Poppade från stack');  System.out.println('Toppelement är :' + s.peek());  System.out.print('Element som finns i stack :');  sprinta();  } } //Denna kod är modifierad av Vinay Pandey>

Pytonorm

# 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');  returnera falskt;  } annat { t+=1;  a[t] = x;    console.log(x + ' inskjuten i stack ');  returnera sant;  } } 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() + ' Poppade från stack');  console.log(' Toppelement är :' + peek());  console.log(' Element som finns i stack: ');  skriva ut(); // Denna kod är bidragit av 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>

Fördelar med Array-implementering:

• Lätt att implementera.
• Minnet sparas eftersom pekare inte är inblandade.

Nackdelar med Array-implementering:

• Den är inte dynamisk, dvs den växer och krymper inte beroende på behov under körning. [Men i fallet med dynamiska arrayer som vektor i C++, lista i Python, ArrayList i Java, kan stackar växa och krympa med arrayimplementering också].
• Den totala storleken på stacken måste definieras i förväg.

// C++-program för länkad listimplementering av stack #omfatta använder sig av namnutrymme std; // En struktur för att representera en stack klass StackNode { offentlig: int data; StackNode* Nästa; }; StackNode* nyNode(int data) { StackNode* stackNode = ny StackNode(); stackNode->data = data; stackNode->Nästa = NULL; lämna tillbaka stackNode; } int är tom(StackNode* rot) { lämna tillbaka !rot; } tomhet skjuta på(StackNode** rot, int data) { StackNode* stackNode = nyNode(data); stackNode->Nästa = *rot; *rot = stackNode; cout << data << ' pushed='' till='' stack<='' span=''> '; } int pop(StackNode** rot) { om (är tom(*rot)) lämna tillbaka INT_MIN; StackNode* temp = *rot; *rot = (*rot)->Nästa; int poppade = temp->data; fri(temp); lämna tillbaka poppade; } int titt(StackNode* rot) { om (är tom(rot)) lämna tillbaka INT_MIN; lämna tillbaka rot->data; } // Förarkod int huvud() { StackNode* rot = NULL; skjuta på(&rot, 10); skjuta på(&rot, tjugo); skjuta på(&rot, 30); cout << pop(&rot) << dök upp från högen '; cout << 'Översta elementet är' << titt(rot) << endl; cout <<'Element som finns i stack:'; //skriv ut alla element i stack: medan(!är tom(rot)) { // skriv ut toppelementet i stack cout << titt(rot) <<' '; // ta bort toppelementet i stack pop(&rot); } lämna tillbaka 0; } // Denna kod är bidragit av 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;  return stackNode; } int isEmpty(struct StackNode* root) { return !root; } void push(struct StackNode** rot, int data) { struct StackNode* stackNode = newNode(data);  stackNode->next = *root;  *root = stackNode;  printf('%d pushad till stack
', data); } int pop(struct StackNode** rot) { if (isEmpty(*root)) return INT_MIN;  struct StackNode* temp = *rot;  *root = (*root)->nästa;  int poppad = temp->data;  gratis(temp);  retur poppade; } int peek(struct StackNode* root) { if (erEmpty(root)) return INT_MIN;  returnera root->data; } int main() { struct StackNode* root = NULL;  push(&root, 10);  push(&root, 20);  push(&root, 30);  printf('%d poppade från stack
', pop(&root));  printf('Översta elementet är %d
', peek(root));  returnera 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());  } }>

Pytonorm

# 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>

Fördelar med implementering av länkad lista:

postorder genomgång av binärt träd

• Den länkade listimplementeringen av en stack kan växa och krympa enligt behoven vid körning.
• Det används i många virtuella maskiner som JVM.

Nackdelar med implementering av länkad lista:

• Kräver extra minne på grund av inblandning av pekare.
• Slumpmässig åtkomst är inte möjlig i stack.

Komplexitetsanalys av operationer på stackdatastruktur:

Fördelar med Stack Datastruktur :

• Enkelhet: Stackar är en enkel och lättförståelig datastruktur, vilket gör dem lämpliga för ett brett spektrum av applikationer.
• Effektivitet: Push och pop operationer på en stack kan utföras i konstant tid (O(1)) ger effektiv tillgång till data.
• Sist in, först ut (LIFO): Staplar följer LIFO-principen, vilket säkerställer att det sista elementet som läggs till stapeln är det första som tas bort. Detta beteende är användbart i många scenarier, som funktionsanrop och uttrycksutvärdering.
• Begränsad minnesanvändning: Stackar behöver bara lagra de element som har tryckts på dem, vilket gör dem minneseffektiva jämfört med andra datastrukturer.

Nackdelar med Stack Datastruktur :

• Begränsad åtkomst: Element i en stack kan endast nås från toppen, vilket gör det svårt att hämta eller ändra element i mitten av stapeln.
• Potential för översvämning: Om fler element skjuts in på en stack än vad den kan hålla, kommer ett spillfel att uppstå, vilket resulterar i förlust av data.
• Inte lämplig för slumpmässig åtkomst: Stack s tillåter inte slumpmässig åtkomst till element, vilket gör dem olämpliga för applikationer där element måste nås i en specifik ordning.
• Begränsad kapacitet: Stackar har en fast kapacitet, vilket kan vara en begränsning om antalet element som behöver lagras är okänt eller mycket varierande.

Tillämpningar av stackdatastruktur:

• Infix till Postfix /Prefixkonvertering
• Gör om-ångra funktioner på många ställen som redigerare, photoshop.
• Framåt- och bakåtfunktioner i webbläsare
• I minneshantering använder alla moderna datorer en stack som den primära hanteringen för ett körande syfte. Varje program som körs i ett datorsystem har sina egna minnesallokeringar.
• Stack hjälper också till att implementera funktionsanrop i datorer. Den senast anropade funktionen slutförs alltid först.

Relaterade artiklar:

• Implementera en stack med en länkad lista
• Grundläggande operationer i stackdatastruktur med implementeringar
• De 50 bästa problemen med stackdatastrukturen frågade i SDE-intervjuer
• Tillämpningar, fördelar och nackdelar med Stack
  
• Stack för konkurrenskraftig programmering