• Main Menu
  • Stacks


    Stacks are one of the commonly used data structures. A stack is also known as a last in first out (LIFO) system. It can be considered as a linear list in which insertion and deletion can take place only at one end called the top. This structure operates in much the same way as a stack of trays.

    This article covers the representation of stacks using arrays. For the representation using self-referential structures, please refer to Stacks using Dynamic Memory Allocation.

    Here is a stack of trays:
    Stack of trays

    The following figures illustrate a stack, which can accommodate maximum of 10 elements

    Stack after pushing elements 8,10,12,-5,6:

    Stack with 5 elements

    Stack after popping top two elements:
    Stack after popping 2 elements

    Stack after pushing elements -5,6,9,55
    Stack with 7 elements

    Operations on Stacks

    • createstack(s) — to initialize s as an empty stack
    • push(s,i) — to push element i onto stack s.
    • pop(s) — to access and remove the top element of the stack s
    • peek(s) — to access the top element of the stack without removing it from the stack s.
    • isfull(s) — to check whether the stack s is full
    • isempty — to check whether the stack s is empty

    Stack Declaration Using an Array

    Suppose elements of the stack are of type int and the stack can store a maximum of 10 elements.

    .cf { font-family: Lucida Console; font-size: 9pt; color: black; background: white; } .cl { margin: 0px; } .cb2 { color: blue; }

    #define MAX 10
    typedef struct
    {
        int top;
        int elements[MAX];
    }stack;
    stack s;

    • Here we have defined our own data type named stack.
    • The first element “top” will be used to index the topmost element
    • Array “elements” holds the elements of the stack
    • The last line declares a variable “s” of type stack

    Representation of Stack in Memory

    Representation of stack in memory

    Creating an Empty Stack

    • Before we can use a stack, it needs to be initialized.
    • As the index of array elements can take any value in the range 0 to MAX-1, the purpose of initializing the stack is served by assigning value -1 to the top of variable.
    • This simple task can be accomplished by the following function.

    void createstack( stack *ps)
    {
        ps->top = -1;
    }

    Testing if the Stack is Empty

    bool isempty(stack *ps)
    {
        if(ps->top==-1)
            return true;
        else
            return false;
    }

    or

    bool isempty(stack *ps)
    {
        return ((ps->top==-1)?true:false);
    } 

    or even

    bool isempty (stack *ps)
    {
        return ps->top==-1;
    }

    Note: bool can be defined as

    typedef enum {false, true} bool;

    Testing if the Stack is Full

    bool isfull(stack *ps)
    {
        if(ps->top==MAX-1)
            return true;
        else
            return false;
    }

    or

    bool isfull(stack *ps)
    {
        return ((ps->top==MAX-1)?true:false);
    }

    Push Operation

    Before the push operation, if the stack is empty, then the value of the top will be – 1 and if the stack is not empty then the value of the top will be the index of the element currently on the top. Therefore, when we place the value onto the stack, the value of top is incremented so that it points to the new top of stack, where incoming element is placed.

    void push(stack *ps, int value)
    {
        ps->top++;    
        ps->elements[ps->top]=value;
    }

    Pop Operation

    The element on the top of the stack is assigned to a local variable, which later on will be returned via the return statement. After assigning the top element to a local variable, the variable top is decremented so that it points to a new top

    int pop(stack *ps)
    {
        int temp;  
        temp=ps->elements[ps->top];    
        ps->top--;
        return temp;
    }

    Accessing the Top Element

    There may be instances when we want to access the top element of the stack without removing it from the stack.

     
    int peek( stack *ps)
    {
        return(ps->elements[ps->top]);
    }

    Got Something To Say:

    Your email address will not be published. Required fields are marked *

    One comment
    1. priya bhat

      27 June, 2012 at 10:24 am

      Hello

      I find some issue with array implementation of stack. As per the theory when you pop out the top most element, the “elements[ps->top]” should be empty or garbage value. But with this implementation element array still holds the top most value even after popping out. Please clarify this.

      EX:
      struct stack s;
      push(&s,10);
      push(&s,20);
      push(&s,30);
      push(&s,40);
      int x = pop(&s); // AFTER THIS MOMENT THE STACK VALUE SHOULD BE 10,20,30 ? BUT s.element[] still holds 10,20,30,40????
      display(&s);

      Reply
    C
    } 240 queries in 0.301 seconds.