Stack का Implementation

एक array पर बनाया गया stack plates के एक pile जैसा है जहां आप एक marker रखते हैं जो दिखाता है कौन सी plate top पर है। Pushing marker को ऊपर move करता है और popping इसे नीचे।

In this page:

Array Stack
Stack Class
Overflow and Underflow
Linked List Stack
Implementation Practice

Syntax

markup

class Stack:
    def __init__(self):
        self.items = []
    def push(self, item):
        self.items.append(item)
    def pop(self):
        return self.items.pop()
    def peek(self):
        return self.items[-1]

Array Stack

एक stack एक plain array के ऊपर बनाया जा सकता है एक top index रखकर जो सबसे हाल ही में pushed element की position track करता है, push पर इसे increment करते हुए और pop पर decrement करते हुए।

उदाहरण: Array Stack

#include <iostream>
using namespace std;
int main() {
    int arr[5]; int top = -1;
    arr[++top] = 10; arr[++top] = 20;
    cout << "top index=" << top << ", value=" << arr[top] << endl;
    top--;
    cout << "after pop, top index=" << top << endl;
    return 0;
}

public class Main {
    public static void main(String[] args) {
        int[] arr = new int[5]; int top = -1;
        arr[++top] = 10; arr[++top] = 20;
        System.out.println("top index=" + top + ", value=" + arr[top]);
        top--;
        System.out.println("after pop, top index=" + top);
    }
}

arr = [0] * 5
top = -1
top += 1; arr[top] = 10
top += 1; arr[top] = 20
print("top index=", top, ", value=", arr[top])
top -= 1
print("after pop, top index=", top)

#include <stdio.h>
int main() {
    int arr[5]; int top = -1;
    arr[++top] = 10; arr[++top] = 20;
    printf("top index=%d, value=%d\n", top, arr[top]);
    top--;
    printf("after pop, top index=%d\n", top);
    return 0;
}

Stack Class

उस array और top index को एक class के अंदर wrap करना internal details private रखता है और सिर्फ clean push, pop, और peek methods expose करता है, इसलिए stack उपयोग करने वाले code को यह जानने की ज़रूरत नहीं कि यह underneath कैसे implemented है।

उदाहरण: Stack Class

#include <iostream>
using namespace std;
class Stack {
    int arr[5]; int top = -1;
public:
    void push(int x) { arr[++top] = x; }
    int pop() { return arr[top--]; }
    int peek() { return arr[top]; }
};
int main() {
    Stack s;
    s.push(5); s.push(15);
    cout << "peek: " << s.peek() << endl;
    return 0;
}

class Stack {
    int[] arr = new int[5]; int top = -1;
    void push(int x) { arr[++top] = x; }
    int pop() { return arr[top--]; }
    int peek() { return arr[top]; }
}
public class Main {
    public static void main(String[] args) {
        Stack s = new Stack();
        s.push(5); s.push(15);
        System.out.println("peek: " + s.peek());
    }
}

class Stack:
    def __init__(self):
        self.items = []

    def push(self, x):
        self.items.append(x)

    def pop(self):
        return self.items.pop()

    def peek(self):
        return self.items[-1]

s = Stack()
s.push(5); s.push(15)
print("peek:", s.peek())

#include <stdio.h>
typedef struct { int arr[5]; int top; } Stack;
void push(Stack *s, int x) { s->arr[++s->top] = x; }
int peek(Stack *s) { return s->arr[s->top]; }
int main() {
    Stack s = { .top = -1 };
    push(&s, 5); push(&s, 15);
    printf("peek: %d\n", peek(&s));
    return 0;
}

Overflow and Underflow

एक array-backed stack की एक fixed capacity है, इसलिए एक full stack में push करना overflow का कारण बनता है, और एक empty से pop करना underflow का कारण बनता है। दोनों को crash होने या garbage data return करने से बचने के लिए explicit checks चाहिए।

उदाहरण: Overflow and Underflow

#include <iostream>
using namespace std;
int main() {
    int arr[2]; int top = -1; int capacity = 2;
    arr[++top] = 1; arr[++top] = 2;
    if (top == capacity - 1) cout << "overflow: stack is full, cannot push" << endl;
    top = -1;
    if (top == -1) cout << "underflow: stack is empty, cannot pop" << endl;
    return 0;
}

public class Main {
    public static void main(String[] args) {
        int[] arr = new int[2]; int top = -1; int capacity = 2;
        arr[++top] = 1; arr[++top] = 2;
        if (top == capacity - 1) System.out.println("overflow: stack is full, cannot push");
        top = -1;
        if (top == -1) System.out.println("underflow: stack is empty, cannot pop");
    }
}

arr = [0, 0]
top = -1
capacity = 2
top += 1; arr[top] = 1
top += 1; arr[top] = 2
if top == capacity - 1:
    print("overflow: stack is full, cannot push")
top = -1
if top == -1:
    print("underflow: stack is empty, cannot pop")

#include <stdio.h>
int main() {
    int arr[2]; int top = -1; int capacity = 2;
    arr[++top] = 1; arr[++top] = 2;
    if (top == capacity - 1) printf("overflow: stack is full, cannot push\n");
    top = -1;
    if (top == -1) printf("underflow: stack is empty, cannot pop\n");
    return 0;
}

Linked List Stack

एक stack एक array के बजाय एक linked list पर भी बनाया जा सकता है, head पर push और pop करते हुए, जिसकी naturally कोई fixed size limit नहीं और कभी overflow नहीं होता, node pointers के लिए per element थोड़ी extra memory की कीमत पर।

उदाहरण: Linked List Stack

#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
int main() {
    Node* top = nullptr;
    Node* n1 = new Node{1, top}; top = n1;
    Node* n2 = new Node{2, top}; top = n2;
    cout << "pushed onto head, top=" << top->data << endl;
    top = top->next;
    cout << "popped from head, new top=" << top->data << endl;
    return 0;
}

class Node { int data; Node next; Node(int d, Node n) { data = d; next = n; } }
public class Main {
    public static void main(String[] args) {
        Node top = null;
        top = new Node(1, top);
        top = new Node(2, top);
        System.out.println("pushed onto head, top=" + top.data);
        top = top.next;
        System.out.println("popped from head, new top=" + top.data);
    }
}

class Node:
    def __init__(self, data, next_node):
        self.data = data
        self.next = next_node

top = None
top = Node(1, top)
top = Node(2, top)
print("pushed onto head, top=", top.data)
top = top.next
print("popped from head, new top=", top.data)

#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
int main() {
    struct Node *top = NULL;
    struct Node *n1 = malloc(sizeof(struct Node)); n1->data = 1; n1->next = top; top = n1;
    struct Node *n2 = malloc(sizeof(struct Node)); n2->data = 2; n2->next = top; top = n2;
    printf("pushed onto head, top=%d\n", top->data);
    top = top->next;
    printf("popped from head, new top=%d\n", top->data);
    return 0;
}

Implementation Practice

चाहे एक array या एक linked list से backed हो, दोनों implementations identical push/pop/peek behavior expose करते हैं; choice इस पर आ जाती है कि आपको एक fixed, predictable memory footprint चाहिए या unbounded, dynamic growth।

उदाहरण: Implementation Practice

#include <iostream>
#include <stack>
using namespace std;
int main() {
    stack<int> arrayLike;
    arrayLike.push(1); arrayLike.push(2);
    cout << "same push/pop/peek interface regardless of array or linked-list backing: " << arrayLike.top() << endl;
    return 0;
}

import java.util.Stack;
public class Main {
    public static void main(String[] args) {
        Stack<Integer> arrayLike = new Stack<>();
        arrayLike.push(1); arrayLike.push(2);
        System.out.println("same push/pop/peek interface regardless of backing: " + arrayLike.peek());
    }
}

array_like = []
array_like.append(1)
array_like.append(2)
print("same push/pop/peek interface regardless of backing:", array_like[-1])

#include <stdio.h>
int main() {
    int s[10], top = -1;
    s[++top] = 1; s[++top] = 2;
    printf("same push/pop/peek interface regardless of backing: %d\n", s[top]);
    return 0;
}

Chapter Quiz — Complete all 5 topics to unlock

0/5 topics done

Complete these topics first:

← Previous Lesson Stack Introduction Next Lesson → Balanced Parentheses