Лабораторная работа 49

Стеки и очереди

Цель работы: изучить создание и работу с очередями и стеками, научиться решать задачи с использованием очередей и стеков на языке C++.

Теоретические сведения

Очередь и стек – это частные случаи однонаправленного списка.

Стеки

В списках доступ к элементам происходит посредством адресации, при этом доступ к отдельным элементам не ограничен. Но существуют также и такие списковые структуры данных, в которых доступ к элементам ограничен, наиболее важная из них – стековый список или просто стек.

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

Стек – это список, у которого доступен один элемент (одна позиция). Этот элемент называется вершиной стека. Взять элемент можно только из вершины стека, добавить элемент можно только в вершину стека. Например, если записаны в стек числа 1, 2, 3, то при последующем извлечении получим 3,2,1.

Рис. Стек

Описание стека выглядит следующим образом:

struct имя_типа {

информационное поле;

адресное поле;

};

где информационное поле – это поле любого ранее объявленного или стандартного типа;

адресное поле – это указатель на объект того же типа, что и определяемая структура, в него записывается адрес следующего элемента стека.

Например:

struct list {

type pole1;

list *pole2 ;

} stack;

В стеке добавление и удаление элементов осуществляется с одного конца, который называется вершиной стека. Поэтому для стека можно определять функции:

· доступ к вершине;

· добавление элемента в вершину;

· удаление элемента из вершины.

Пример 1. Рассмотрим задачу. Пусть требуется ввести некоторую последовательность символов, заканчивающуюся точкой, и напечатать ее в обратном порядке. Представленная ниже программа сначала вводит все символы последовательности, записывая их в стек, а затем содержимое стека печатается в обратном порядке. Реализация стека выполнена в связанном хранении при помощи указателей p и q на тип, именованный как STACK.

#include <stdio.h>

#include <stdlib.h>

typedef struct st {// объявление типа STACK

char ch;//информационное поле

struct st *ps;

//указатель на структуру типа st

} STACK;

void main() {

STACK *p,*q;

char a;

p=NULL;

do {// заполнение стека

scanf("%c",&a);

q=(STACK*)malloc(sizeof(STACK));

q->ps=p; p=q; q->ch=a;

}

while(a!='.');

do {// печать стека

p=q->ps;

free(q);q=p;

printf("%c",p->ch);

}

while(p->ps!=NULL);

}

Пример 2. Дана строка символов. Проверьте правильность расстановки в ней круглых скобок.

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

//объявление структуры стека

struct node {

struct node *next;

char ch;

};

//Объявление вершины стека

struct node *VER=NULL;

struct node *steak;

void AddToSteak(char ch) { //Добавление элемента в стек

steak =(node*)malloc(sizeof(node));

steak->next=VER;

steak->ch=ch;

VER=steak;

}

int DelNode() {//Удаление элемента из стека

if(VER==NULL) return 0;

VER=steak->next;

free(steak);

steak=VER;

return 1;

}

void DestroySteak() {//Удалить весь стек

printf("Error!");

while(steak!=NULL) {

VER=steak->next;

free(steak);

steak=VER;

}

}

void main() {

char text[255];

int i;

int flag=1;

//идентификатор при удалении верхнего элемента стека

printf("Input line of text with \"(\" and \")\" ->");

gets(text);

for(i=0;i<strlen(text); i++) {

if(text[i]==')' ) {

if(steak==NULL) {

//Попытка удалить нулевой элемент стека

flag=0;;

break;

}

if(steak->ch=='(') {

flag=DelNode();

if(flag==0) {//Попытка удалить нулевой элемент стека

break;

}

}

}

if(text[i]=='(')AddToSteak(text[i]);

}

if(flag!=0 && steak==NULL) printf("All right!");

else DestroySteak();

printf("\n");

}