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]);
}