Content deleted Content added
|
|
|
Стек
==программ хангамжын стек==
Стек нь өгөгдөл хийх ба гаргаж авах гэсэн 2 үйлдэл бүхий шугаман бүтэц бөгөөд эдгээр үйлдлүүдийг стекийн орой гэх зөвхөн нэг төгсгөлд гүйцэтгэдэг. Өөрөөр хэлбэл стекийн орой дахь хамгийн сүүлд орсон элемент нь хамгийн түрүүнд гарах зарчмаар ажилладаг. Иймээс стекийг сүүлд орсон нь эхэлж гарах (LIFO last in first out) жагсаалт гэж бас нэрлэдэг. Стек нь рекурсив програмчлалын үндэс юм. Бидний хэрэглэж буй компьютер бүр стектэй байдаг. Өөрөөр хэлбэл дахин шинэ стек хийх шаардлага үүсдэггүй
• Ассемблер хэлээр push, pop командыг бичихэд стекэд өгөгдөл нэмж, хасах боломжтой.
===хэрэгжүүлэлт===
Стекийг олон янзын аргаар нэвтрүүлж болох боловч шугаман массив болон нэг холбоост жягсаалт ашигладаг.
Стекийн шаардлага:
Хэдийгээр стек нь маш хязгаарлагдмал үйлдэлтэй боловч компьютерийн програмчлалд чухал үүрэгтэй өгөгдлийн бүтцүүдийн нэг юм. Тухайлбал ямар нэг ажлын явцад өөр зүйл хийхээр түр хойшлуулах, эсвэл програм бүхэлдээ ийм зарчмаар ажиллах зэрэг олон алгоритмд стек үндсэн үүрэг гүйцэтгэнэ. Жишээ нь CALL, RETURN зэрэг функцэд стекийг ашигладаг байна.
====Массив====
Стекийг массив ашиглан нэвтрүүлэх
Стекийг олон янзын аргаар нэвтрүүлж болох боловч ихэвчлэн шугаман массив, ашигланэсвэл хэрхэннэг нэвтрүүлэхийгхолбоост авчжагсаалт үзьеашигладаг. ИймМассив стекашиглах ньстекийг статикаарихэвчлэн гараар тодорхойлж тодорхойлогддогөгдөг. Дараах стекStack кдассынклассын зарлалттаарзарлалтаар maxSizeMaxSize хэмжээтэй стекstack массив, стекийн оройг тодорхойлох top хувьсагч болон стекд элемент хийх push() функц, стекээс элеменээлемэнт авах рорpop() функц бусад туслах функынфункцүүдийн хамт тодорхойлогдсон байнатодорхойллоо. СтекStack массивыг заагчаар тодорхойлсоноортодорхойлсноор динамик ойгоос new операторын тусламжтайгаар maxSizeMaxSize хэмжээтэй зайг стекStack классын объектобьект зарлах үед нөөцлөн авна. Энэ нь хэдийгээр заагч ашиглаж байгаа боловч хувиарлалт хийснээс хойш түүний хэмжээ MaxSize-аас хэтрэхгүй тул статикаар тодорхойлогдож байна.
template <class Type>
class Stack{
int top, maxSize;
Type*Stack;
puplic:
Stack(int mSize ): maxSize(msize)
{stack=new Type[maxSize]; top=-1;}
Stack()
{delete[] stack;}
bool push(const Type item);
bool pop(Type & item);
bool empty();
bool full();
====Жагсаалт====
Зарим бодлогын хувьд стекп хадгалагдах өгөгдлийн хэмжээг урьдчилан хэлж мэдэх боломжгүй тохиолдлууд байдаг. Энэ тохиолдолд стекийг нэг холбоост жагсаалаар илэрхийлхээс өөр аргагүй юм. Стекийг жагсаалтаар илэрхийлдсэнээр түүний хэмжээ нь бодлогын нөхцөлөөс хамаарч программ ажиллах явцад динамикаар өөрчлөгдөх боломжтой. Дараах классын зарлалтаар стекийг тодорхойлоё.
template <class Type>
class Stack{
struct Node{
Type data; Node*link;
};
Node*top;
public:
Stack() {top=null;}
Stack(){
Node*temp;
while(top){
temp=top; top=pop->link;
delete temp;
}
}
bool push(const Type item);
bool pop(Type & item);
bool empty();
}
|
