data-structures
ढेर
खोज…
ढेर करने के लिए परिचय
स्टैक एक LIFO (अंतिम-इन, पहली-आउट) डेटा-संरचना है, यानी स्टैक में जोड़ा गया सबसे हाल का (या "अंतिम") तत्व पहला हटाए गए तत्व ("पहला आउट") होगा।
आइए एक बॉक्स में पुस्तकों के उदाहरण पर विचार करें। एक समय में केवल एक पुस्तक को बॉक्स से जोड़ा या हटाया जा सकता है, और इसे केवल जोड़ा और ऊपर से हटाया जा सकता है।
अब, पहली दो पुस्तकों वाला बॉक्स इस तरह दिखता है:
|--------| | book 2 | ◀──── top of box |--------| | book 1 | ◀──── bottom of box |--------|
यदि हम पुस्तक 3 जोड़ते हैं, तो यह सबसे ऊपर होगा। बाकी किताबें, जो कि पुस्तक 3 से पहले जोड़ी गई थीं, इसके नीचे रहेंगी:
|--------| | book 3 | ◀──── top of box |--------| | book 2 | |--------| | book 1 | ◀──── bottom of box |--------|
बॉक्स एक स्टैक की तरह है और किताबें डेटा तत्व हैं। बॉक्स में एक किताब जोड़ना, हटाए जाने के दौरान पुश ऑपरेशन होता है / बॉक्स के ऊपर से एक किताब निकालना पॉप ऑपरेशन है। यदि हम पॉप ऑपरेशन करते हैं, तो हमें किताब 3 मिलेगी, और बॉक्स वापस उसी तरह से चला जाएगा, जैसा कि हमने किताब 3 को धकेलने से पहले किया था। इसका मतलब है कि हमने जो अंतिम (या सबसे हाल का) तत्व डाला था वह पहला तत्व था। निकल गया (LIFO)। पुस्तक 1 प्राप्त करने के लिए, हमें दो और पॉप करने होंगे: एक पुस्तक 2 निकालने के लिए, और दूसरी पुस्तक 1 पाने के लिए।
एक सरणी का उपयोग करके स्टैक का कार्यान्वयन। इसके लिए, हमें शीर्ष स्थान (tos) की ओर इशारा करते हुए एक इंडेक्स की आवश्यकता होती है। जब भी किसी तत्व को एक के बाद एक स्टैक टॉग्रेस इंक्रीमेंट में धकेला जाता है और जब भी कोई पॉप ऑपरेशन किया जाता है तो स्टैक के शीर्ष को इंगित करने वाला इंडेक्स एक से घट जाता है।
धक्का दें:
PUSH ऑपरेशन से पहले
tos
|
|
|-----|-----|-----|-----|-----|
| i1 | i2 | i3 | i4 | |
|-----|-----|-----|-----|-----|
void push(dataElment item){
stack[top]=item; //item = i4
top++;
}
PUSH ऑपरेशन के बाद स्टैक में स्टैक के शीर्ष पर एक पॉइंटर होता है। जब भी पुश ऑपरेशन कहा जाता है, यह शीर्ष पर मूल्य रखता है और इसे मूल्य अपडेट करता है।
tos -- Top of the stack
tos
|
|
|-----|-----|-----|-----|
| i1 | i2 | i3 | |
|-----|-----|-----|-----|
POP: पॉप ऑपरेशन स्टैक के ऊपर से सामग्री को हटाता है और 1 से घटाकर टॉस के मूल्य को अपडेट करता है
पॉप ऑपरेशन से पहले:
tos
|
|
|-----|-----|-----|-----|-----|
| i1 | i2 | i3 | i4 | |
|-----|-----|-----|-----|-----|
dataElment pop(){
dataElment value = stack[tos--];
return value;
}
पॉप ऑपरेशन के बाद:
tos
|
|
|-----|-----|-----|-----|
| i1 | i2 | i3 | i4 |
|-----|-----|-----|-----|
When a push operation is performed it overwrites i4.
Palindromes खोजने के लिए ढेर का उपयोग करना
एक पैलिंड्रोम एक ऐसा शब्द है, जिसे 'कश्ती' की तरह पढ़ा जा सकता है।
यह उदाहरण दिखाएगा कि पायथन 3 का उपयोग करते हुए किसी दिए गए शब्द का तालमेल कैसा है।
सबसे पहले, हमें एक स्ट्रिंग को स्टैक में बदलने की आवश्यकता है (हम एरेस को स्टैक के रूप में उपयोग करेंगे)।
str = "string"
stk = [c for c in str] #this makes an array: ["s", "t", "r", "i", "n", "g"]
stk.append("s") #adds a letter to the array
stk.pop() #pops the last element
अब, हमें शब्द को उलटना होगा।
def invert(str):
stk = [c for c in str]
stk2 = []
while len(stk) > 0:
stk2.append(stk.pop())
#now, let's turn stk2 into a string
str2 = ""
for c in stk2:
str2 += c
return str2
अब हम शब्द और उल्टे रूप की तुलना कर सकते हैं।
def palindrome(str):
return str == invert(str)
सरणी और लिंक्ड सूची का उपयोग करके स्टैक कार्यान्वयन
एरे कार्यान्वयन
#include<stdio.h>
#define MAX 100000 //Global variables
int top = -1;
int a[MAX];
void push(int x){
if(top == MAX-1){ // Check whether stack is full
printf("Stack Overflow\n");
return;
}
a[++top] = x; // Otherwise increment top and insert x
}
void pop(){
if(top == -1){ // if top = -1, empty stack
printf("Empty stack\n");
return;
}
top--;
}
void print(){ //printing stack values
for(int i=0;i <= top;i++){
printf("%d ",a[i]);
}
printf("\n");
}
void topValue(){ // Method can print the top value of a stack
printf("%d",a[top]);
}
int main(){
push(5);
push(20);
push(15);
print();
pop();
print();
push(35);
print();
topValue();
}
लिंक्ड सूची कार्यान्वयन
#include<stdio.h>
#include<malloc.h>
struct node{
int data;
node* link;
};
node* top = NULL;
void push(int data){
node* temp = (struct node*)malloc(sizeof(struct node*));
temp->data = data;
temp->link = top;
top = temp;
}
void pop(){
if(top == NULL) return;
node* temp = top;
top = top->link;
free(temp);
}
void print(){
node* t = top;
while(t != NULL){
printf("%d ",t->data);
t=t->link;
}
printf("\n");
}
void topValue(){
printf("%d ",top->data);
}
int main(){
push(5);
push(20);
push(15);
print();
pop();
print();
push(35);
print();
topValue();
}
बैलेंस्ड कोष्ठक की जाँच
एक कोष्ठक को निम्नलिखित वर्णों में से किसी एक में माना जाता है: ( , ) , { , } , [ , या ] ।
दो कोष्ठक अगर एक खुला कोष्ठक (यानी, एक जोड़ी मिलान माना जाता है ( , [ , या { ) एक बंद कोष्ठक (यानी, के लिए छोड़ दिया करने के लिए होता है ) , ] , या } ठीक उसी प्रकार के)। कोष्ठक के तीन प्रकार के मिलान जोड़े हैं: [] , {} , और () ।
यदि ब्रैकेट्स के सेट को संलग्न किया जाता है, तो मिलान करने के लिए कोष्ठक की एक मिलान जोड़ी संतुलित नहीं है। उदाहरण के लिए, {[(])} संतुलित नहीं है क्योंकि { और } बीच की सामग्री संतुलित नहीं है। वर्ग कोष्ठक की जोड़ी एक एकल, असंतुलित प्रारंभ कोष्ठक, encloses ( , और कोष्ठक की जोड़ी एक एकल, असंतुलित समापन वर्ग कोष्ठक encloses, ] ।
इस तर्क के द्वारा, हम कहते हैं कि कोष्ठक का एक क्रम संतुलित माना जाता है यदि निम्नलिखित स्थितियाँ पूरी होती हैं:
इसमें कोई बेजोड़ कोष्ठक नहीं है।
कोष्ठक के एक मिलान जोड़े की सीमा के भीतर संलग्न कोष्ठक का सबसेट भी कोष्ठक की एक मिलान जोड़ी है।
कलन विधि:
- एक ढेर घोषित करें (
stackकहें)। - अब स्ट्रिंग इनपुट को पार करें।
- a) यदि वर्तमान वर्ण एक प्रारंभिक ब्रैकेट है (यानी
(या{या[) तो इसे स्टैक करने के लिए धक्का दें। - b) यदि वर्तमान वर्ण एक समापन ब्रैकेट (यानी
)या}या]तो स्टैक से पॉप करें। यदि पोप किया हुआ पात्र मिलान शुरू करने वाला ब्रैकेट है तो ठीक है और अन्य कोष्ठकnot balancedहैं। - ग) यदि वर्तमान वर्ण एक समापन ब्रैकेट (यानी
)या}या]और स्टैक खाली है, तो कोष्ठकnot balanced।
- पूर्ण ट्रैवर्सल के बाद, यदि स्टैक में कुछ शुरुआती ब्रैकेट बचे हैं, तो स्ट्रिंग
not balancedनहीं है, हमारे पास एकbalancedस्ट्रिंग है।