[SOLVED] Last In-First Out Stack in bash?

Issue

Is it possible to do Last In-First Out Stack using shell scripting?
I am not expert in bash but I would like to learn
I can do it in c++ as follows

int main()  
{  
    stack<int> stack ;  
  
    stack_push(stack);  
    stack_peek(stack);  
    stack_search(stack, 2);  
    return 0; 
} 

Solution

You can implement a stack easily using an array.

Note that bash is not object oriented, so there is no way to write mystack.doSomething() like you would in C++. Instead, you have to pass the stack name as a parameter to the function: doSomething myStack. If you need only one stack, you can hardcode the stack name inside the functions, which makes things easier.

One Global Stack

#! /bin/bash
stack=()
push() { stack+=("$@"); }
peek() { printf %s\\n "${stack[-1]}"; }
pop() { peek; unset 'stack[-1]'; }

Interactive example usage. $ is the prompt:

$ push a b
$ push c
$ peek
c
$ pop
c
$ pop
b
$ pop
a
$ pop # stack is empty, results in error
-bash: unset: [-1]: bad array subscript

Multiple Stacks

#! /bin/bash
push() { local -n "stack=$1"; shift; stack+=("$@"); }
peek() { local -n "stack=$1"; printf %s\\n "${stack[-1]}"; }
pop() { peek "$1"; unset "$1[-1]"; }

Interactive example usage. $ is the prompt:

$ push stack1 a
$ push stack2 b
$ peek stack1
a
$ peek stack2
b

Other Operations

Remember that the stacks are just regular arrays. Functions like size or search can be implemented by accessing the array directly. For instance, for the size of stack write ${#stack[@]}.

Alternative Approach: Multiple Stacks In One Single Associative Array

Up until now, each stack used its own array. You have to make sure to avoid name collisions with the rest of your script. Because the variable for each stack used the stack name (first argument after push/peek/pop) the stacks could only have names accepted by bash (for instance stack1, but not stack 2, 3rdStack, ., or ""). As an alternative, you can store all stacks in a single associative array (also known as map). However, you will loose the direct array access from before, so implementing additional methods might get more involved:

#! /bin/bash
declare -A stacks=()
size() { local j="${stacks[.$1]}"; printf %d\\n "${j/-*/0}"; }
lastindex() { local i="$(size "$1")"; echo "$((i - 1))"; }
push() { local j="$(size "$1")"; stacks["$j.$1"]="$2"; stacks[".$1"]="$((j+1))"; }
peek() { local i="$(lastindex "$1")"; printf %s\\n "${stacks[$i.$1]}"; }
pop() { local i="$(lastindex "$1")"; peek "$1"; unset "stacks[$i.$1]"; stacks[".$1"]="$i"; }

This is only a basic implementation. You can only push one element at a time, that is, you have to write push stackname a; push stackname b instead of push stackname a b. peek or pop on an empty stack do nothing but print an empty line.

Answered By - Socowi

Answer Checked By - Pedro (WPSolving Volunteer)