Laboratory work number 1. "Semi-static data structures"

Objective: to investigate and study the stacks.


The task of the work: to master the skills of writing programs to study stacks in the programming language PASCAL.


Operating procedure :

• 
  study the description of the laboratory work;
• 
  according to the task given by the teacher, to develop an algorithm for the program for solving the problem;
• 
  write a program in PASCAL;
• 
  debug the program;
• 
  to solve a task;
• 
  issue a report.

Brief theory

The concept of queuing is well known to everyone from everyday life. The elements of the queue in the general case are orders for a particular service: knock out a check for the required amount at the store's cash desk, get the necessary information in the information desk, perform the next part processing operation on this machine in an automatic line, etc.

In programming, there is a data structure called a queue . This data structure is used, for example, to simulate real queues in order to determine their characteristics (average queue length, time the order is in the queue, etc.) with a given law of receipt of orders and the discipline of their maintenance.

Essentially, a queue is a semi - static structure — over time, the length of the queue, and the set of its constituent elements may change.

There are two main types of queues, differing in the discipline of servicing the elements in them:

1. 
   At the first of the disciplines, the order that entered the queue first is selected first for service (and removed from the queue). This discipline of service is called FIFO ( First input-First output , that is, the first one arrived - the first one left). The queue is open on both sides.

2. 
   It is accepted to call the second discipline LIFO ( Last input - First output , that is, the last one came - the first one left), during which the queue element that entered it last was selected first for service. The queue of this type in programming is called STEKOM (store) - this is one of the most commonly used data structures, which is very convenient for solving various problems.

Due to the specified service discipline, its only position is available on the stack, which is called the TOP of the stack - this is the position in which the last item on the stack is located. When we push a new element onto the stack, it is placed on top of the top and is now at the top of the stack itself. You can select an item only from the top of the stack; at the same time, the selected element is removed from the stack, and at its top is an element that was pushed onto the stack before the selected element (structure with limited access to data).

Algorithm

OPERATIONS ON STAGES:

- PUSH (s, i) —the item is pushed onto the stack, where s is the name of the stack, i is the item that is pushed onto the stack;

- POP (s) - selection of an element from the stack. When sampling the element is placed in the working area of ​​memory, where it is used;

- EMPTY (s) - stack checking for emptiness (true - empty, false - non-empty);

- STACKTOP (s) - reading the top element without deleting it.


Fragment of the program to create a stack (the necessary procedures)


Program STACK;

const

max_st = 50;

const

max_st = 50;

var

st, st2: array [1..max_st] of integer;

n: integer;


function empty: boolean; {Check stack for items in it}

begin

empty: = n = 0

end;


procedure push (a: char); {Put item on stack}

begin

inc (n);

st [n]: = a;

end;


procedure pop (var a: char); {Remove item from stack}

begin

a: = st [n];

dec (n);

end;


function full: boolean; {Check for overflow}


begin

Full: = n = max_st

end;


procedure stacktop (var a: char); {Learn top item}

begin

a: = st [n];

end;


begin {Main program}

.

.

end.

Tasks

• 
  Enter the characters forming a stack of them.

Options:

1. Swap the first and last elements of the stack.

2. Expand the stack, i.e. make the bottom of the stack the top and the top the bottom.

3. Remove the element that is in the middle of the stack, if an odd number of elements, and if even, then two medium.

4. Delete every second element of the stack.

5. Insert the '*' character in the middle of the stack, if there is an even number of elements, and if it is odd, then after the middle element.

6. Find the minimum element and insert 0 after it.

7. Find the maximum element and insert 0 after it.

8. Remove the minimum item.

9. Delete all items equal to the first.

10. Delete all items equal to the last.

11.Remove the maximum element.

12. Find the minimum element and insert 0 in its place.

• 
  Print the resulting stack to the screen.

• 
  Print the resulting stack.