Википедиа

Стек: Засвар хоорондын ялгаа

Browse history interactively
← Өмнөх өөрчлөлтДараагийн ялгаа →
Content deleted Content added
VisualWikitext
No edit summary
No edit summary
Мөр 2:
{{cleanup|date=October 2011}}
[[Image:Data stack.svg|thumb|200px|right|стекийн хялбар дүрслэл]]
[[компьютерийн шинжлэх ухаанд]], '''стек''' (stack) нь онцгой үүрэгтэй [[өгөгдөлийн бүтэцийн төрөл]] буюу цуглуулга юм. Стек нь санах ойд байрлах өгөгдлийг зохион байгуулах нэгэн арга бөгөөд хязгаарлагдмал хандалт бүхий өгөгдлийн бүтцийн нэг бол стек юм. Стек нь top(орой), button(ёроол) -той. Стек нь pop(элемент авах) ба push( элемент хийх) гэсэн үндсэн үйлдэлүүдээс гадна бусад туслах функцуудтэй шугаман бүтэц бөгөөд эдгээр үйлдлүүдийг стекийн орой гэх нэг төгсгөлд гүйцэтгэдэг. Өөрөөр хэлбэл стекийн орой дахь хамгийн сүүлд орсон элемент эхэлж гарах зарчмаар ажиладаг.
 
Стекийг хамгийн энгийнээр сав гэж ойлгож болно. Бид савны дээрээс нь ямар нэгэн зүйлийг нэмж дээрээс нь хийсэн зүйлээ авдаг. Яг үүнтэй адилаар стек нь багцын pop(орой) гэж нэрлэгдэх нэг л талаас нь нэмдэг, устгадаг өгөгдлийн хийсвэр төрөл юм.
Мөр 11:
алгоритмд стек үндсэн үүрэг гүйцэтгэнэ. Жишээ нь CALL, RETURN зэрэг функцэд стекийг ашигладаг байна.
 
Стекийг олон янзын аргаар нэвтрүүлж болох боловч шугаман массив болон нэг холбоост жягсаалт ашигладаг. Массив ашиглах стекийг ихэвчлэн гараар тодорхойлж өгдөг. стек(stack) массивыг заагчаар тодорхойлсноор динамик ойгоос new операторын тусламжтайгаар MaxSize хэмжээтэй зайг Stack классын обьект зарлах үед нөөцлөн авна. Энэ нь хэдийгээр заагч ашиглаж байгаа боловч хувиарлалт хийснээс хойш түүний хэмжээ MaxSize-аас хэтрэхгүй тул статикаар тодорхойлогдож байна.
 
'''Стекийн хэрэглээ:'''
Line 45 ⟶ 44:
 
===хэрэгжүүлэлт===
Стекийг олон янзын аргаар нэвтрүүлж болох боловч шугаман массив болон нэг холбоост жягсаалт ашигладаг.
Стек нь массив болон шугаман жагсаалтыг хэрэгжүүлдэг. What identifies the data structure as a stack in either case is not the implementation but the interface: the user is only allowed to pop or push items onto the array or linked list, with few other helper operations. The following will demonstrate both implementations, using C.
 
====ArrayМассив====
Стекийг массив ашиглан хэрхэн нэвтрүүлэхийг авч үзье. Ийм стек нь статикаар тодорхойлогддог. Дараах стек кдассын зарлалттаар maxSize хэмжээтэй стек массив стекийн оройг тодорхойлох top хувьсагч болон стекд элемент хийх push() функц стекээс элеменэ авах рор() функц бусад туслах функын хамт тодорхойлогдсон байна. Стек массивыг заагчаар тодорхойлсоноор динамик ойгоос new операторын тусламжтайгаар maxSize хэмжээтэй зайг стек классын объект зарлах үед нөөцлөн авна. Энэ хэдийгээр заагч ашиглаж байгаа боловч статикаар тодорхойлогдож байна.
The '''array implementation''' aims to create an array where the first element (usually at the zero-offset) is the bottom. That is, <code>array[0]</code> is the first element pushed onto the stack and the last element popped off. The program must keep track of the size, or the length of the stack. The stack itself can therefore be effectively implemented as a two-element structure in C:
 
template <class Type>
<source lang="c">
class Stack{
typedef struct {
int top, maxSize;
size_t size;
Type*Stack;
int items[STACKSIZE];
puplic:
} STACK;
Stack(int mSize ): maxSize(msize)
</source>
{stack=new Type[maxSize]; top=-1;}
Stack()
{delete[] stack;}
bool push(const Type item);
bool pop(Type & item);
bool empty();
bool full();
}
 
====Жагсаалт====
The <code>push()</code> operation is used both to initialize the stack, and to store values to it. It is responsible for inserting (copying) the value into the <code>ps->items[]</code> array and for incrementing the element counter (<code>ps->size</code>). In a responsible C implementation, it is also necessary to check whether the array is already full to prevent an [[Buffer overflow|overrun]].
Зарим бодлогын хувьд стекп хадгалагдах өгөгдлийн хэмжээг урьдчилан хэлж мэдэх боломжгүй тохиолдлууд байдаг. Энэ тохиолдолд стекийг нэг холбоост жагсаалаар илэрхийлхээс өөр аргагүй юм. Стекийг жагсаалтаар илэрхийлдсэнээр түүний хэмжээ нь бодлогын нөхцөлөөс хамаарч программ ажиллах явцад динамикаар өөрчлөгдөх боломжтой. Дараах классын зарлалтаар стекийг тодорхойлоё.
 
template <class Type>
<source lang="c">
class Stack{
void push(STACK *ps, int x)
struct Node{
{
Type data; Node*link;
if (ps->size == STACKSIZE) {
};
fputs("Error: stack overflow\n", stderr);
Node*top;
abort();
public:
} else
Stack() {top=null;}
ps->items[ps->size++] = x;
Stack(){
}
Node*temp;
</source>
while(top){
 
temp=top; top=pop->link;
The <code>pop()</code> operation is responsible for removing a value from the stack, and decrementing the value of <code>ps->size</code>. A responsible C implementation will also need to check that the array is not already empty.
delete temp;
 
}
<source lang="c">
}
int pop(STACK *ps)
bool push(const Type item);
{
bool pop(Type & item);
if (ps->size == 0){
bool empty();
fputs("Error: stack underflow\n", stderr);
}
abort();
} else
return ps->items[--ps->size];
}
</source>
 
If we use a [[dynamic array]], then we can implement a stack that can grow or shrink as much as needed. The size of the stack is simply the size of the dynamic array. A dynamic array is a very efficient implementation of a stack, since adding items to or removing items from the end of a dynamic array is amortized O(1) time.
 
====Linked list====
The '''linked-list''' implementation is equally simple and straightforward. In fact, a simple [[singly linked list]] is sufficient to implement a stack—it only requires that the head node or element can be removed, or popped, and a node can only be inserted by becoming the new head node.
 
Unlike the array implementation, our structure typedef corresponds not to the entire stack structure, but to a single node:
 
<source lang="c">
typedef struct stack {
int data;
struct stack *next;
} STACK;
</source>
 
Such a node is identical to a typical singly linked list node, at least to those that are implemented in C.
 
The <code>push()</code> operation both initializes an empty stack, and adds a new node to a non-empty one. It works by receiving a data value to push onto the stack, along with a target stack, creating a new node by allocating memory for it, and then inserting it into a linked list as the new head:
 
<source lang="c">
void push(STACK **head, int value)
{
STACK *node = malloc(sizeof(STACK)); /* create a new node */
 
if (node == NULL){
fputs("Error: no space available for node\n", stderr);
abort();
} else { /* initialize node */
node->data = value;
node->next = empty(*head) ? NULL : *head; /* insert new head if any */
*head = node;
}
}
</source>
 
A <code>pop()</code> operation removes the head from the linked list, and assigns the pointer to the head to the previous second node. It checks whether the list is empty before popping from it:
 
<source lang="c">
int pop(STACK **head)
{
if (empty(*head)) { /* stack is empty */
fputs("Error: stack underflow\n", stderr);
abort();
} else { //pop a node
STACK *top = *head;
int value = top->data;
*head = top->next;
free(top);
return value;
}
}
</source>
 
===Stacks and programming languages===
Some languages, like [[Lisp (programming language)|LISP]] and [[Python (programming language)|Python]], do not call for stack implementations, since '''push''' and '''pop''' functions are available for any list. All [[Forth (programming language)|Forth]]-like languages (such as [[PostScript|Adobe PostScript]]) are also designed around language-defined stacks that are directly visible to and manipulated by the programmer. Examples from [[Common Lisp]]:
 
<source lang="lisp">
(setf list (list 'a 'b 'c))
;; ⇒ (A B C)
(pop list)
;; ⇒ A
list
;; ⇒ (B C)
(push 'new list)
;; ⇒ (NEW B C)
</source>
 
C++'s [[Standard Template Library]] provides a "<code>stack</code>" templated class which is restricted to only push/pop operations. Java's library contains a {{Javadoc:SE|java/util|Stack}} class that is a specialization of {{Javadoc:SE|java/util|Vector}}---this could be considered a design flaw, since the inherited get() method from {{Javadoc:SE|java/util|Vector}} ignores the LIFO constraint of the {{Javadoc:SE|java/util|Stack}}. PHP has an [http://www.php.net/manual/en/class.splstack.php SplStack] class.
"https://mn.wikipedia.org/wiki/Стек"-с авсан