• # 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:

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

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

Stack after popping top two elements:

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

## 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

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

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