Shaligram Prajapat Ph.D.

Stack

A Stack is a linear data structure in which elements are inserted and deleted from one end only, called the TOP. It follows the LIFO (Last In, First Out) principle.
Example: Stack of plates. Stack of books.

Possible Operations:

Push: Insert an element onto the TOP of the stack.
Pop: Remove an element from the TOP of the stack.
Peek/Top: View the TOP element without removing it.
isEmpty: Check whether the stack is empty.
isFull: Check whether the stack is full in an array-based implementation.
Size: Find the number of elements in the stack.
Display/Traverse: View all elements of the stack.
Search: Find a specified element in the stack.
Clear: Remove all elements from the stack.

Stack Delcaration and Operations

#define MAX 100

typedef struct {

int data[MAX];

int top;

} Stack;

void push(Stack *s, int value);

int pop(Stack *s);

int peek(const Stack *s);

int isEmpty(const Stack *s);

int isFull(const Stack *s);

void display(const Stack *s);

MultiStack (n=2)

Two stacks can be implemented efficiently in one array by growing the two stacks from opposite ends of the array.

Two Stacks in a Single Array

Suppose the array has size MAX = 10.

Stack 1 grows from left to right.
Stack 2 grows from right to left.
Both stacks share the unused space in the middle.
Overflow occurs when top1 + 1 == top2.

Array: with 2 stacks

+----+----+----+----+----+----+----+----+----+----+--+----+

| S1 | S1 | S1 | | | | | S2 | S2 | S2 |

+----+----+----+----+----+----+----+----+----+----+--+----+

↑ ↑

top1 top2

Initialization

#define MAX 10

int stack[MAX];

int top1 = -1; // Stack 1

int top2 = MAX; // Stack 2

PUSH Operation

______________________________

Push into Stack 1

void push1(int value)

{

if (top1 + 1 == top2)

printf("Stack Overflow");

else

stack[++top1] = value;

}

Push into Stack 2

void push2(int value)

{

if (top1 + 1 == top2)

printf("Stack Overflow");

else

stack[--top2] = value;

}

POP Operation

______________________________

Pop from Stack 1

int pop1()

{

if (top1 == -1)

return -1;

return stack[top1--];

}

Pop from Stack 2

int pop2()

{

if (top2 == MAX)

return -1;

return stack[top2++];

}

Example

If we perform:

push1(10)

push1(20)

push1(30)

push2(90)

push2(80)

push2(70)

The array becomes:

Index: 0 1 2 3 4 5 6 7 8 9

+----+----+----+----+----+----+----+----+----+----+

| 10 | 20 | 30 | | | | | 70 | 80 | 90 |

+----+----+----+----+----+----+----+----+----+----+

↑ ↑

top1 top2

Main advantage: The unused space of one stack can be used by the other stack. This reduces wastage compared with allocating two separate fixed-size arrays.

Viva Questions

Why are two stacks implemented from opposite ends?
What is the initial value of top1?
What is the initial value of top2?
What is the condition for overflow?
How does push1() differ from push2()?
How does pop1() differ from pop2()?
What happens when the two stacks meet?
What is the advantage of implementing two stacks in one array?
What is the time complexity of push and pop operations?
Can the two stacks have different numbers of elements? Why?

Applications of Stack