Stack Basics

• Stack is usually implemented as a list,

with additions and removals taking place
at one end of the list
• The active end of the list implementing
the stack is the top of the stack
• Stack types:
– Static – fixed size, often implemented using
an array
– Dynamic – size varies as needed, often
implemented using a linked list
18-771
 Stack Operations and Functions

Operations:
– push: add a value at the top of the stack
– pop: remove a value from the top of the stack
Functions:
– isEmpty: true if the stack currently contains no
elements
– isFull: true if the stack is full; only useful for
static stacks

18-772
 Static Stack Implementation
• Uses an array of a fixed size
• Bottom of stack is at index 0. A variable called
top tracks the current top of the stack
const int STACK_SIZE = 3;
char s[STACK_SIZE];
int top = 0;

top is where the next item will be added

18-773
 Array Implementation Example
This stack has max capacity 3, initially top = 0 and
stack is empty.

K K
push('E'); push('K'); push('G');
E E E
top is 1 top is 2 top is 3

18-774
 Stack Operations Example
After three pops, top is 0 and the stack is empty

K
pop(); pop(); pop();
(remove G) E (remove K) E (remove E)

18-775
 Array Implementation
char s[STACK_SIZE];
int top=0;
To check if stack is empty:
bool isEmpty()
{
if (top == 0)
return true;
else return false;
}

18-776
 Array Implementation
char s[STACK_SIZE];
int top=0;
To check if stack is full:
bool isFull()
{
if (top == STACK_SIZE)
return true;
else return false;
}

18-777
 Array Implementation
To add an item to the stack
void push(char x)
{
if (isFull())
{error(); exit(1);}
// or could throw an exception
s[top] = x;
top++;
}
18-778
 Array Implementation
To remove an item from the stack
void pop(char &x)
{
if (isEmpty())
{error(); exit(1);}
// or could throw an exception
top--;
x = s[top];
}
18-779
 Class Implementation
class STACK
{
private:
char *s;
int capacity, top;
public:
void push(char x);
void pop(char &x);
bool isFull(); bool isEmpty();
STACK(int stackSize);
~STACK()
};
18-780
 Exceptions from Stack Operations
• Exception classes can be added to the
stack object definition to handle cases
where an attempt is made to push onto a
full stack (overflow) or to pop from an
empty stack (underflow)
• Programs that use push and pop
operations should do so from within a try
block.
• catch block(s) should follow the try
block, interpret what occurred, and inform
the user.
18-781
 18.2 Dynamic Stacks

• Implemented as a linked list

• Can grow and shrink as necessary
• Can't ever be full as long as memory is
available

18-782
 Dynamic Linked List Implementation
• Define a class for a dynamic linked list

• Within the class, define a private member

class for dynamic nodes in the list

• Define a pointer to the beginning of the

linked list, which will serve as the top of the
stack

18-783
 Linked List Implementation

A linked stack after three push operations:

push('a'); push('b'); push('c');

c b a NULL

top

18-784
 Operations on a Linked Stack
Check if stack is empty:
bool isEmpty()
{
if (top == NULL)
return true;
else
return false;
}

18-785
 Operations on a Linked Stack

Add a new item to the stack

void push(char x)
{
top = new LNode(x, top);
}

18-786
 Operations on a Linked Stack

Remove an item from the stack

void pop(char &x)
{
if (isEmpty())
{ error(); exit(1);}
x = top->value;
LNode *oldTop = top;
top = top->next;
delete oldTop;
}
•

18-787
 18.3 The STL stack Container
• Stack template can be implemented as a
vector, list, or a deque
• Implements push, pop, and empty
member functions
• Implements other member functions:
– size: number of elements on the stack
– top: reference to element on top of the stack
(must be used with pop to remove and retrieve
top element)
18-788