In this course and the next two courses, we'll be going through two data structures in programming: Stacks and Queues. This course will be on stacks and its basic operations.
What is a stack?
There are many types of data structures which allow the storing of information, and a stack is one of them. A stack is a data structure that allows items to be added and removed from one end. That's why it's also described as a LIFO stack. Last In First Out. A stack can be directly compared to some real-life objects. For example, a stack of trays. Trays are only added and removed from the top. A stack of exercise books can also be used as another analogy. Students only take away or pass up exercise books from the top.
So what's the use of a stack?
While it may seem pretty useless to have a data structure that only accepts input and output from one end, you'll realize that certain applications would become easier to write when implementing stacks. For example, a calculator. Calculators are able to calculate calculations while following the rules of precedence by using stacks. Stacks are also used in your computer's allocation of memory. You see, even though the structure might seem quite rigid, stacks can actually be used in a great number of situations.
How are stacks implemented then?
Okay, let's get a bit into the theory. A stack can be implemented using an array and a number indicating the top of the stack. There is a flaw, however, that the capacity of the stack is fixed and limited. However, we could use Linked Lists to implement it so that the stack dynamically expands its capacity.
There are five basic operations associated with a stack:
Alright, let's start coding!
We'll start off first by declaring a constant, MAX, as the maximum height of the stack. This way, we can easily increase the maximum height as needed.
const MAX = 20;As mentioned before, each stack is made up of an array, and a number indicating its top. Since we want to make it modular, let's make our own type definition. (To learn more about user defined types, look up 'type' in the online help.)
type int_Stack = record int_array: array[0..MAX] of integer; top: integer; end;Now let's code all the five basic operations. The 'trick' is this: We identify that a stack is empty when top is equal to -1. That's why when we initialize it, we set top to become -1. Then when something is pushed, top increases to become 0. It's that simple!
function is_empty(s: int_Stack) : boolean; begin is_empty := (s.top = -1); end; function is_full(s: int_Stack) : boolean; begin is_full := (s.top = MAX); end; function top(s: int_Stack) : integer; begin top := s.int_array[s.top]; end; procedure push(var s: int_Stack; x: integer); begin if is_full(s) then Writeln('Stack Full') else begin s.top := s.top + 1; s.int_array[s.top] := x; end; end; function pop(var s: int_Stack) : integer; var t: integer; begin if is_empty(s) then Writeln('Stack Empty') else begin t := s.int_array[s.top]; s.top := s.top - 1; pop := t; end; end;Great! Now, with this library of commands, you can easily implement stacks into any program. But it doesn't end here. Go on to the next course to learn about Queues and how to implement them.