प्रौद्योगिकी साझेदारी

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

शीर्षक

नमस्ते मित्राणि!

1. स्तम्भः

१.१ ढेरस्य मूलभूताः अवधारणाः

Stack: एकः विशेषः रेखीयसूची या केवलं नियत-अन्ते सम्मिलित-विलोपन-क्रियाणां अनुमतिं ददाति । यः अन्तः दत्तांशप्रवेश-विलोपन-क्रियासु प्रविशति सः स्तम्भस्य उपरिभागः इति उच्यते, अपरः अन्तः स्तम्भस्य अधः इति उच्यते ।स्तम्भे दत्तांशतत्त्वानि अनुपालनं कुर्वन्तिलिफो (Last In First Out) इति सिद्धान्तः । मटनकबाबभक्षणवत् कल्पयितुं शक्नुमः,प्रथमं स्थापयतुमटनस्य खण्डाः अन्तः निपीडिताः भवन्तिअधः，अन्तिमःमटनखण्डाः अन्तः सन्तिउपरिइत्यस्य।

स्तम्भस्य धक्कानम् : स्तम्भस्य निवेशनक्रिया push/push/push इति कथ्यते ।स्टैकस्य उपरितः दत्तांशं सम्मिलितं कुर्वन्तु。

Pop: stack इत्यस्य deletion operation popping इति उच्यते ।बहिर्गच्छन् दत्तांशः अपि स्तम्भस्य उपरि अस्ति。

१.२ ढेरस्य कार्यान्वयनम्

सामान्यतया स्टैक् कार्यान्वितुं सरणीं उपयुज्य अथवा स्टैक् कार्यान्वितुं लिङ्क्ड् सूचीं उपयुज्य यत्किमपि श्रेष्ठं, सापेक्षतया, कार्यान्वितुं शक्यतेसरणी संरचनास्टैक् इत्यस्य कार्यान्वयनम् सरलतरं अधिकं कार्यकुशलं च भवति ।

यतः पूर्वक्रमसारणीयाः (data structure sequence table) अस्माकं कृते अन्तेतः सम्मिलितुं विलोपयितुं च सरणीयाः संरचनायाः उपयोगः अतीव सुविधाजनकः अस्ति, अतः स्टैकस्य कार्यान्वयने वयं सरणीयाः अन्तं स्तम्भस्य उपरिभागं, शिरः च तलम् इति परिभाषयामः स्तम्भः ।

---

2. स्टैक इन्टरफेस् कार्यान्वयनम्

क्रमसूची इव स्टैक् नियतदीर्घतायाः स्थिरस्टैक् अथवा गतिशीलरूपेण वर्धमानः स्टैक् इत्यस्य रूपेण डिजाइनं कर्तुं शक्यते ।यतः नियत-दीर्घतायाः स्तम्भस्य महतीः सीमाः सन्ति तथा च व्यवहारे व्यावहारिकं न भवति, अतः वयं मुख्यतया समर्थनं कार्यान्वयामःगतिशीलरूपेण वर्धमानः ढेरः。

पूर्वस्य अनुक्रमसूची/लिङ्क्ड् सूची अन्तरफलकस्य कार्यान्वयनस्य समानं वयं प्रथमं "Stack.h" इति शीर्षकसञ्चिकां तथा च "Stack.c" तथा "Test.c" इति स्रोतसञ्चिकाद्वयं निर्मामः ।

प्रथमं "Stack.h" इत्यस्य सम्पूर्णं कोडं दर्शयामः, २ स्रोतसञ्चिकासु "Stack.h" इत्यस्य उद्धरणं न विस्मरन्तु

#pragma once				//防止头文件被二次引用
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
 
typedef int ElemType;		//如果要修改存储的数据类型可直接在此修改
typedef struct Stack {
	ElemType* arr;			//动态数组
	int top;				//栈顶
	int capacity;			//容量
}Stack;
 
 
void StackInit(Stack* ps);//初始化栈
 
void StackPush(Stack* ps, ElemType x);//入栈
 
void StackPop(Stack* ps);//出栈
 
ElemType StackTop(Stack* ps);//获取栈顶元素
 
int StackSize(Stack* ps);//获取栈中有效元素的个数
 
int StackEmpty(Stack* ps);//检测栈是否为空,如果为空返回非零结果,如果不为空返回0
 
void StackDestroy(Stack* ps);//销毁栈

तेषु "उपरि" इत्यस्य अर्थः प्रारम्भिकमूल्येन निर्धारितः भवति, यत् अधः विस्तरेण व्याख्यास्यते । तदनन्तरं वयं interface इत्यस्य कार्यान्वयनम् आरभामः ।

(1) आरंभीकरण ढेर

//初始化栈
void StackInit(Stack* ps) {
	assert(ps);		//断言,防止传入空指针
	ps->arr = NULL; //初始化数组,置空
	ps->capacity = 0;//top指向栈顶元素的下一个位置
	ps->top = 0;	 //初始化容量
}

सहजतया अवगन्तुं वयं संरचनायां top इत्येतत् सरणीयाः उपलिपिः इति अनुमानतः अवगच्छामः ।यदि वयं स्तम्भस्य आरम्भं कुर्वन्तः शीर्षं 0 यावत् आरभामः तर्हि स्तम्भे कोऽपि दत्तांशः नास्ति, तथा च शीर्षः स्तम्भे शीर्षदत्तांशस्य अग्रिमस्थानं सूचयति ।

यदि वयं top -1 -पर्यन्तं आरभामः तर्हि top इत्येतत् स्टैक् मध्ये top data इत्यस्य स्थानं सूचयिष्यति । अत्र 0 इति आरम्भं कर्तुं अस्माकं कृते श्रेयस्करम् यतः एलिमेण्ट् योजयितुं एलिमेण्ट्स् डिलीट् कर्तुं च सुविधाजनकम् अस्ति ।

(2) स्तम्भे धक्कायन्तु

//入栈
void StackPush(Stack* ps, ElemType x) {
	//扩容
	if (ps->capacity == ps->top) //容量已满,需要扩容
	{
		//如果容量为0,则扩容到4; 否则扩大2倍
		int newCapacity = ps->capacity == 0 ? 4 : 2 * (ps->capacity);
		//创建一个临时指针变量来存储新空间地址,防止开辟失败
		ElemType* temp = realloc(ps->arr, newCapacity * sizeof(ElemType));
		if (temp == NULL) //防止开辟失败出现空指针
		{
			perror("realloc fail!n");
			exit(1);
		}
		ps->arr = temp;	  //将临时指针变量中存放的新空间地址赋给arr
		ps->capacity = newCapacity;//空间容量更新
	}
	ps->arr[ps->top] = x;//将数据存放进栈顶元素的下一个位置
	ps->top++;//位置更新
}

यतः stack तथा sequence table इत्येतयोः मध्ये भेदः अस्ति, अतः वयं directly traverse and print कर्तुं न शक्नुमः अतः यदि वयं stack मध्ये elements मुद्रयितुम् इच्छामः तर्हि StackEmpty function तथा StackPop function इत्यस्य उपयोगः करणीयः, यस्य विषये पश्चात् चर्चा भविष्यति .

(3) पोप आउट्

//出栈
void StackPop(Stack* ps) {
	assert(ps);			//断言,防止传入空指针
	assert(ps->top);	//断言,防止栈中没有元素,却还在执行删除
	ps->top--;			//top指针往前挪动一位(相当于这个位置被覆盖了)
}

(4) ढेरस्य उपरितनतत्त्वं प्राप्नुवन्तु

//获取栈顶元素
ElemType StackTop(Stack* ps) {
	assert(ps);				//断言,防止传入空指针
	assert(ps->top);		//断言,防止栈为空
	return ps->arr[ps->top - 1];//top-1为栈顶元素的位置,返回其值
}

(5) स्टैक् मध्ये वैधतत्त्वानां संख्यां प्राप्नुत

//获取栈中有效元素的个数
int StackSize(Stack* ps) {
	assert(ps);				//断言,防止传入空指针
	return ps->top;			//top即为有效元素的个数
}

(6) स्तम्भः रिक्तः अस्ति वा इति पश्यन्तु

//检测栈是否为空,如果为空返回非零结果,如果不为空返回0
int StackEmpty(Stack* ps) {
	assert(ps);				//断言,防止传入空指针
	return ps->top == 0;	//如果top==0, 说明栈为空
}

अत एव पूर्वस्मिन् प्रतिपादने StackEmpty इत्येतत् योजयितुं आवश्यकम्तार्किक नकारात्मकता संचालककारणं यत् यदि स्तम्भः रिक्तः अस्ति तर्हि StackEmpty सत्यं प्रत्यागच्छति, तथा च false इत्यस्य नकारः स्तम्भे तत्त्वानि सन्ति इति सिद्धयितुं शक्नोति ।

(7) स्तम्भं नाशयतु

//销毁栈
void StackDestroy(Stack* ps) {
	assert(ps);				//断言,防止传入空指针
	if (ps->arr)			//如果动态数组有效
	{
		free(ps->arr);		//释放arr
		ps->arr = NULL;		//将arr置空
	}
	ps->capacity = 0;		//数组的容量为0
	ps->top = 0;			//数组的栈顶top为0
 
}

सर्वेषां अन्तरफलकानां समाप्तेः अनन्तरं Test.c इत्यस्मिन् कोडस्य परीक्षणं कुर्मः:

किञ्चित् अधिकं परीक्षयामः :

सर्वथा समस्या नास्ति।

#include"Stack.h"
 
//初始化栈
void StackInit(Stack* ps) {
	assert(ps);		//断言,防止传入空指针
	ps->arr = NULL; //初始化数组,置空
	ps->capacity = 0;//top指向栈顶元素的下一个位置
	ps->top = 0;	 //初始化容量
}
 
//入栈
void StackPush(Stack* ps, ElemType x) {
	//扩容
	if (ps->capacity == ps->top) //容量已满,需要扩容
	{
		//如果容量为0,则扩容到4; 否则扩大2倍
		int newCapacity = ps->capacity == 0 ? 4 : 2 * (ps->capacity);
		//创建一个临时指针变量来存储新空间地址,防止开辟失败
		ElemType* temp = realloc(ps->arr, newCapacity * sizeof(ElemType));
		if (temp == NULL) //防止开辟失败出现空指针
		{
			perror("realloc fail!n");
			exit(1);
		}
		ps->arr = temp;	  //将临时指针变量中存放的新空间地址赋给arr
		ps->capacity = newCapacity;//空间容量更新
	}
	ps->arr[ps->top] = x;//将数据存放进栈顶元素的下一个位置
	ps->top++;//位置更新
}
 
//出栈
void StackPop(Stack* ps) {
	assert(ps);			//断言,防止传入空指针
	assert(ps->top);	//断言,防止栈中没有元素,却还在执行删除
	ps->top--;			//top指针往前挪动一位(相当于这个位置被覆盖了)
}
 
//获取栈顶元素
ElemType StackTop(Stack* ps) {
	assert(ps);				//断言,防止传入空指针
	assert(ps->top);		//断言,防止栈为空
	return ps->arr[ps->top - 1];//top-1为栈顶元素的位置,返回其值
}
 
//获取栈中有效元素的个数
int StackSize(Stack* ps) {
	assert(ps);				//断言,防止传入空指针
	return ps->top;			//top即为有效元素的个数
}
 
//检测栈是否为空,如果为空返回非零结果,如果不为空返回0
int StackEmpty(Stack* ps) {
	assert(ps);				//断言,防止传入空指针
	return ps->top == 0;	//如果top==0, 说明栈为空
}
 
//销毁栈
void StackDestroy(Stack* ps) {
	assert(ps);				//断言,防止传入空指针
	if (ps->arr)			//如果动态数组有效
	{
		free(ps->arr);		//释放arr
		ps->arr = NULL;		//将arr置空
	}
	ps->capacity = 0;		//数组的容量为0
	ps->top = 0;			//数组的栈顶top为0
 
}

व्यायाम खण्ड

1. स्टैक्स् विषये निम्नलिखितवाक्येषु कः सम्यक् अस्ति ( ) .

उ. स्टैक् "first in first out" इति दत्तांशसंरचना अस्ति

B. लिङ्क्ड् सूचीं वा क्रमसूचीं वा उपयुज्य स्टैक् कार्यान्वितुं शक्यते

C. स्टैक् केवलं स्टैक् इत्यस्य अधः एव दत्तांशं सम्मिलितुं शक्नोति

D. स्टैक् दत्तांशं विलोपयितुं न शक्नोति

सम्यक् उत्तरम् : १. ख

त्रुटिः क: ढेरः अन्तिम-प्रथम-निर्गमः दत्तांशसंरचना अस्ति, तथा च कतारः प्रथम-प्रवेशः, प्रथम-बहिः अस्ति ।

B सम्यक् अस्ति: क्रमसूचीनां तथा लिङ्क्ड् सूचीनां उपयोगः स्टैक्स् कार्यान्वितुं शक्यते, परन्तु क्रमसूचीनां उपयोगः सामान्यतया भवति यतोहि स्टैक् अनुक्रमसूचिकायाः ​​क्षत्रियसंस्करणरूपेण गण्यते प्रयुक्तं भवति, तथा च क्रमसारणीयाः पुच्छप्रवेशः प्रयुक्तः भवति पुच्छविलोपनं पुच्छविलोपनं च चलतत्त्वानां आवश्यकता नास्ति तथा च ते अतीव कुशलाः सन्ति, अतः सामान्यतया क्रमिकसारणीनां उपयोगेन कार्यान्विताः भवन्ति

C error: स्टैक् केवलं स्टैक् इत्यस्य उपरि input insertion and deletion operations कर्तुं शक्नोति

D error: स्टैक् मध्ये push तथा pop ऑपरेशन्स् सन्ति Pop इति स्टैक् तः एकं एलिमेण्ट् डिलीट् कर्तुं भवति ।

2. एकस्य स्टैकस्य पुश-अनुक्रमः ABCDE भवति, असम्भवः पॉप-अनुक्रमः च ( ) भवति ।

A.ABCDE

बी.ई.डी.सी.बी.ए

सी.डीसीईबीए

D.ECDBA

सम्यक् उत्तरम् : १. घ

यदि E प्रथमं बहिः आगच्छति तर्हि तस्य अर्थः अस्ति यत् ABCDE सर्वं स्टैक् उपरि धक्कायितम् अस्ति ततः E स्टैक् तः बहिः पॉप् कृत्वा स्टैक् इत्यस्य उपरितनं तत्त्वं D भवति यदि पुनः पॉप् आउट् भवति तर्हि D भवितुमर्हति, न तु C .

अतः D इति चयनं कर्तव्यम्

3. क्रमिक-ढेरस्य तुलने श्रृङ्खला-स्तम्भस्य स्पष्टलाभाः सन्ति ( ) ।

उ. सम्मिलनसञ्चालनं अधिकं सुविधाजनकं भवति

B. विलोपनसञ्चालनं अधिकं सुविधाजनकं भवति

ग. स्तम्भे धक्कायन्ते सति विस्तारस्य आवश्यकता नास्ति

सम्यक् उत्तरम् : १. ग

त्रुटिः A. यदि एतत् लिङ्क्ड् स्टैक् अस्ति तर्हि सामान्यतया हेड इन्सर्शन अथवा हेड डिलीशन क्रियाः आवश्यकाः सन्ति, यदा तु क्रमिक स्टैक् सामान्यतया टेल् इन्सर्शन तथा टेल डिलीशन ऑपरेशन्स् करोति, लिङ्क्ड् लिस्ट् इत्यस्य ऑपरेशन् क्रमिकसारणीयाः अपेक्षया अधिकं जटिलं भवति, अतः भवति एकं स्तम्भं कार्यान्वितुं क्रमिकसंरचनायाः उपयोगः सरलतरः ।

ख गलतः अस्ति, कारणार्थं क इति पश्यन्तु।

C सम्यक् भवति यदा स्तम्भः श्रृङ्खलासंरचनायां कार्यान्वितः भवति तदा स्तम्भे प्रत्येकं धक्काः लिङ्क्ड् सूचीयाः शिरसि नोड् सम्मिलितुं समकक्षः भवति ।

4. कतारं कार्यान्वितुं स्टैक्स् इत्यस्य उपयोगविषये निम्नलिखितेषु कथनेषु कः अशुद्धः अस्ति ( ) ।

उ. कतारं कार्यान्वितुं स्टैक् सिमुलेशनस्य उपयोगेन द्वौ स्टैक् उपयोक्तुं शक्यते, एकः स्टैक् कतारं प्रविष्टुं अनुकरणं करोति, एकः स्टैक् च कतारं त्यक्त्वा गमनस्य अनुकरणं करोति ।

B. प्रत्येकं वारं यदा भवन्तः dequeue कुर्वन्ति तदा भवन्तः एकस्मिन् stack मध्ये सर्वाणि elements अन्यस्मिन् stack मध्ये import कृत्वा ततः pop out करणीयम् ।

C. पङ्क्तौ प्रवेशं कुर्वन् केवलं पङ्क्तिप्रवेशस्य अनुकरणं कुर्वन्तः स्टैक् मध्ये प्रत्यक्षतया तत्त्वानि संग्रहयन्तु ।

D. कतारक्रियायाः समयजटिलता O(1) भवति ।

सम्यक् उत्तरम् : १. ख

विकल्पे B मध्ये एकः स्तम्भः कतारविच्छेदनस्य अनुकरणं करोति यदा स्टैक् रिक्तः भवति तदा अनुकरणीयपङ्क्तिस्थापनस्य सर्वे तत्त्वानि न .प्रतिवारं तत्त्वानि आयातितव्यानि, अतः त्रुटिः अस्ति

विकल्पे A मध्ये, स्तम्भानां पङ्क्तिनां च लक्षणं विपरीतम् अस्ति A स्तम्भः कतारं कार्यान्वितुं न शक्नोति ।

विकल्पे C मध्ये एकः स्तम्भः पङ्क्तिप्रवेशस्य अनुकरणं करोति, एकः स्तम्भः पङ्क्तिं प्रविशति सति पङ्क्तिप्रवेशस्य अनुकरणं कुर्वन्तः स्तम्भाः प्रत्यक्षतया संगृहीताः भवन्ति ।

विकल्पे D मध्ये कतारीकरणस्य अर्थः भवति स्तम्भे तत्त्वानि स्थापनम्, अतः समयजटिलता O(1) भवति ।

समाप्तः

अद्य वयं स्टैकस्य दत्तांशसंरचनायाः विषये ज्ञातवन्तः किं लिङ्क्ड् लिस्ट् इत्यस्मात् अधिकं सरलं न भवति हाहाहाहा, आशासे यत् एषः लेखः मम मित्रेभ्यः सहायकः भविष्यति !!!

याचतेपसन्दं कुर्वन्तु, प्रियं च अनुसरणं कुर्वन्तु !!!

धन्यवादः सर्वेभ्यः !