Algorithms and Data Structures : Stack

Algorithms and Data Structures : Stack - Stack is a linear data structure with the addition or subtraction of elements performed at one end only. Stack implements last entry last out (LIFO = last in, first out). If we have a pile of books, we have to take one at a book from the top so that the stack does not collapse.

Figure 3.1 Example of a pile in daily life

Operation on stack

There are four basic operations on stack, namely:

1. Initialize stack

Stack initialization operation creates an empty stack, a stack that does not have
elements.

Figure 3.2 Initialize stack

2. Push

Push operation is the operation of adding to the top of the pile of data in a stack. The algorithm to add data on the stack:

 Create a new data that will be pushed into the stack.
 The new data is pushed into the stack.
 The top pointer is modified to point to the data that you just added.

Figure 3.3 Push

3. Pop

Pop operation on the stack is an operation of taking data from a stack. The data is taken from the top of the stack. The algorithm to take a data from a stack is defined as follows:

 Initially, there is a stack that already has some data with the top data as the top.
 The top pointer is modified to point to the data under the top data.
 The data is taken from the top of the stack.

Figure 3.4 Pop

4. isEmpty

IsEmpty operation checks if the stack has elements or not. If the stack is empty, the operation will return true. If the stack is not empty, the operation will return a false value.

Implementation
Stack data structure can be implemented in two ways, namely by the array and the linked list. Implementation of the array uses an array of records. Each record has two fields, namely the data to store the data values and top to keep the top spot index on the stack. In the implementation of the linked list, each node is also a record for storing the data and for the pointer to the address of the other node.

Figure 3.5 Implementation of the stack

This module only deals with array implementation of stack. Stack can be implemented with an array and an integer index that records the top of the pile. Top is set -1 for an empty stack. To push, do increment the top counter and write the data into a top position in the array. To pop, do decrement the top counter.
   typedef struct{
      int TOP;
      int data[20];
      }stack;
   void buatStack(stack &S){
      int i;
      S.TOP=-1;
      }
   void push(stack &S, int IB){
      S.TOP= S.TOP + 1;
      S.data[S.TOP] = IB;
   }
   void pop(stack &S){
      int IB;
      if (stackKosong(S)!= 1){
      IB = S.data[S.TOP];
      cout<<" data yang diambil = "<<IB<<endl;
      S.TOP= S.TOP-1;
      }
      }
   int stackKosong(stack S){
      int hasil;
      if (S.TOP== -1) {
         hasil = 1;
         }
      else hasil = 0;
   return hasil;
   }

Exercises
1. Create a program to push data into a stack and display data from the stack.
2. Create a program to reverse the arrangement of a string of characters entered by the user.