Stack

1. Overview of Stack

What is a stack

Stack is a data structure in which the order of data output is reversed to the order of input
-> Follows the LIFO order : Last-In-First-Out

Ex) In a computer various function call is occured, and when function ends program must return to the position where function was called : stack is ued to remember address of memory to return

Stack STL : CPP

create(size) :: = Create a stack that has a size of 'size'
is_full(s) :: = Check if stack is full
is_empty(s) :: = Check if stack is empty
push(s,item) :: = Push item to top of stack
pop(s) :: = Remove top element in stack
top(s) :: = Returns a reference to the top most element of the stack

2. Implement stack

Structure of stack

Stack is implemented using a 1d array (element of array can be any data type from int to struct (user defined datatype)

An additional int variable top is used to track the last element in stack (the element in the most top position : latest added, first to go out)

Code of stack

Define stack using class :

• Stores elements and top (include top as class element to be able to track top element for each stack)
• Initializes top=-1

class StackType
{
   int top;
   public:
   	element data[MAX]; //stack array
   	StackType() { top = -1; }
};

Check if stack is empty :

int is_empty(StackType *s) {
    return (s->top==-1);
}

Check if stack is full :

int is_full(StackType *s) {
    return (s->top == (MAX-1));
}

Check if stack is full and if not, add element to top of stack and increase top element by 1

void push(StackType *s) {
    if(is_full(s) return;
    else s->data[++(s->top)] = item;
}

Check if stack is empty and if not, delete top element and decrease top variable by 1

element pop(StackType *s) {
    if(is_empty(s)) return;
    else return s->data[(s->top)--];
}

Dynamic allocation of stack (for C)

• In previous example, we used a 1D array where the size was determined in compile time
• Therefore we need to know the stack size in compile time which is very difficult
• Therefore we use malloc() to dynamically allocate memory in run time : Can dynamically increase size of stack when needed

typedef int element;
typedef struct {
    element *data;
    int capacity;
    int top;
} StackType;

//When initialize stack, we secure capacity store 1 element in stack
void init_stack(StackType *s) {
    s->top = -1;
    s->capacity = 1;	//# of element
    s->data = (element *) malloc(s->capacity*sizeof(element)); 
    //Memory space to store all elements in stack
}

//delete stack
void delete (StackType *s) {
    free(s);
}

//Main difference is occured in push() : 
//When stack is full -> does not return but increase memory space by twice of original
void push(StackType *s, element item) {
    if(is_full(s)) {
    	s->capacity *= 2;
        s->data = (element *) realloc(s->data, s->capacity*sizeof(element)); 
    }
}

Note : realloc() is used to reset the size of memory space already allocated by previously using the malloc() function

3. Use of stack

Check bracket match

Check if the type of bracket matches the rules

• 1st condition : # of left bracket == # of right bracket
• 2nd condition : In same type bracket, left bracket must appear infront of right bracket
• 3rd condition : Different type of brackets of left and right should not cross each other

Algorithm of check_matching(expr) :

while(input expr did not reach end)
ch <- next letter of expr
switch(ch) 
    case '(' : case '[' : case '{' :
    	insert ch to stack
        break;
    case ')' : case']' : case '}' :
    	if (stack == empty) 
        	then 'error'
        else print out left bracket from stack
        	if(ch doesnt match with left bracket from stack)	
                    then 'error'
    break
if(stack is not empty) 
	then 'error' //not match 1st condition
      

Code :

class Solution {
public:
    bool isValid(string s) {
        stack<char> temp;
        for (int i=0; i<s.size(); i++) {
            if(s[i]=='{'||s[i]=='('||s[i]=='[') {
                temp.push(s[i]);
            }
            else if(!temp.empty()) {
                if(s[i]=='}'&&temp.top()=='{') temp.pop();
                else if(s[i]==']'&&temp.top()=='[') temp.pop();
                else if(s[i]==')'&&temp.top()=='(') temp.pop();
            }
            else 
                return false;
        }
        return temp.empty();                           
    }
};