# Data Structure (I) - 04 Stacks
> PART (I) - 04
> Other parts in this series $\rightarrow$ [Data Structure - Syllabus ](/bU7575BKTwmwkvmJ5742xA)
> All the code in this part $\rightarrow$ [Stack](https://github.com/Benny0w0Liu/Data-Structure-Learning/tree/main/Stack)
# Stack as ADT
In computer science, a stack is an abstract data type that serves as a collection of elements with two main operations:
* Push - which adds an element to the collection, and
* Pop - which removes the most recently added element.
The order in which an element added to or removed from a stack is described as last in, first out, referred to by the acronym LIFO.
You can imagine that with pictures below. However, there is disgusting but impresssive way to understand this concept. Imagine you are a stack, then instead of pooping, the only way your body to excretes shit is vomit :)
<div style="displat:flex; margin-left:10px">
<img src="https://hackmd.io/_uploads/BkVX-5sqC.png" width="50%">
<img src="https://hackmd.io/_uploads/Sk46eqsqC.png" width="30%">
</div>
## constructor
Need a head.
## operations
* Push element, $O(1)$
* Pop element, $O(1)$
# Implementation(Using C)
## Array Implementation
Using a number to record the top index.
<img src="https://hackmd.io/_uploads/S11uMis5A.png" width="30%">
```c=
void push(int stack[],int* top,int size,int n) {
if(*top==size-1) return;
stack[++(*top)]=n;
}
```
```c=
void pop(int* stack,int* top){
if(*top==-1) return;
(*top)--;
}
```
## Link List Implementation
There are two terminals in the link list(head and tail), which one should we use as top? When we using tail as the top we need to travel it to the end each time, the time complexity of pushing or popping the element will be $O(n)$ instead of $O(1)$, so we can only use the head as the top.
* push : insert head (see [Link List operation](/LP6dmIsqRLWOI8pQC6cqhQ))
```c=
void push(struct Node** pointerToTop ,int x){
struct Node* temp = (struct Node*)malloc(sizeof(struct Node*));
temp->data = x;
temp->next = *pointerToTop;
*pointerToTop=temp;
}
```
* pop : delete head (see [Link List operation](/LP6dmIsqRLWOI8pQC6cqhQ))
```c=
void pop(struct Node** pointerToTop){
if (*pointerToTop==NULL) return;
struct Node* temp = *pointerToTop;
*pointerToTop = (*pointerToTop)->next;
free(temp);
}
```
# Application(using C++)
We will use `<stack>` libarary.
The functions associated with stack are:
* empty( ) : Returns whether the stack is empty – Time Complexity : $O(1)$
* size( ) : Returns the size of the stack – Time Complexity : $O(1)$
* top( ) : Returns a reference to the top most element of the stack – Time Complexity : $O(1)$
* push(x) : Adds the element 'x' at the top of the stack : Time Complexity : $O(1)$
* pop( ) : Deletes the most recent entered element of the stack – Time Complexity : $O(1)$
## Reverse String
Simply chanhe "Hello World" to "dlroW olleH"
* Time complexity = $O(n)$
* Space complexity = $O(n)$
```cpp=
#include<iostream>
#include<stack>
#include <cstring>
using namespace std;
void Reverse(char C[],int n){
stack<char> S;
for(int i=0;i<n;i++){
S.push(C[i]);
}
for(int i=0;i<n;i++){
C[i]=S.top();
S.pop();
}
}
int main(){
char C[101];
cin.getline(C,101);
Reverse(C,strlen(C));
cout<<C;
}
```
## Check for balanced parentheses
| expression | parentheses | balanced? |
| -------- | -------- | -------- |
| (A+B) | ( ) | Yes |
| {(A+B)*(C+D)}|{ ( )( ) }| Yes |
| {(A+B)+(C+D}|{ ( )( }| No |
| ( A*B }|( }| No |
| )C/D(|) (| No |
| (A+B*[CD)]|( [ ) ]| No |
Last open. First close. $\rightarrow$ Last in. First out.
Take `char[7] str="{()()}"` for example:
|||||
|:---:|:--- |:---:|:---|
| i=0 | str[i]: `{`<br>stack : `{`$\leftarrow$push | i=3 |str[i]: `(` <br>stack : `{`,`(`$\leftarrow$push <br> |
| i=1 | str[i]: `(` <br> stack : `{`,`(`$\leftarrow$push <br> | i=4 | str[i]: `)` <br> stack : `{`$\leftarrow$pop`(` <br> |
| i=2 | str[i]: `)` <br> stack : `{`$\leftarrow$pop`(` <br> | i=5 | str[i]: `}` <br> stack : $\leftarrow$pop`{` <br> |
```cpp=
#include<iostream>
#include<stack>
#include <cstring>
using namespace std;
bool IfBalanced(char C[],int n){
stack<char> S;
for(int i=0;i<n;i++){
if(C[i]=='('||C[i]=='['||C[i]=='{'){
S.push(C[i]);
}else if(C[i]==')'||C[i]==']'||C[i]=='}'){
if((C[i]==']'&&S.top()=='[') || (C[i]==')'&&S.top()=='(') || (C[i]=='}'&&S.top()=='{')) S.pop();
else return false;
}
}
return true;
}
int main(){
char C[101];
gets(C);
if(IfBalanced(C,strlen(C))) cout<<"It is Balanced"<<endl;
else cout<<"It is opened"<<endl;
}
```
## Infix, Prefix and Postfix
Here we go again, the descrete mathmatic...
| Notation|Example|Order|Complexity|Usage|
|---|-------|---|---|---|
| Infix|1. A + B<br>2. A+B*C | Operators between operands | Requires precedence rules or parentheses | Most familiar, human-readable|
| Prefix | 1. + A B<br>2. +A*BC | Operators before operands | Unambiguous without parentheses | Useful in compilers and functional programming |
| Postfix | 1. A B +<br>2. ABC*+ | Operators after operands | Easily evaluated by machines **using a stack** | Common in stack-based machine computation |
> we will focus on postfix because it is easily evaluated by machines using a stack. You can draw a stack and run the code with your brain and find out how it work.
### Infix to postfix
There are only 4 operators : `+`, `-`, `*`, `/`, and I only use `()` as parentheses in this case.
```cpp=
#include<iostream>
#include<stack>
#include <cstring>
using namespace std;
void InfixToPostfix(char str[]){
char result[101]={'\0'};
stack<char*> S;//storage operators and parentheses
const char* d = " ";
char *p;
p = strtok(str, d);
while (p != NULL) {
if(strcmp(p,"(")==0){
S.push(p);//push the parentheses
//if p==')', then close the parentheses
}else if(strcmp(p,")")==0){
//push all the operator in the parentheses, until the left parentheses and pop it out
while(strcmp(S.top(),"(")!=0){
strcat(result, S.top());
strcat(result, " ");
S.pop();
}
S.pop();
}
//if p == operators
else if(strcmp(p,"+")==0||strcmp(p,"-")==0||strcmp(p,"*")==0||strcmp(p,"/")==0){
//if p =="+" or "-" then check if there are "*" and "/" in stack
if((strcmp(p,"+")==0||strcmp(p,"-")==0) && !S.empty()){
//if S.top() == "*" or "/" then add them first (including the operators storage before)
if(strcmp(S.top(),"*")==0||strcmp(S.top(),"/")==0){
while(strcmp(S.top(),"(")!=0){//until the parentheses
strcat(result, S.top());
S.pop();
strcat(result, " ");
}
}
}
S.push(p);//push into stack
}else{
strcat(result, p);//add operands directerlly into stack
}
if(result[strlen(result)-1]!=' '&&strlen(result)!=0) strcat(result, " ");
p = strtok(NULL, d);
}
while(!S.empty()){//add rest of the operators
strcat(result, S.top());
S.pop();
strcat(result, " ");
}
strncpy(str, result, 101);
}
int main(){
char str[101];
cout<<"Input your formula, please add space between operators and operands"<<endl;
cin.getline(str,101);
InfixToPostfix(str);
cout<<str;
}
```
example input and output:
```
Input your formula, please add space between operators and operands
( ( 1 + 2 ) * 3 - 4 ) * 5
1 2 + 3 * 4 - 5 *
```
### Calculate postfix
postfix notation is much easier for computer to calculate:D
```cpp=
#include<iostream>
#include<stack>
#include <cstring>
using namespace std;
int CalculatePostfix(char str[]){
stack<int> S;//storage numbers
const char* d = " ";
char *p;
p = strtok(str, d);
while (p != NULL) {
if(strcmp(p,"+")==0||strcmp(p,"-")==0||strcmp(p,"*")==0||strcmp(p,"/")==0){
//take first two numbers and operate it if p is operator
int a=S.top();
S.pop();
int b=S.top();
//push back result
if(strcmp(p,"+")==0) S.push(b+a);
else if(strcmp(p,"-")==0) S.push(b-a);
else if(strcmp(p,"*")==0) S.push(b*a);
else if(strcmp(p,"/")==0) S.push(b/a);
}else{
S.push(atoi(p));//push p if it is a number
}
p = strtok(NULL, d);
}
return S.top();//it should be the only one in stack
}
int main(){
char str[101];
cout<<"Input your postfix formula, please add space between operators and operands"<<endl;
cin.getline(str,101);
int num=CalculatePostfix(str);
cout<<num;
}
```
example input and output:
```
Input your postfix formula, please add space between operators and operands
1 2 + 3 * 4 - 5 *
25
```
Sign in with Wallet
Connect another wallet