Stacks And Queues

Stacks and Queues

implementation

Concept of Stacks, Operation on Stacks, Application of stacks-Expression evaluation, conversion of Infix, Postfix, Prefix expressions, Recursion, Tower of Hanoi, Concept of Queues, Operation on Queues, Types of queues - Priority Queues, Circular Queues, Double ended Queues.

problem solving

Implement stack using linked list, Implement queue using linked list, Balanced Parenthesis, Two stacks in an array, K stacks in an array, Next Greater element, Next Smaller element, Min stack, Largest Rectangular area in a histogram, Stock span, Infix to postfix, Infix to prefix, Reversing a queue, Generate numbers with given digits

implementation

stacks

data structure

it's a linear data structure, linear means the memory grows and shrinks in one direction only, and along with being linear, insertion and deletion is always at the same end, which is the top iterator, we say that stack is in lifo ( last-in-first-out ).

use cases of stacks

The undo-redo operations are underneath implemented as a stack, and even the back and forward navigation of web pages is managed by a stack handled by a web browser. The messages on whatsapp are pushed to the top always and shown to su likewise. The latest dialed or missed calls shown to us are also implemented using stacks.

Stacks helps us to evaluate expressions that have parenthesis, or have many operators of different precedence. It normalizes the expression’s precedence either through postfix conversion or prefix conversion and then evaluates, so these mathematical operations are evaluated using these internal conversions through stacks.

The scope of methods and variables are also implemented using stacks, for a function call. The main function is added to the stack by the compiler, from there, further function calls from main function will create memory blocks in the stack, and top will be incremented, and as soon as a function block reaches an end, the scope of that function block is resolved and that memory block is freed, and top is decremented again. In the same way, we can have infinite nested function calls, which as we know are recursive calls, implemented internally through stacks. We can say, the variables and parameters at the time of function call are stored in the call stack, which will be popped from memory when it comes back to the caller.

Advanced algorithms that involve backtracking and dynamic programming also use stack implementation to solve problems, such as solving a maze, or finding all the valid paths.

stack operations

the main operations include push(e) to add item to top and pop() to remove item from top, as well as other operations such as peek() to take a glimpse of the topmost stack item, and isempty() to see whether it has something in it.

stack implementation

a stack typically contains an array to store the elements, and a top pointer to point to the last pushed item of the array, which represents the top of stack anyway, or we can also define it using structures where we take a integer to store data as well as an pointer of type structure which acts as an pointer to point to the next node.

for array,

int arr[MaxSize];

int top = -1;

for linkedlist,

struct{

int data;

*next;

};

stack algorithms for array,

push(e)

overflow condition if( top == MaxSize - 1 )

return overflow error

push item top++

arr[top] = e

pop()

underflow condition if( top == -1 )

return underflow error

pop item item = arr[top]

top--

peek()
invalid index if( top == -1 )
return no element found
show item item = arr[top]
print item
isempty()
if empty if( top == -1 )
return true
if not empty else
return false
stacks time complexity analysis
to push or pop elements at the top would have O(1) time complexity, so stacks are always preferred when we need to push and pop items very frequently, where stacks outperforms other linear data structures.
but to access an element at a certain position in the stack, we would have to traverse the stack by popping elements one by one, leading to O(n) time complexity, as well as for searching if an element exists or not.
stack implementation in c using arrays,
#include <stdio.h>
#include <stdbool.h>
#define MAX 100

int arr[MAX];
int top = -1;

voidpush(int e){
if( top == MAX - 1 ){
printf("overflow");
return;
}
top++;
arr[top] = e;
}

intpop(){
if( top == -1 ){
printf("underflow");
return-1;
}
return arr[top--];
}

boolisempty(){
if( top == -1 ){
returntrue;
} else {
returnfalse;
}
}

intpeek(){
if( isempty() ){
printf("element not found\n");
return-1;
} else {
return arr[top];
}
}

intmain(){
peek();
pop();
push(5);
push(10);
pop();
return0;
}



using linked list,
struct node{
int data;
struct node *next;
};
push(head, e)
overflow condition linkedlist is dynamic ( no overflow error )
create a new dynamic node newnode = new node()
push item newnode->data = e
connect newnode with head node newnode->next = head
increment the top head = newnode

pop(head)
underflow condition if( head == null )
return underflow error
store pop node (to free memory) temp = head
pop item e = head->data
decrement top head = head->next
free node memory free(temp)


peek(head)
underflow condition if( head == null )
return underflow error
return data in node return head->data

isempty(head)
if empty if( head == null )
return true
if not empty else
return false






stack implementation in c using linked list,
#include <stdio.h>
#include <stdlib.h>

structnode{
int data;
structnode *next;
};

voidpush(struct node **head, int e){

structnode *newnode = (structnode *)malloc(sizeof(structnode));
newnode->data = e;

newnode->next = *head;
*head = newnode;
}

intpop(struct node **head){
if( *head == NULL){
printf("underflow");
return0;
}
structnode *temp = *head;

int e = temp->data;
*head = (*head)->next;

free(temp);
return e;
}

intmain(){

structnode *top = NULL;

push(&top, 5);
printf(" %d \n",pop(&top));
printf(" %d \n",pop(&top));
push(&top, 10);
push(&top, 20);
printf(" %d \n",pop(&top));
printf(" %d \n",pop(&top));
printf(" %d \n",pop(&top));
return0;
}

problem solving

Conversion from Infix to Postfix


/*
Infix Expression : (A+(B*C-(D/E*F)^G)+3*H-2)
Postfix Expression : ABC*DE/F*G^-+3H*+2-

1 brackets -> open or closed
2 operands -> alphabets ( upper or lower ) or nums
3 operators -> + - * / ^ ( of different precedence )

3 arrays, a stack to evaluate, a postfix array, and an infix expression
simple algo to convert to postfix

1 we parse the infix expression using while loop

2 if it has an open bracket -> push it to the stack

3 if we have an operand -> directly push it to postfix array

4 if we get an operator -> calculate precedence
1 while top of stack has operator
2 if top of stack has no operator -> push current operator to stack
3 if top of stack has operator -> if its precedence is greater or equal than current
operator's precedence, then pop from stack, push to postfix
4 else if stack operator has less precedence -> push current operator to stack

5 if we get an closed bracket ->
1 pop it from stack till we encounter open bracket
2 evaluate all operators in stack and push it to postfix

How many functions do we need?
precedence function
infix to postfix function
*/

#include <stdio.h>
#include <stdbool.h>
#define MAX 100
char stack[MAX];
int top = -1;
void push(char e){
if( top == MAX - 1 ){
printf("overflow");
return;
}
top++;
stack[top] = e;
}
char pop(){
if( top == -1 ){
printf("underflow");
return '\0';
}
return stack[top--];
}
bool isempty(){
if( top == -1 ){
return true;
} else {
return false;
}
}
char peek(){
if( isempty() ){
printf("element not found\n");
return '\0';
} else {
return stack[top];
}
}
int precedence(char e){
if(e == '^'){
return 3;
} else if(e == '*' || e == '/'){
return 2;
} else if(e == '+' || e == '-'){
return 1;
} else {
return 0;
}
}
int main(){

char e[MAX];
printf("enter expression: ");
scanf("%s", e);

char ans[MAX];
int ans_index = 0;

for(int i = 0; e[i] != '\0'; i++){
if(e[i] == '('){
push(e[i]);
} else if( e[i] >= 65 && e[i] <= 90 || e[i] >= 97 && e[i] <= 122 || e[i] >= 48 && e[i] <= 57){
ans[ans_index++] = e[i];
} else if(e[i] == ')'){
while(peek() != '(' && !isempty() ){
ans[ans_index++] = pop();
}
if (!isempty()) {
pop();
}
} else {
while( !isempty() && precedence(peek()) >= precedence(e[i]) ){
ans[ans_index++] = pop();
}
push(e[i]);
}
}

while( !isempty() ){
ans[ans_index++] = pop();
}
ans[ans_index] = '\0';
printf("\n postfix expression: %s", ans);


return 0;
}

output:
enter expression: (A+(B*C-(D/E*F)^G)+3*H-2)
postfix expression: ABC*DE/F*G^-+3H*+2-









postfix expression evaluation ( single digit expression )
/*
Postfix expression: 23*45*+
ans: 26
1. we get an postfix expression from the user
2. we parse the postfix expression as a string
3. either we get an operand ( which are numbers in this case )
or we get an operator ( binary operators only in this case )
4. since all the operators are binary and not ++ unary operator,
we will push 2 operands into the stack,
and pop them once we encounter an operator
5. popped operands will be evaluated based on operator
and the resulting expression is pushed back to the stack
6. the final expression is stored in the top of the stack, now we pop it.
*/
#include <stdio.h>
#define MAX 100
int stack[MAX];
int top = -1;
void push(int e){
if( top == MAX - 1){
printf("overflow");
return;
} else {
top++;
stack[top] = e;
}
}
int pop(){
if( top == - 1 ){
printf("underflow");
return '\0';
} else{
return stack[top--];
}
}
int cal(char e){
if(e == '*'){
return pop() * pop();
} else if(e == '+'){
return pop() + pop();
} else if(e == '-'){
return pop() - pop();
} else if(e == '/'){
return pop() / pop();
} else {
printf("wrong operator");
return 0;
}
}
int main(){

char s[MAX];
printf("enter postfix expression: ");
scanf("%s", s);

for(int i = 0; s[i] != '\0'; i++){
if( s[i] >= 48 && s[i] <= 57 ){
push((int) s[i] - 48);
} else {
push(cal(s[i]));
}
}

printf("ans: %d", pop());

return 0;
}


balanced parenthesis
/*
input: {[[()]]} output: true
input: ([]}) output: false
input: {[] output: false
we have three types of brackets and each has open and closed brackets,
3 * 2 = 6 symbols in a parenthesis expression, other expressions are ignored.
for every open bracket, there must be a closed bracket following it.

for every pair of brackets, open bracket is pushed to stack,
and once it encounters the closed bracket of the same type, it gets popped.

if at the end of expression, stack is empty,
means pair of brackets are balanced
else they are not balanced at all.
*/
#include <stdio.h>
#include <stdbool.h>
#define MAX 100
char stack[MAX];
int top = -1;
void push(char e){
if( top == MAX - 1){
printf("overflow");
return;
} else {
top++;
stack[top] = e;
}
}
char pop(){
if( top == - 1 ){
printf("underflow");
return '\0';
} else{
return stack[top--];
}
}
bool isempty(){
if( top == -1 ){
return true;
} else {
return false;
}
}
char peek(){
if( isempty() ){
return '\0';
} else {
return stack[top];
}
}
int main(){
char s[MAX];
printf("enter expression: ");
scanf("%s", s);

for(int i = 0; s[i] != '\0'; i++){
if( s[i] == '(' || s[i] == '[' || s[i] == '{' ){
push(s[i]);
} else if( peek() == '(' && s[i] == ')' || peek() == '[' && s[i] == ']' || peek() == '{' && s[i] == '}' ){
pop();
} else if( s[i] == '}' && peek() != '{' || s[i] == ')' && peek() != '(' || s[i] == ']' && peek() != '[' ){
push('-');
break;
}
}
if( isempty() ){
printf("%s is balanced", s);
} else {
printf("%s is not balanced", s);
}
return 0;
}


Conversion from infix to prefix
/*
Input : a+b*c/d
Output : +a*b/cd
Input : a+(b-c^(d+e))*f
Output : +a*-b^c+def
+ to convert infix to prefix expression
1. we take infix expression from user as a string
2. we reverse that expression and store it in another string
such that brackets as well as all expression is swapped
3. the same algorithm for postfix expression is evaluated
using stacks and operator precedence
4. the final expression is again reversed and returned as an prefix expression
*/
#include <stdio.h>
#include <stdbool.h>
#define MAX 100
char stack[MAX];
int top = -1;
void push(char e) {
if( top == MAX - 1 ) {
printf("overflow");
return;
}
top++;
stack[top] = e;
}
char pop() {
if( top == -1 ) {
printf("underflow");
return '\0';
}
return stack[top--];
}
bool isempty() {
if( top == -1 ) {
return true;
} else {
return false;
}
}
char peek() {
if( isempty() ) {
printf("element not found\n");
return '\0';
} else {
return stack[top];
}
}
int precedence(char e) {
if(e == '^') {
return 3;
} else if(e == '*' || e == '/') {
return 2;
} else if(e == '+' || e == '-') {
return 1;
} else {
return 0;
}
}
int main() {
char abc[MAX];
printf("enter expression: ");
scanf("%s", abc);

int i = 0;
while( abc[i] != '\0'){
i++;
}

char e[MAX];
int e_index = 0;
while( --i != -1 ){
if(abc[i] == ')'){
e[e_index++] = '(';
} else if(abc[i] == '('){
e[e_index++] = ')';
} else {
e[e_index++] = abc[i];
}
}
e[e_index] = '\0';
char ans[MAX];
int ans_index = 0;
for(int i = 0; e[i] != '\0'; i++) {
if(e[i] == '(') {
push(e[i]);
} else if( e[i] >= 65 && e[i] <= 90 || e[i] >= 97 && e[i] <= 122 || e[i] >= 48 && e[i] <= 57) {
ans[ans_index++] = e[i];
} else if(e[i] == ')') {
while(peek() != '(' && !isempty() ) {
ans[ans_index++] = pop();
}
if (!isempty()) {
pop();
}
} else {
while( !isempty() && precedence(peek()) >= precedence(e[i]) ) {
ans[ans_index++] = pop();
}
push(e[i]);
}
}
while( !isempty() ) {
ans[ans_index++] = pop();
}
ans[ans_index] = '\0';

char pre[MAX];
int pre_index = 0;
while(--ans_index != -1){
if(ans[ans_index] == ')'){
pre[pre_index++] = '(';
} else if(ans[ans_index] == '('){
pre[pre_index++] = ')';
} else {
pre[pre_index++] = ans[ans_index];
}
}
pre[pre_index] = '\0';

printf("\n prefix expression: %s", pre);
return 0;
}















prefix to postfix conversion
/* Iterate the given expression from right to left, one character at a time
1 If the character is operand, push it to the stack.
2 If the character is operator,
1 Pop an operand from the stack, say it's s1.
2 Pop an operand from the stack, say it's s2.
3 perform (s1 s2 operator) and push it to stack.
3 Once the expression iteration is completed, initialize the result string and pop
out from the stack and add it to the result.
4 Return the result.
when we concat strings, we have to make sure of null termination of the new string.
and because we are handling strings, not just characters, we need a 2D array stack.

Input: Prefix expression: *-A/BC-/AKL
Output: Postfix expression: ABC/-AK/L-*
*/
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#define MAX 100
char stack[MAX][MAX];
int top = -1;
void push(char* e) {
if( top == MAX - 1 ) {
printf("overflow");
return;
}
top++;
strcpy(stack[top], e);
}
char* pop() {
if( top == -1 ) {
printf("underflow");
return NULL;
}
return stack[top--];
}
bool operator(char e){
if(e == '^' || e == '*' || e == '/' || e == '+' || e == '-' ){
return true;
} else {
return false;
}
}
int main() {
char e[MAX];
printf("enter prefix expression: ");
scanf("%s", e);
char g[MAX], op1[MAX], op2[MAX];
int len = strlen(e);
for(int i = len - 1; i >= 0; i--){
if( !operator(e[i]) ){
char temp[2] = {e[i], '\0'};
push(temp);
}
else if( operator(e[i]) ){
g[0] = '\0';
strcpy(op1, pop());
strcpy(op2, pop());
strcat(g, op1);
strcat(g, op2);
char op3[2] = {e[i], '\0'};
strcat(g, op3);
push(g);
}
}
printf("%s\n", pop());
return 0;
}