Инструменты пользователя

Инструменты сайта


Боковая панель

Связь

stek

Стек

Стек (англ. stack — стопка) — структура данных с методом доступа к элементам LIFO (англ. Last In — First Out, «последним пришел — первым вышел»). Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно снять верхнюю. Наиболее наглядным примером организации стека служит детская пирамидка, где добавление и снятие колец осуществляется как раз согласно определению стека.

Добавление элемента, называемое также проталкиванием (push), возможно только в вершину стека (добавленный элемент становится первым сверху). Удаление элемента, называемое также выталкивание (pop), возможно также только из вершины стека, при этом, второй сверху элемент становится верхним.

Стеки широко применяются в системном программном обеспечении, компиляторах, в различных рекурсивных алгоритмах.

Источник: От C к Ассемблеру. Часть памяти, выделяемой программе системой, резервируется под стек. Процессоры Intel 80386 и выше имеют в своем распоряжении регистр esp (от англ. stack pointer – указатель вершины стека), в котором хранится адрес текущей вершины стека.

A.Bадрес возврата в функцию
x=0значение переменной
A.Bадрес возврата в функцию
x=5значение переменной

Стек - динамическая структура данных, представляющая из себя упорядоченный набор элементов, в которой добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной стека. Кроме того, стек обладает так называемым базовым адресом. Под этим понятием скрывается начальный адрес памяти, в которой размещается стек.

Для хранения стека в памяти отводится сплошная область, граничные адреса которой являются параметрами физической структуры стека. Если в процессе заполнения стека указатель, перемещаясь "вверх", выходит за границу первоначально отведенной области, то происходит переполнение стека (stack overflow). Переполнение стека рассматривается как исключительная ситуация, требующая выполнения действий по ее ликвидации.

Основные операции над стеком и его элементами:

  • Добавление элемента в стек.
  • Удаление элемента из стека.
  • Проверка, пуст ли стек. (Стек считается "пустым", если указатель вершины совпадает с указателем нижней границы.)
  • Просмотр элемента в вершине стека без удаления.
  • Очистка стека.
  • Применение.
  • Динамическая структура Стек чаще всего используется при синтаксическом анализе всевозможных выражений.
Кстати, каждое приложение имеет собственный стек. В нём компилятор создает локальные переменные. А, также, через стек происходит передача параметров в функцию.

Стек протоколов TCP/IP

Стек протоколов TCP/IP (англ. Transmission Control Protocol/Internet Protocol) — набор сетевых протоколов разных уровней модели сетевого взаимодействия DOD, используемых в сетях. Протоколы работают друг с другом в стеке (англ. stack, стопка) — это означает, что протокол, располагающийся на уровне выше, работает «поверх» нижнего, используя механизмы инкапсуляции. Например, протокол TCP работает поверх протокола IP. Стек протоколов TCP/IP основан на модели сетевого взаимодействия DOD и включает в себя протоколы четырёх уровней:

прикладного (application),
транспортного (transport),
сетевого (internet),
уровня доступа к среде (network access)

Протоколы этих уровней полностью реализуют функциональные возможности модели OSI. На стеке протоколов TCP/IP построено всё взаимодействие пользователей в IP-сетях. Стек является независимым от физической среды передачи данных.

Реализация - стек

#include <iostream>
#include <string.h>
#include <time.h>
using namespace std;

class Stack
{
	// Нижняя и верхняя границы стека
	enum {EMPTY = -1, FULL = 20};

	// Массив для хранения данных
	char st[FULL + 1];

	// Указатель на вершину стека
	int top;

public:
	// Конструктор
	Stack();

	// Добавление элемента
	void Push(char c); 

	// Извлечение элемента
	char Pop();        

	// Очистка стека
	void Clear();    

	// Проверка существования элементов в стеке
	bool IsEmpty();    

	// Проверка на переполнение стека
	bool IsFull();     

	// Количество элементов в стеке
	int GetCount();    
};


Stack::Stack()
{
	// Изначально стек пуст
	top = EMPTY;
}

void Stack::Clear()
{
	// Эффективная "очистка" стека 
	// (данные в массиве все еще существуют, 
	// но функции класса, ориентированные на работу с вершиной стека,
	// будут их игнорировать)
	top = EMPTY;
}

bool Stack::IsEmpty()
{
	// Пуст?
	return top == EMPTY;
}

bool Stack::IsFull()
{
	// Полон?
	return top == FULL;
}

int Stack::GetCount()
{
	// Количество присутствующих в стеке элементов
	return top + 1;
}

void Stack::Push(char c)
{
	// Если в стеке есть место, то увеличиваем указатель
	// на вершину стека и вставляем новый элемент
	if(!IsFull())
		st[++top] = c;
}

char Stack::Pop()
{
	// Если в стеке есть элементы, то возвращаем верхний и
	// уменьшаем указатель на вершину стека
	if(!IsEmpty())
		return st[top--];
	else // Если в стеке элементов нет
		return 0;
}

void main()
{
	srand(time(0));
	Stack ST;
	char c;
	// пока стек не заполнится
	while(!ST.IsFull()){
        c=rand()%4+2;
		ST.Push(c);
	}
	// пока стек не освободится
	while(c=ST.Pop()){
       		cout<<c<<" ";
	}
	cout<<"\n\n";

}

Ссылки




stek.txt · Последние изменения: 2010/12/18 18:10 (внешнее изменение)