Stack class (array implementation)

public class Stack{

private int[] stack;

private int topOfStack;

 

public Stack(){

this.stack = new int[10];

this.topOfStack = -1; //initially empty

}

 

public boolean isEmpty(){

//code not shown

}

public int pop(){

//code not shown

}

public void push(){

//code not shown

}

Push method

//push an item onto stack

public void push(int item){

if(topOfStack == stack.length-1){

System.out.println("Stack Full!");

}else{

topOfStack = topOfStack + 1;

stack[topOfStack] = item;

}

}

Take a moment to consider this. It relates directly to the simulation on the unit page.

Abstract Data Structure

An abstract data structure is a data structure which stores data and also has methods which can manipulate the data.

For example, a stack can store data and it has push(), pop() methods to add and remove data from the stack.

Another example is a queue, which has enqueue() and dequeue() methods to add and remove items from the queue.

stack review

Name 3 methods which operate on a stack.

Describe the behaviour of a stack.

A stack, CITIES, contains strings. Write an algorithm in pseudocode that will pop items from the stack until "Edinburgh" is reached.

A empty stack of strings, CITIES, exists. Write an algorithm that will input strings and push them onto the stack until -1 is entered.

Stacks

how the undo function in your applications works

Stacks

A stack is an .

It has interesting behaviour → LAST IN FIRST OUT LIFO

We can push(item) onto the top of the stack.

We can pop() items from the stack (ie remove them) and then update the top of the stack.

We can peek() at the item at the top of the stack without popping it!

We can check if a stack isFull()

We can check if a stack isEmpty()

Check out this simulation in which a stack is implemented on a static 1-dimensional array of length 5.

push
pop
peek

 

Stack

 

     
    4
    3
    2
    1
    0
     

top

-1

Task

Complete the worksheet.

Another sim

Here is another stack simulation. With this one, the top of the stack is always the next available element, not the latest element.

Exercises

Past Paper Questions

Tags

stack array push pop lifo full empty